×

The Floyd-Warshall algorithm on graphs with negative cycles. (English) Zbl 1197.05143

Summary: The Floyd-Warshall algorithm is a simple and widely used algorithm to compute shortest paths between all pairs of vertices in an edge weighted directed graph. It can also be used to detect the presence of negative cycles. We will show that for this task many existing implementations of the Floyd-Warshall algorithm will fail because exponentially large numbers can appear during its execution.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments

Software:

Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Chan, Timothy M., All-pairs shortest paths with real weights in \(O(n^3 / \log n)\) time, Algorithmica, 50, 236-243 (2008) · Zbl 1151.68043
[3] Floyd, Robert W., Algorithm 97: Shortest path, Communications of the ACM, 5, 6, 345 (1962)
[4] Fredman, Michael L., New bounds on the complexity of the shortest path problem, SIAM Journal on Computing, 5, 1, 83-89 (1976) · Zbl 0326.68027
[6] Han, Yijie, A note of an \(O(n^3 / \log n)\) time algorithm for all pairs shortest paths, Information Processing Letters, 105, 114-116 (2008) · Zbl 1184.68663
[7] Han, Yijie, An \(O(n^3(\log \log n / \log n)^{5 / 4})\) time algorithm for all pairs shortest paths, Algorithmica, 51, 428-434 (2008) · Zbl 1147.68092
[8] Korte, Bernhard; Vygen, Jens, Combinatorial Optimization: Theory and Algorithms (2008), Springer-Verlag: Springer-Verlag Berlin-Heidelberg · Zbl 1149.90126
[9] Pettie, Seth, A new approach to all-pairs shortest paths on real-weighted graphs, Theoretical Computer Science, 312, 47-74 (2004) · Zbl 1071.68084
[10] Reingold, Edward M.; Nievergelt, Jurg; Deo, Narsingh, Combinatorial Algorithms: Theory and Practice (1977), Prentice-Hall, Inc. · Zbl 0367.68032
[11] Takaoka, Tadao, A new upper bound on the complexity of the all pairs shortest path problem, Information Processing Letters, 43, 195-199 (1992) · Zbl 0763.68044
[12] Takaoka, Tadao, A faster algorithm for the all-pairs shortest path problem and its application, (Chwa, K.-Y.; Munro, J. I., COCOON 2004. COCOON 2004, Lecture Notes in Computer Science, vol. 3106 (2004), Springer-Verlag: Springer-Verlag Berlin-Heidelberg), 278-289 · Zbl 1091.68082
[13] Takaoka, Tadao, An \(O(n^3 \log \log n / \log n)\) time algorithm for the all-pairs shortest path problem, Information Processing Letters, 96, 155-161 (2005) · Zbl 1191.68473
[14] Weiss, Mark Allen, Data Structures and Algorithm Analysis (1995), The Benjamin/Cummings Publishing Company, Inc. · Zbl 0844.68023
[16] Zwick, Uri, A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths, Algorithmica, 46, 181-192 (2006) · Zbl 1101.68071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.