Floyd Warshall Algorithm
The Floyd–Warshall algorithm also known as WFI algorithm is an algorithm used for finding the shortest paths in a directed weighted graph with both positive and negative edge weights but without negative cycles. By the execution of algorithm we can find the lengths of the shortest paths between all pairs of vertices. Although through execution of algorithm we can find the length i.e summed weight but it does not return details of the paths themselves, Although it is possible to reconstruct the paths with simple modifications to the algorithm.
Versions of Floyd’s algorithm can also be used for finding the transitive closure of a relation or for finding the widest paths between all pairs of vertices in a weighted graph.
History and naming
The Floyd-Warshall algorithm is an example of dynamic programming, and was published in its currently recognized from by Robert Floyd in 1962. However it is essentially the same as algorithms previously published by Bernard Roy in 1959 and also by Stephen Warshall in 1962 for finding the transitive closure of a graph and is closely related to Kleene’s algorithm.
The modern formulation of the algorithm as three nested for-loops was first described by Peter Ingerman, in 1962.
Algorithm
For finding the shortest path the Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with time complexity of 0(n³),
No matter how many edges are in the graph every combination edge is tested. It does it by improving an estimate on the shortest path between two vertices, until the estimate is optimal.
Consider a graph G with V vertices numbered from 1 to N. Further consider a function shortest path(i,j,k) that returns the shortest possible path from i to j using vertices only from the set {1,2,3,…..,k} as intermediate points along the way. Now, given this function our goal is to find the shortest path from each i to each j using any vertex in {1,2,3…..N}
For each of these pairs of vertices, the shortest Path(i,j,k) could be either
1. a path that does not go through k (only uses vertices in the set {1,2,3….,k-1})
2. a path that does go through k (from i to k and then from k to j, both only using intermediate vertices in {1,2,3….,k-1})
We know that the best path from i to j that only uses vertices 1 through k-1 is defined by shortest path(i,j,k-1) and it is clear that if there was a better path from i to k to j then the length of this path would be the concatenation of the shortest path from i to k (only using intermediate vertices in {1,…….,k-1}) and the shortest path from k to j using intermediate vertices.
If w (i,j) is the weight of the edge between vertices i and j, we can define shortestpath (i,j,k) in terms of the following recursive formula the base case is
Shortestpath (i,j,0) = w(i,j)
and the recursive case is
shortestPath(i,j,k)= min(shortestpath(i,j,k-1), shortestpath(i,k,k-1) + shortestpath(k,j,k-1))
This formula is the heart of the Floyd–Warshall algorithm. The algorithm works by first computing shortest path (i,j,k) for all (i,j) pairs for k=1 then k=2 and so on. This process continues until k=N and we have found the shortest path for all (i,j) pairs using intermediate vertices.
The Pseudocode for this basic version follows
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
dist[u][v] ← w(u, v) // The weight of the edge (u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
Behavior with negative cycles
A negative cycle is a cycle whose edges sum to a negative value. There is no shortest path between any pair of vertices i,j which form part of a negative cycle, because path-lengths from
i to j can be arbitrarily small. For numerically meaningful output, the Floyd–Warshall algorithm assumes that there are no negative cycles. Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them. The intuition is as follows:
1. The Floyd–Warshall algorithm iteratively revises path lengths between all pairs of vertices (i,j) including where i = j;
- Initially, the length of the path (i,j) is zero;
3. A path [i,k,……,i] can only improve upon this if it has length less than zero, i.e. denotes a negative cycle;
4. Thus, after the algorithm, (i,j) will be negative if there exists a negative length path from I back to i
Hence to detect negative cycles using the Floyd–Warshall algorithm, one can inspect the diagonal of the path matrix, and the presence of a negative number indicates that the graph contains at least one negative cycle. During the execution of the algorithm, if there is a negative cycle, exponentially large numbers can appear. To avoid overflow and underflow problems one should check for negative numbers on the diagonal of the path matrix within the inner for loop of the algorithm.
Path reconstruction
The Floyd–Warshall algorithm typically only provides the lengths of the paths between all pairs of vertices. With simple modifications, it is possible to create a method to reconstruct the actual path between any two endpoint vertices. While one may be inclined to store the actual path from each vertex to each other vertex, this is not necessary, and in fact, is very costly in terms of memory. Instead the shortest path tree allows us to efficiently reconstruct a path from any two connected vertices.
Pseudocode
let dist be a |V|×|V| array of minimum distances initialized to
∞ (infinity)
let next be a |V|×|V| array of vertex indices initialized to null
procedure FloydWarshallWithPathReconstruction() is
for each edge (u, v) do
dist[u][v] ← w(u, v) // The weight of the edge (u, v)
next[u][v] ← v
for each vertex v do
dist[v][v] ← 0
next[v][v] ← v
for k from 1 to |V| do // standard Floyd-Warshall implementation
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
next[i][j] ← next[i][k]
procedure Path(u, v)
if next[u][v] = null then
return []
path = [u]
while u ≠ v
u ← next[u][v]
path.append(u)
return path
Time Complexity
There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n³).
Space Complexity
The space complexity of the Floyd-Warshall algorithm is O(n²).
Floyd Warshall Algorithm Applications
1. To find the shortest path is a directed graph
2. To find the transitive closure of directed graphs
3. To find the Inversion of real matrices
4. For testing whether an undirected graph is bipartite