2-C-6 Negative cycle detection by a Dijkstra-based algorithm

概要

論文の詳細を見る
Nakayama and Anazawa [1] proposed three algorithms for finding a shortest path from a source to each vertex in a network with edges of negative length. Each of them has the same complexity O(n_0S(m, n)), where no is the number of vertices incident to edges of negative length, and S(m, n) is the complexity of Dijkstra's method for an underlying graph with m edges and n vertices. In [1], input networks are assumed to have no negative cycles (i.e. to be conservative). We propose in this paper a revised version of a Dijkstra-based algorithm which can detect a negative cycle in any input network without conservativeness. The revised algorithm also runs in O(n_0S(m, n)) time.
2012-09-12