Mikkel Thorup
Abstract
The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s, find the shortest path from s to all other vertices in the graph.
Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from s. Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from s. However, we do not know how to sort in linear time.
Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.
- AHUJA, R. K., MELHORN, K., ORLIN, J. B., AND TARJAN, R.E. 1990. Faster algorithms for the shortest path problem. J. ACM 37, 213-223. Google Scholar
- ALBERS, S. AND HAGERUP, f. 1997. Improved parallel integer sorting without concurrent writing. Inf. Control 136, 25-51. Google Scholar
- ANDERSSON, A., HAGERUP, f., NILSSON, S., AND RAMAN, R. 1995. Sorting in linear time? In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (Las Vegas, Nev., May 29-June 1). ACM, New York, pp. 427-436. Google Scholar
- ANDERSSON, A. MILTERSEN, P. B. AND THORUP, M. 1999. Fusion trees can be implemented with AC~ instructions only. Theoret. Comput. Sci., 215, 337-344. Google Scholar
- CHERKASSKY, B. V., GOLDBERG, A. V., AND SILVERSTEIN, C. 1997. Buckets, heaps, lists, and monotone priority queues. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 83-92. Google Scholar
- DIJKSTRA, E. W. 1959. A note on two problems in connection with graphs. Numer. Math. 1, 269-271.Google Scholar
- DINIC, E.A. 1978. Finding shortest paths in a network. In Transportation Modeling Systems, Y. Popkov and B. Shmulyian, eds. Institute for System Studies, Moscow, CIS, pp. 36-44.Google Scholar
- FREDMAN, M. L., AND TARJAN, R.E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3 (July), 596-615. Google Scholar
- FREDMAN, M. L., AND WILLARD, D. E. 1993. Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424-436. Google Scholar
- FREDMAN, M. L., AND WILLARD, D.E. 1994. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 533-551. Google Scholar
- GABOW, H.N. 1985. A scaling algorithm for weighted matching on general graphs. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 90-100.Google Scholar
- GABOW, H. N. AND TARJAN, R.E. 1985. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209-221.Google Scholar
- HENZINGER, M. R., KLEIN, P., RAO, S., AND SUBRAMANIAN, S. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 53, 2-23. Google Scholar
- KRUSKAL, J. B. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48-50.Google Scholar
- MELHORN, K., AND NAHLER, S. 1990. Bounded ordered dictionaries in O(log log n) time and O(n) space. Inf. Proc. Lett. 35, 183-189. Google Scholar
- RAMAN, R. 1996. Priority queues: small monotone, and trans-dichotomous. In Proceedings of the 4th Annual European Symposium on Algorithms. Lecture Notes on Computer Science, vol. 1136, Springer-Verlag, New York, pp. 121-137. Google Scholar
- RAMAN, R. 1997. Recent results on the single-source shortest paths problem. SICACT News 28, 81-87. Google Scholar
- TARJAN, R.E. 1975. Efficiency of a good but not linear set union algorithm. J. ACM 22, 2 (Apr.), 215-225. Google Scholar
- THORUP, M. 1996. On RAM priority queues. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 59-67. Google Scholar
- THORUP, M. 1998. Floats, integers, and single source shortest paths. In Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science. Lecture Notes on Computer Science, vol. 1373. Springer-Verlag, New York, pp. 14-24. Google Scholar
- VAN EMDE BOAS, P. 1977. Preserving order in a forest in less than logarithmic time and linear space. Inf. Proc. Lett. 6, 80-82.Google Scholar
- VAN EMDE BOAS, P., KAAS, R., AND ZIJLSTRA, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99-127.Google Scholar
- WILLARD, D. E. 1992. Applications of the fusion tree method to computational geometry and searching. In Proceedings of the 3rd Annual A CM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 386-395. Google Scholar
- WILLIAMS, J. W.J. 1964. Heapsort. Commun. ACM 7, 6 (June), 347-348.Google Scholar
Index Terms
- Undirected single-source shortest paths with positive integer weights in linear time
Recommendations
Single source shortest paths in H-minor free graphs
We present an algorithm for the Single Source Shortest Paths (SSSP) problem in directedH-minor free graphs. For every fixed H, if G is a graph with n vertices having integer edge lengths and s is a designated source vertex of G, the algorithm runs in O@?...
Non-crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
Computer Science – Theory and ApplicationsAbstractGiven a set of terminal pairs on the external face of an undirected unweighted planar graph, we give a linear-time algorithm for computing the union of non-crossing shortest paths joining each terminal pair, if such paths exist. This allows us to ...
Non-crossing shortest paths lengths in planar graphs in linear time
AbstractGiven a plane graph it is known how to compute the union of non-crossing shortest paths. These algorithms do not allow neither to list each single shortest path nor to compute length of shortest paths. Given the union of non-crossing shortest ...
Reviews
Pradip K. Srimani
One of the best-known problems in classical graph theory is the single-source shortest path problem for a graph whose edges are assigned nonnegative weights. An elegant solution of this problem was provided by Dijkstra in the late 1950s, and many algorithms have followed, all of which essentially follow Dijkstra's principle of visiting the nodes in order of increasing distance from the source vertex. No linear algorithm has been known for this problem, possibly because of the problem's inherent underpinning in sorting, which cannot be done in linear time. This paper, for the first time, proposes a linear-time and linear-space algorithm to solve this problem, albeit with the constraint that the edge weights in the given graph are all integers (linear-time algorithms had previously been known only for planar graphs). This result is predicated upon using multiplications in the algorithm, in addition to the usual AC 0 operations such as addition, shift, and Boolean operations; if multiplication is excluded, the algorithm runs in O a m , n m time, where n is the number of nodes, m is the number of edges, and a m,n is the inverse of the well-known Ackermann function. The results that lead to the final claim are elegant; they provide a lot of insights into many aspects of graph theory and arithmetic. The paper is mathematical in nature; the presentation is lucid, and relevant background and results are mentioned, but readers will need mathematical maturity to make sense of the finer points. The paper is a must-read for anybody interested in mathematical graph theory.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments