skip to main content
research-article

Shortest-path feasibility algorithms: An experimental evaluation

Published: 05 January 2010 Publication History

Abstract

This is an experimental study of algorithms for the shortest-path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including new algorithms) has very robust performance in practice. Our work advances the state of the art in the area.

References

[1]
Bellman, R. E. 1958. On a routing problem. Quart. Appl. Math. 16, 87--90.
[2]
Chandrachoodan, N., Battacharyya, S. S., and Liu, K. J. R. 2001. Adaptive negative-cycle detection in dynamic graphs. In Proceedings of International Symposium on Circuits and Systems (ISCAS). IEEE, Los Alamitos, CA, 163--166.
[3]
Cherkassky, B., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., and Werneck, R. F. 2008. Shortest-path feasibility algorithms: An experimental evaluation. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, Philadelphia, 118--132.
[4]
Cherkassky, B. V. and Goldberg, A. V. 1999. Negative-cycle detection algorithms. Math. Prog. 85, 277--311.
[5]
Cherkassky, B. V., Goldberg, A. V., and Radzik, T. 1996. Shortest-Paths Algorithms: Theory and Experimental Evaluation. Math. Prog. 73, 129--174.
[6]
Dasdan, A. 2004. Experimental Analysis of the Fastest Optimum Cycle Ratio and Mean Algorithms. ACM Trans. Des. Autom. Electron. Syst. 9, 4, 385--418.
[7]
Dechter, R., Meiri, I., and Pearl, J. 1991. Temporal Constraint Networks. Artif. Intell. 49, 61--95.
[8]
Demetrescu, C., Goldberg, A., and Johnson, D. 2007. 9th DIMACS Implementation Challenge: Shortest-Paths. http://www.dis.uniroma1.it/~challenge9/.
[9]
Denardo, E. V. and Fox, B. L. 1979. Shortest--Route Methods: 1. Reaching, pruning, and buckets. Oper. Res. 27, 161--186.
[10]
Dial, R. B., Glover, F., Karney, D., and Klingman, D. 1979. A computational analysis of alternative algorithms and labeling techniques for finding shortest-path trees. Networks 9, 215--248.
[11]
Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numer. Math. 1, 269--271.
[12]
Ford, Jr., L. 1956. Network Flow Theory. Tech. rep. P-932, The Rand Corporation.
[13]
Ford, Jr., L. and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press, Princeton, NJ.
[14]
Fredman, M. L. and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach. 34, 596--615.
[15]
Gallo, G. and Pallottino, S. 1988. Shortest-paths algorithms. Annals of Oper. Res. 13, 3--79.
[16]
Georgiadis, L., Goldberg, A. V., Tarjan, R. E., and Werneck, R. F. 2009. An experimental study of minimum mean cycle algorithms. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, Philadelphia, 1--13.
[17]
Goldberg, A. V. 1995. Scaling algorithms for the shortest-paths problem. SIAM J. Comput. 24, 494--504.
[18]
Goldberg, A. V. and Radzik, T. 1993. A heuristic improvement of the Bellman-Ford algorithm. Applied Math. Let. 6, 3--6.
[19]
Held, S., Korte, B., Massberg, J., Ringe, M., and Vygen, J. 2003. Clock scheduling and clocktree construction for high performance ASICs. In Proceedins IEEE/ACM International Conference on CAD (ICCAD'03). 232--239.
[20]
Kennington, J. L. and Helgason, R. V. 1980. Algorithms for Network Programming. John Wiley and Sons, New York.
[21]
Kolliopoulos, S. and Stein, C. 1996. Finding real-valued single-source shortest-paths in o(n<sup>3</sup>) expected time. In Proceedings of the 5th International Programming and Combinatorial Optimization Conference.
[22]
Moore, E. F. 1959. The Shortest-Path Through a Maze. In Proceedings of the International Symposium on the Theory of Switching. Harvard University Press, 285--292.
[23]
Nonato, M., Pallottino, S., and Xuewen, B. 1999. SPT_L Shortest-Path Algorithms: Reviews, New Proposals, and Some Experimental Results. Tech. rep. TR-99-16, Dipartmento di Informatica, Pisa University, Italy.
[24]
Pallottino, S. 1984. Shortest-path methods: Complexity, interrelations and new propositions. Networks 14, 257--267.
[25]
Pape, U. 1974. Implementation and efficiency of Moore algorithms for the shortest-root problem. Math. Prog. 7, 212--222.
[26]
Tarjan, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 146--160.
[27]
Tarjan, R. E. 1981. Shortest-Paths. Tech. rep., AT&T Bell Laboratories, Murray Hill, NJ.
[28]
Tarjan, R. E. 1983. Data Structures and Network Algorithms. SIAM, Philadelphia.
[29]
Tseitin, G. 1970. On the Complexity of Derivation in Propositional Calculus. In Studies in Constructive Mathematics and Mathematical Logic. 115--125.
[30]
Wong, C.-H. and Tam, Y.-C. 2005. Negative-cycle detection problem. In Proceedings of the 13th Annual European Symposium on Algorithms. Springer, Berlin, 652--663.

Cited By

View all
  • (2019)Vehicle Routing with Transportable Resources: Using Carpooling and Walking for On-Site ServicesEuropean Journal of Operational Research10.1016/j.ejor.2019.06.039Online publication date: Jun-2019
  • (2019)Route feasibility testing and forward time slack for the Synchronized Pickup and Delivery ProblemOR Spectrum10.1007/s00291-018-0544-041:2(491-512)Online publication date: 25-May-2019
  • (2018)A new algorithm for the shortest‐path problemNetworks10.1002/net.2187074:1(16-39)Online publication date: 21-Dec-2018
  • Show More Cited By

Index Terms

  1. Shortest-path feasibility algorithms: An experimental evaluation

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Journal of Experimental Algorithmics
    ACM Journal of Experimental Algorithmics  Volume 14, Issue
    2009
    613 pages
    ISSN:1084-6654
    EISSN:1084-6654
    DOI:10.1145/1498698
    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: 05 January 2010
    Accepted: 01 March 2009
    Received: 01 March 2009
    Published in JEA Volume 14

    Author Tags

    1. Shortest paths
    2. feasibility
    3. negative cycles

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)32
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Vehicle Routing with Transportable Resources: Using Carpooling and Walking for On-Site ServicesEuropean Journal of Operational Research10.1016/j.ejor.2019.06.039Online publication date: Jun-2019
    • (2019)Route feasibility testing and forward time slack for the Synchronized Pickup and Delivery ProblemOR Spectrum10.1007/s00291-018-0544-041:2(491-512)Online publication date: 25-May-2019
    • (2018)A new algorithm for the shortest‐path problemNetworks10.1002/net.2187074:1(16-39)Online publication date: 21-Dec-2018
    • (2014)The Dial-A-Ride Problem with TransfersComputers and Operations Research10.1016/j.cor.2013.07.02041(12-23)Online publication date: 1-Jan-2014
    • (2013)Label constrained shortest path estimationProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2507818(1177-1180)Online publication date: 27-Oct-2013
    • (2013)Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedraACM SIGPLAN Notices10.1145/2480359.242912748:1(483-496)Online publication date: 23-Jan-2013
    • (2013)Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedraProceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2429069.2429127(483-496)Online publication date: 23-Jan-2013
    • (2012)Efficiently Eliminate Temporal Conflicts in Operation Plan2012 Second International Conference on Intelligent System Design and Engineering Application10.1109/ISdea.2012.628(817-820)Online publication date: Jan-2012
    • (undefined)Temporal Constraint Modeling and Conflict Resolving Based on the Combat Process of Air and Missile Defense System*2019 IEEE International Conference on Systems, Man and Cybernetics (SMC)10.1109/SMC.2019.8914484(2684-2689)

    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