More Web Proxy on the site http://driver.im/

article

Free access

Efficient Algorithms for Shortest Paths in Sparse Networks

Author:

Donald B. JohnsonAuthors Info & Claims

Journal of the ACM (JACM), Volume 24, Issue 1

Pages 1 - 13

https://doi.org/10.1145/321992.321993

Published: 01 January 1977 Publication History

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(n^1+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(n^2+1/k + ne, n² log n + ne log n).

References

[1]

AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Destgn and Analysts of Computer Algortthms Addison-Wesley, Reading, Mass, 1974

[2]

BELLMAN, R E On a routing problem Quart Appl Math 16, 1 (1958), 87-90

[3]

BERGE, C Theorle des Graphs et Ses Apphcatlons Dunod, Pans, 1958

[4]

DANTZIG, G B On the shortest route through a network Manage Sct 6, 2 (1960), 187-190

[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-92

[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-90

[7]

DIJKSTRA, E W A note on two problems m connexion with graphs. Numer Math 1 (1959), 269-271

[8]

DREYFUS, S E An appraisal of some shortest-path algorithms Operattons Res 17, 3 (May-June 1969), 395-412

[9]

EDMONDS, J, AND KARP, R M Theoretical ~mprovements m algorithmic effioency for network flow problems J ACM 19, 2 (April 1972), 248-264

[10]

FLOYD, F W Algorithm 97~ shortest path Comm ACM 5, 6 (June 1962), 345

[11]

FORD. L R JR, AND FULKERSON, D R Flows m Networks Princeton U Press, Prin~~eon, N J, 1962

[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-99

[13]

FREOMAN, M L New bounds on the complexity of the shortest path problem SIAM J Comput 5, 1 (March 1976), 83-89

[14]

HOFFMAN, A J, AND WINOGRAO, S Finding all shortest &stances In a directed network IBM J Res Devel. 16, 4 (July 1972), 412-414

[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-390

[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, Va

[17]

JOHNSON, D B A note on Dqkstra's shortest path algorithm J ACM 20, 3 (July 1973), 385-388

[18]

JOHNSON, D B Priority queues with update and finding minimum spanning trees lnformatton Processmg Letters 4, 3 (Dec 1975), 53-57

[19]

JOHNSON, E L On shortest paths and sorting Proc ACM 25th Annual Conf, Aug 1972, pp 510-517

[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-103

[21]

KNUTH, D E The Art of Computer Programming, Vol I Fundamental Algortthms Addison-Wesley, Reading, Mass, 1968

[22]

KNUTH, D E The Art of Computer Programming, Vol 3 Sorting and Searching Addison-Wesley, Reading, Mass, 1973

[23]

LAWLER, E L Combmatortal Opttmtzauon Networks and Matrotds Holt, Rinehart, and Winston, New York, I976

[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-292

[25]

MOR~,VEK, J A note upon mlmmal path problem J Math Anal Appl 30 (1970), 702-717

[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-334

[27]

NILSSON, N J. Problem-Solwng Methods m Arttfictal Intelhgence McGraw-Hall, New York, 1971

[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-149

[29]

WAGNER, R A A shortest path algorithm for edge-sparse graphs J ACM 23, 1 (Jan 1976), 50-57

[30]

WARSnALL, S A theorem on Boolean matrices J ACM 9, 1 (Jan 1962), 11-12

[31]

YEN, J Y A shortest path algorithm Ph.D Th, U of California, Berkeley, Cahf, 1970.

[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-530

[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

Cited By

Irastorza-Valera LBenítez JMontáns FSaucedo-Mora L(2024)An Agent-Based Model to Reproduce the Boolean Logic Behaviour of Neuronal Self-Organised Communities through Pulse Delay Modulation and Generation of Logic GatesBiomimetics10.3390/biomimetics90201019:2(101)Online publication date: 9-Feb-2024
https://doi.org/10.3390/biomimetics9020101
Lin N(2024)Improving Talent Management: Army Officer Assignment System RecommendationsSSRN Electronic Journal10.2139/ssrn.4924877Online publication date: 2024
https://doi.org/10.2139/ssrn.4924877
Prihozhy AKarasik O(2024)New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes«System analysis and applied information science»10.21122/2309-4923-2023-4-4-13(4-13)Online publication date: 12-Jan-2024
https://doi.org/10.21122/2309-4923-2023-4-4-13
Show More Cited By

Index Terms

Efficient Algorithms for Shortest Paths in Sparse Networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Network flows
      2. Paths and connectivity problems
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Distributed approximation algorithms for weighted shortest paths
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

A 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,
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> &sube; <i>V</i> of <i>s</i> nodes, the goal is to compute almost shortest paths between ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 24, Issue 1

Jan. 1977

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321992

Issue’s Table of Contents

Copyright © 1977 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1977

Published in JACM Volume 24, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

776
Total Citations
View Citations
4,733
Total Downloads

Downloads (Last 12 months)608
Downloads (Last 6 weeks)105

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Irastorza-Valera LBenítez JMontáns FSaucedo-Mora L(2024)An Agent-Based Model to Reproduce the Boolean Logic Behaviour of Neuronal Self-Organised Communities through Pulse Delay Modulation and Generation of Logic GatesBiomimetics10.3390/biomimetics90201019:2(101)Online publication date: 9-Feb-2024
https://doi.org/10.3390/biomimetics9020101
Lin N(2024)Improving Talent Management: Army Officer Assignment System RecommendationsSSRN Electronic Journal10.2139/ssrn.4924877Online publication date: 2024
https://doi.org/10.2139/ssrn.4924877
Prihozhy AKarasik O(2024)New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes«System analysis and applied information science»10.21122/2309-4923-2023-4-4-13(4-13)Online publication date: 12-Jan-2024
https://doi.org/10.21122/2309-4923-2023-4-4-13
Khan AMatskin MProdan RBussler CRoman DSoylu A(2024)Cost modelling and optimisation for cloud: a graph-based approachJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-024-00709-613:1Online publication date: 30-Sep-2024
https://dl.acm.org/doi/10.1186/s13677-024-00709-6
Gu HZheng SLiu XXie HLui J(2024)Online Incentive Protocol Design for Reposting Service in Online Social NetworksACM Transactions on the Web10.1145/3696473Online publication date: 19-Sep-2024
https://dl.acm.org/doi/10.1145/3696473
Panagiotakis CDaskalaki EPapadakis HFragopoulou P(2024)An Expectation-Maximization framework for Personalized Itinerary Recommendation with POI Categories and Must-see POIsACM Transactions on Recommender Systems10.1145/36961143:1(1-33)Online publication date: 16-Sep-2024
https://dl.acm.org/doi/10.1145/3696114
Fahmin ACheema MEunus Ali MNadjaran Toosi ALu HLi HTaniar DA. Rakha HShen B(2024)Eco-Friendly Route Planning Algorithms: Taxonomies, Literature Review and Future DirectionsACM Computing Surveys10.1145/369162457:1(1-42)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3691624
Li NZhang MLi JAdepu SKang EJin Z(2024)A Game-Theoretical Self-Adaptation Framework for Securing Software-Intensive SystemsACM Transactions on Autonomous and Adaptive Systems10.1145/365294919:2(1-49)Online publication date: 20-Apr-2024
https://dl.acm.org/doi/10.1145/3652949
Feng YWang HZhu YLiu XLu HLiu Q(2024)DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted GraphsProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656600(1-13)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656600
Mao XMohar BShinkar IO'Donnell R(2024)Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649695(1141-1152)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649695
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents