Donald B. Johnson
Abstract
Algorithms for finding shortest paths are presented which are faster than algorithms previously known on networks which are relatively sparse in arcs. Known results which the results of this paper extend are surveyed briefly and analyzed. A new implementation for priority queues is employed, and a class of “arc set partition” algorithms is introduced. For the single source problem on networks with nonnegative arcs a running time of O(min(n1+1/k + e, n + e) log n)) is achieved, where there are n nodes and e arcs, and k is a fixed integer satisfying k > 0. This bound is O(e) on dense networks. For the single source and all pairs problem on unrestricted networks the running time is O(min(n2+1/k + ne, n2 log n + ne log n).
- 1 AHO, A V , HOPCROFT, J E , AND ULLMAN, J D The Destgn and Analysts of Computer Algortthms Addison-Wesley, Reading, Mass , 1974 Google Scholar
- 2 BELLMAN, R E On a routing problem Quart Appl Math 16, 1 (1958), 87-90Google Scholar
- 3 BERGE, C Theorle des Graphs et Ses Apphcatlons Dunod, Pans, 1958Google Scholar
- 4 DANTZIG, G B On the shortest route through a network Manage Sct 6, 2 (1960), 187-190Google Scholar
- 5 DANa'ZIG, G B All shortest routes m a graph Proc Int Symp on Theory of Graphs (Rome, 1966), Gordon and Breach, New York, 1967, pp 91-92Google Scholar
- 6 DANTZIG, G B, BLAI"rNER, W O , AND RAO, M R All shortest routes from a fixed ongm in a graph Proc Int Symp on Theory of Graphs (Rome, 1966), Gordon and Breach, New York, 1967, pp 85-90Google Scholar
- 7 DIJKSTRA, E W A note on two problems m connexion with graphs. Numer Math 1 (1959), 269-271Google Scholar
- 8 DREYFUS, S E An appraisal of some shortest-path algorithms Operattons Res 17, 3 (May-June 1969), 395-412Google Scholar
- 9 EDMONDS, J , AND KARP, R M Theoretical ~mprovements m algorithmic effioency for network flow problems J ACM 19, 2 (April 1972), 248-264 Google Scholar
- 10 FLOYD, F W Algorithm 97~ shortest path Comm ACM 5, 6 (June 1962), 345 Google Scholar
- 11 FORD. L R JR, AND FULKERSON, D R Flows m Networks Princeton U Press, Prin~~eon, N J , 1962Google Scholar
- 12 FREDMAN, M L On the decision tree complexity of the shortest path problems Conf Rec 16th Annual IEEE Syrup on Foundations Comptr. Sc~, Oct 1975, 98-99Google Scholar
- 13 FREOMAN, M L New bounds on the complexity of the shortest path problem SIAM J Comput 5, 1 (March 1976), 83-89Google Scholar
- 14 HOFFMAN, A J , AND WINOGRAO, S Finding all shortest &stances In a directed network IBM J Res Devel. 16, 4 (July 1972), 412-414Google Scholar
- 15 Hu, T C, AND TORRES, W.T Shortcut in the decomposition algorithm for shortest paths m a network IBM J Res Devel 13, 4 (July 1969), 387-390Google Scholar
- 16 JOHNSON, D B Algorithms for shortest paths Tech Rep 73-169, Dep Comptr Sci, CorneU U, ithaca, N Y , May 1973, available as PB-220 872, NTIS, Springfield, VaGoogle Scholar
- 17 JOHNSON, D B A note on Dqkstra's shortest path algorithm J ACM 20, 3 (July 1973), 385-388 Google Scholar
- 18 JOHNSON, D B Priority queues with update and finding minimum spanning trees lnformatton Processmg Letters 4, 3 (Dec 1975), 53-57Google Scholar
- 19 JOHNSON, E L On shortest paths and sorting Proc ACM 25th Annual Conf, Aug 1972, pp 510-517 Google Scholar
- 20 KARP, R M Reduobdlty among combinatorial problems In Complexity of Computer Computattons,{ R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103Google Scholar
- 21 KNUTH, D E The Art of Computer Programming, Vol I Fundamental Algortthms Addison-Wesley, Reading, Mass , 1968 Google Scholar
- 22 KNUTH, D E The Art of Computer Programming, Vol 3 Sorting and Searching Addison-Wesley, Reading, Mass, 1973 Google Scholar
- 23 LAWLER, E L Combmatortal Opttmtzauon Networks and Matrotds Holt, Rinehart, and Winston, New York, I976Google Scholar
- 24 MOORE, E F. The shortest path through a maze Proc Int Symp. on Theory of Switching, Part II, April 2-5, 1957; Annals of the Computation Lab of Harvard Untverslty 30, Harvard U Press, Cambridge, Mass, 1959, pp 285-292Google Scholar
- 25 MOR~,VEK, J A note upon mlmmal path problem J Math Anal Appl 30 (1970), 702-717Google Scholar
- 26 NEMI-IAVSER, G L A generahzed permanent label setting algorithm for the shortest path between specified nodes J Math Anal Appl 38, 2 (May 1972), 328-334Google Scholar
- 27 NILSSON, N J. Problem-Solwng Methods m Arttfictal Intelhgence McGraw-Hall, New York, 1971 Google Scholar
- 28 PmRCE, A R Bibliography on algorithms for shortest path, shortest spanning tree and related circuit routing problems (1956-1974) Networks 5, 2 (Aprd 1975), 129-149Google Scholar
- 29 WAGNER, R A A shortest path algorithm for edge-sparse graphs J ACM 23, 1 (Jan 1976), 50-57 Google Scholar
- 30 WARSnALL, S A theorem on Boolean matrices J ACM 9, 1 (Jan 1962), 11-12 Google Scholar
- 31 YEN, J Y A shortest path algorithm Ph.D Th , U of California, Berkeley, Cahf, 1970.Google Scholar
- 32 YEN, J Y An a|gonthm for finding shortest routes from all source nodes to a given destination m general networks Quart Appl Math 27, 4 (Jan 1970), 526-530Google Scholar
- 33 YEN, J Y Fmdlng the lengths of all shortest paths in N-node nonnegatlve-&stance complete networks using ~ N3 additions and N3 comparisons J A CM 19, 3 (July 1972), 423-424 Google Scholar
Index Terms
- Efficient Algorithms for Shortest Paths in Sparse Networks
Recommendations
Distributed approximation algorithms for weighted shortest paths
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computingA distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n) bandwidth restriction on edges (the ...
Computing almost shortest paths
We study the <i>s-sources almost shortest paths</i> (abbreviated <i>s-ASP</i>) problem. Given an unweighted graph <i>G</i> = (<i>V,E</i>), and a subset <i>S</i> ⊆ <i>V</i> of <i>s</i> nodes, the goal is to compute almost shortest paths between ...
Comments