Cherkassky, Boris V.; Goldberg, Andrew V. Negative-cycle detection algorithms. (English) Zbl 0954.90057 Math. Program. 85, No. 2 (A), 277-311 (1999). Summary: 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 survey cycle detection strategies, study various combinations of shorest 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 computational 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. Cited in 24 Documents MSC: 90C35 Programming involving graphs or networks 65K05 Numerical mathematical programming methods Keywords:algorithms; graph theory; computational evaluation; shortest paths; negative-length cycles PDFBibTeX XMLCite \textit{B. V. Cherkassky} and \textit{A. V. Goldberg}, Math. Program. 85, No. 2 (A), 277--311 (1999; Zbl 0954.90057) Full Text: DOI