| Negative-Cycle Detection Algorithms (1996) | |||||||||||||||
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 author was visiting NEC Research Institute, Inc. 1 Introduction The negative cycle problem is the problem of finding a negative length cycle in a network or proving that there are none (see e.g. [15]). The problem is closely related to the shortest path problem (see e.g. [1, 7, 16, 18, 19, 20]) of finding shortest path distances in a netwo... | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||