Floyd-Warshall Algorithm: Difference between revisions
Jump to navigation
Jump to search
| (5 intermediate revisions by the same user not shown) | |||
| Line 10: | Line 10: | ||
* [[Johnson's Algorithm]] | * [[Johnson's Algorithm]] | ||
=Overview= | =Overview= | ||
The Floyd-Warshall algorithm computes all-pairs shortest path in a directed graph with arbitrary edge length, include negative lengths. The only case that does not make sense is whether the graph has negative | The Floyd-Warshall algorithm computes all-pairs shortest path in a directed graph with arbitrary edge length, include negative lengths. The only case that does not make sense is whether the graph has negative cost cycles. In this case there is no shortest path, because the cycle can be followed an infinite number of times, leading to negative infinity length paths. If this is the case, the Floyd-Warshall will detect the situation in its final result, by scanning the diagonal of the matrix it computes. | ||
The running time is O(n<sup>3</sup>). | The running time is O(n<sup>3</sup>). | ||
| Line 21: | Line 21: | ||
│ 0 if i == j | │ 0 if i == j | ||
for all i,j ∈ V, A[i,j,0] = │ c<sub>ij</sub> if (i, j) ∈ E | for all i,j ∈ V, A[i,j,0] = │ c<sub>ij</sub> if i≠j and (i, j) ∈ E | ||
│ +∞ if i≠j and (i,j) ∉ E | │ +∞ if i≠j and (i,j) ∉ E | ||
| Line 31: | Line 31: | ||
</font> | </font> | ||
If the graph has a negative cost cycle. | If the graph has a negative cost cycle, the diagonal of the matrix A[i,i,n] < 0 for at least one i ∈ V, at the end of the algorithm. | ||
==Playground Implementation== | |||
{{External|https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/16-all-points-shortest-paths/src/main/java/playground/standford/apsp/FloydWarshallAlgorithm.java}} | |||
Latest revision as of 02:54, 25 November 2021
External
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/VQStd/problem-definition
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/3BBkw/optimal-substructure
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/WKb60/the-floyd-warshall-algorithm
Internal
- All-Pairs Shortest Path Algorithms
- Dynamic Programming
- Bellman-Ford Shortest-Path Algorithm
- Johnson's Algorithm
Overview
The Floyd-Warshall algorithm computes all-pairs shortest path in a directed graph with arbitrary edge length, include negative lengths. The only case that does not make sense is whether the graph has negative cost cycles. In this case there is no shortest path, because the cycle can be followed an infinite number of times, leading to negative infinity length paths. If this is the case, the Floyd-Warshall will detect the situation in its final result, by scanning the diagonal of the matrix it computes.
The running time is O(n3).
Algorithm
We assume that the vertices are labeled from 1 to n.
Let A = 3D array, indexed by i, j, k
# Initialize the tridimensional matrix with the trivial cases
│ 0 if i == j
for all i,j ∈ V, A[i,j,0] = │ cij if i≠j and (i, j) ∈ E
│ +∞ if i≠j and (i,j) ∉ E
for k = 1 to n:
for i = 1 to n:
for j = 1 to n:
A[i,j,k] = max(A[i,j,k-1], A[i,k,k-1] + A[k,j,k-1])
If the graph has a negative cost cycle, the diagonal of the matrix A[i,i,n] < 0 for at least one i ∈ V, at the end of the algorithm.