The Floyd-Warshall algorithm on graphs with negative cycles

作者：Hougardy Stefan^*

来源：Information Processing Letters, 2010, 110(8-9): 279-281.

DOI：10.1016/j.ipl.2010.02.001

• Floyd-Warshall algorithm
• Design of algorithms
• Graph algorithms

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.

• 出版日期2010-4-1