skip to main content
article

Finding the k shortest simple paths: A new algorithm and its implementation

Published: 01 November 2007 Publication History

Abstract

We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed by Hershberger and Suri [2001], and can yield a factor Θ(n) improvement for this problem. But there is a caveat: The fast replacement paths subroutine is known to fail for some directed graphs. However, the failure is easily detected, and so our k shortest paths algorithm optimistically uses the fast subroutine, then switches to a slower but correct algorithm if a failure is detected. Thus, the algorithm achieves its Θ(n) speed advantage only when the optimism is justified. Our empirical results show that the replacement paths failure is a rare phenomenon, and the new algorithm outperforms the current best algorithms; the improvement can be substantial in large graphs. For instance, on GIS map data with about 5,000 nodes and 12,000 edges, our algorithm is 4--8 times faster. In synthetic graphs modeling wireless ad hoc networks, our algorithm is about 20 times faster.

References

[1]
Brander, A., and Sinclair, M. 1995. A comparative study of K-shortest path algorithms. In Proceedings of 11th UK Performance Engineering Workshop, 370--379.
[2]
Dial, R., Glover, F., Karney, D., and Klingman, D. 1979. A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Netw. 9, 3, 215--248.
[3]
Eppstein, D. 1998. Finding the k shortest paths. SIAM J. Comput. 28, 2, 652--673.
[4]
Fox, B. L. 1975. k-th shortest paths and applications to the probabilistic networks. In Proceedings of the ORSA/TIMS Joint National Meeting 23, B263.
[5]
Fredman, M. 1976. New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5, 83--89.
[6]
Fredman, M., and Tarjan, R. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596--615.
[7]
Hadjiconstantinou, E., and Christofides, N. 1999. An efficient implementation of an algorithm for finding K shortest simple paths. Netw. 34, 2, 88--101.
[8]
Hershberger, J., and Suri, S. 2001. Vickrey prices and shortest paths: What is an edge worth? In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 252--259.
[9]
Hershberger, J., and Suri, S. 2002. Erratum to “Vickrey prices and shortest paths: What is an edge worth?”. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 809.
[10]
Hershberger, J., Suri, S., and Bhosle, A. 2007. On the difficulty of some shortest path problems. ACM Trans. Alg. 3, 1, Article 5. http://doi.acm.org/10.1145/1219944.1219951.
[11]
Hoffman, W., and Pavley, R. 1959. A method for the solution of the Nth best path problem. J. ACM 6, 506--514.
[12]
Jiménez, V. M., and Marzal, A. 2003. A lazy version of Eppstein's K shortest paths algorithm. In Proceedings of the 2nd International Workshop on Experimental and Efficient Algorithms (WEA). Lecture Notes in Computer Science, vol. 2647. Springer, 179--190.
[13]
Katoh, N., Ibaraki, T., and Mine, H. 1982. An efficient algorithm for k shortest simple paths. Netw. 12, 411--427.
[14]
Lawler, E. L. 1972. A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Manag. Sci. 18, 401--405.
[15]
Malik, K., Mittal, A. K., and Gupta, S. K. 1989. The k most vital arcs in the shortest path problem. Oper. Res. Lett. 8, 223--227.
[16]
Martins, E., and Pascoal, M. 2003. A new implementation of Yen's ranking loopless paths algorithm. 4OR Quart. J. Belgian, French, Italian Oper. Res. Soc. 1, 2, 121--134.
[17]
Martins, E., Pascoal, M., and Santos, J. 1997. A new algorithm for ranking loopless paths. Tech. Rep. Universidade de Coimbra, Portugal.
[18]
Perko, A. 1986. Implementation of algorithms for K shortest loopless paths. Netw. 16, 149--160.
[19]
Pollack, M. 1961. The kth best route through a network. Oper. Res. 9, 578.
[20]
Seidel, R. 1995. On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Comput. Syst. Sci. 51, 3, 400--403.
[21]
Yen, J. Y. 1971. Finding the K shortest loopless paths in a network. Manag. Sci. 17, 712--716.
[22]
Yen, J. Y. 1972. Another algorithm for finding the K shortest loopless network paths. In Proceedings of the 41st Meeting of the Operations Research Society of America, vol. 20.
[23]
Zwick, U. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49, 3, 289--317.

Cited By

View all
  • (2024)Improving the Relevance, Speed, and Computational Efficiency of Semantic Search through Database Indexing: A ReviewOptimization Algorithms - Classics and Recent Advances10.5772/intechopen.112232Online publication date: 10-Jul-2024
  • (2024)Derivation of Recovery Operations under Cyber Attack based on Finite Automata and Path Finding有限オートマトンと経路探索に基づくサイバー攻撃発生時の回復動作の導出Transactions of the Institute of Systems, Control and Information Engineers10.5687/iscie.37.10937:4(109-118)Online publication date: 15-Apr-2024
  • (2024)Label-Setting Algorithm for Multi-Destination K Simple Shortest Paths Problem and ApplicationAlgorithms10.3390/a1708032517:8(325)Online publication date: 25-Jul-2024
  • Show More Cited By

Index Terms

  1. Finding the k shortest simple paths: A new algorithm and its implementation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Algorithms
    ACM Transactions on Algorithms  Volume 3, Issue 4
    November 2007
    293 pages
    ISSN:1549-6325
    EISSN:1549-6333
    DOI:10.1145/1290672
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 November 2007
    Published in TALG Volume 3, Issue 4

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Loop-free paths
    2. directed paths
    3. path equivalence class
    4. replacement paths

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)108
    • Downloads (Last 6 weeks)7
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Improving the Relevance, Speed, and Computational Efficiency of Semantic Search through Database Indexing: A ReviewOptimization Algorithms - Classics and Recent Advances10.5772/intechopen.112232Online publication date: 10-Jul-2024
    • (2024)Derivation of Recovery Operations under Cyber Attack based on Finite Automata and Path Finding有限オートマトンと経路探索に基づくサイバー攻撃発生時の回復動作の導出Transactions of the Institute of Systems, Control and Information Engineers10.5687/iscie.37.10937:4(109-118)Online publication date: 15-Apr-2024
    • (2024)Label-Setting Algorithm for Multi-Destination K Simple Shortest Paths Problem and ApplicationAlgorithms10.3390/a1708032517:8(325)Online publication date: 25-Jul-2024
    • (2024) A Distributed Solution for Efficient K Shortest Paths Computation Over Dynamic Road Networks IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3346377(1-14)Online publication date: 2024
    • (2024)AI-Based QoS Optimization in Post-Disaster Ad Hoc Networks: Top-K Path Enumeration with Multicriteria Decision Analysis2024 IEEE 4th International Maghreb Meeting of the Conference on Sciences and Techniques of Automatic Control and Computer Engineering (MI-STA)10.1109/MI-STA61267.2024.10599698(561-566)Online publication date: 19-May-2024
    • (2024)Energy-Efficient Online Service Migration in Edge NetworksIEEE Internet of Things Journal10.1109/JIOT.2024.340670111:18(29689-29708)Online publication date: 15-Sep-2024
    • (2024)Shortest path counting in complex networks based on powers of the adjacency matrixChaos: An Interdisciplinary Journal of Nonlinear Science10.1063/5.022614434:10Online publication date: 21-Oct-2024
    • (2024)A novel data driven anticipatory framework for the communicable syndromeEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.107929132(107929)Online publication date: Jun-2024
    • (2024)Finding the $$\mathrm{K}$$ Mean-Standard Deviation Shortest Paths Under Travel Time UncertaintyNetworks and Spatial Economics10.1007/s11067-024-09618-224:2(395-423)Online publication date: 8-Mar-2024
    • (2023)Algorithm for finding subcritical paths on network diagramsRussian Technological Journal10.32362/2500-316X-2023-11-1-60-6911:1(60-69)Online publication date: 3-Feb-2023
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media