Abstract
We study the problem of finding a negative length cycle in a network. An algorithm for the negative cycle problem combines a shortest path algorithm and a cycle detection strategy. We study various combinations of shortest path algorithms and cycle detection strategies and find the best combinations. One of our discoveries is that a cycle detection strategy of Tarjan greatly improves practical performance of a classical shortest path algorithm, making it competitive with the fastest known algorithms on a wide range of problems. As a part of our study, we develop problem families for testing negative cycle algorithms.
This work was done while the first author was visiting NEC Research Institute, Inc.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. E. Bellman. On a Routing Problem. Quart. Appl. Math., 16:87–90, 1958.
B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest Paths Algorithms: Theory and Experimental Evaluation. In Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, pages 516–525, 1994. To appear in Math. Prog.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990.
G. B. Dantzig. Application of the Simplex Method to a Transportation Problem. In T. C. Koopmans, editor, Activity Analysis and Production and Allocation, pages 359–373. Wiley, New York, 1951.
E. V. Denardo and B. L. Fox. Shortest-Route Methods: 1. Reaching, Pruning, and Buckets. Oper. Res., 27:161–186, 1979.
R. B. Dial, F. Glover, D. Karney, and D. Klingman. A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees. Networks, 9:215–248, 1979.
L. Ford. Network Flow Theory. Technical Report P-932, The Rand Corporation, 1956.
L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962.
G. Gallo and S. Pallottino. Shortest Paths Algorithms. Annals of Oper. Res., 13:3–79, 1988.
F. Glover, R. Glover, and D. Klingman. Computational Study of an Improved Shortest Path Algorithm. Networks, 14:25–37, 1984.
F. Glover, D. Klingman, and N. Phillips. A New Polynomially Bounded Shortest Paths Algorithm. Oper. Res., 33:65–73, 1985.
A. V. Goldberg. Scaling Algorithms for the Shortest Paths Problem. SIAM J. Comput., 24:494–504, 1995.
A. V. Goldberg and T. Radzik. A Heuristic Improvement of the Bellman-Ford Algorithm. Applied Math. Let., 6:3–6, 1993.
M. S. Hung and J. J. Divoky. A Computational Study of Efficinet Shotest Path Algorithms. Comput. Ops. Res., 15:567–576, 1988.
J. L. Kennington and R. V. Helgason. Algorithms for Network Programming. John Wiley and Sons, 1980.
M. Klein. A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. Management Science, 14:205–220, 1967.
S.G. Kolliopoulos and C. Stein. Finding Real-Valued Single-Source Shortest Paths in o(n 3) Expected Time. In Proc. 5th Int. Programming and Combinatorial Optimization Conf., 1996.
E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York, NY, 1976.
B. Ju. Levit and B. N. Livshits. Nelineinye Setevye Transportnye Zadachi. Transport, Moscow, 1972. In Russian.
J-F. Mondou, T.G. Crainic, and S. Nguyen. Shortest Path Algorithms: A Computational Study with the C Progremming Language. Computers and Oper. Res., 18:767–786, 1991.
E. F. Moore. The Shortest Path Through a Maze. In Proc. of the Int. Symp. on the Theory of Switching, pages 285–292. Harvard University Press, 1959.
S. Pallottino. Shortest-Path Methods: Complexity, Interrelations and New Propositions. Networks, 14:257–267, 1984.
U. Pape. Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem. Math. Prog., 7:212–222, 1974.
P. Spirakis and A. Tsakadidis. A Very Fast, Practical Algorithm for Finding a Negative Cycle in a Digraph. In Proc. 13th ICALP, Lecture Notes in Computer Science 226, pages 59–67. Springer-Verlag, 1996.
R. E. Tarjan. Shortest Paths. Technical report, AT&T Bell Laboratories, Murray Hill, NJ, 1981.
R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cherkassky, B.V., Goldberg, A.V. (1996). Negative-cycle detection algorithms. In: Diaz, J., Serna, M. (eds) Algorithms — ESA '96. ESA 1996. Lecture Notes in Computer Science, vol 1136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61680-2_67
Download citation
DOI: https://doi.org/10.1007/3-540-61680-2_67
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61680-1
Online ISBN: 978-3-540-70667-0
eBook Packages: Springer Book Archive