Floyd Warshall Algorithm - David-Chae/Algorithms_Notes_Solutions GitHub Wiki
Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative).
Why Floyd-Warshall Algorithm
Robert W Floyd1(https://en.wikipedia.org/wiki/Robert_W._Floyd#cite_note-1) (June 8, 1936 – September 25, 2001) was a computer scientist. His contributions include the design of the Floyd–Warshall algorithm (independently of Stephen Warshall), which efficiently finds all shortest paths in a graph.
Floyd Warshall Algorithm Complexity
Time Complexity
There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n3).
Space Complexity
The space complexity of the Floyd-Warshall algorithm is O(n2).
Floyd Warshall Algorithm Applications
To find the shortest path is a directed graph To find the transitive closure of directed graphs To find the Inversion of real matrices For testing whether an undirected graph is bipartite
Implementation
Comparison with other shortest path algorithms
The Floyd–Warshall algorithm is a good choice for computing paths between all pairs of vertices in dense graphs, in which most or all pairs of vertices are connected by edges. For sparse graphs with non-negative edge weights, lower asymptotic complexity can be obtained by running Dijkstra's algorithm from each possible starting vertex, since the worst-case running time of repeated Dijkstra ({\displaystyle O(|E||V|+|V|^{2}\log |V|)}{\displaystyle O(|E||V|+|V|^{2}\log |V|)} using Fibonacci heaps) is smaller than the {\displaystyle O(|V|^{3})}O(|V|^{3}) running time of the Floyd–Warshall algorithm when {\displaystyle |E|}|E| is significantly smaller than {\displaystyle |V|^{2}}|V|^{2}. For sparse graphs with negative edges but no negative cycles, Johnson's algorithm can be used, with the same asymptotic running time as the repeated Dijkstra approach.
There are also known algorithms using fast matrix multiplication to speed up all-pairs shortest path computation in dense graphs, but these typically make extra assumptions on the edge weights (such as requiring them to be small integers).[15]16(https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#cite_note-16) In addition, because of the high constant factors in their running time, they would only provide a speedup over the Floyd–Warshall algorithm for very large graphs.
How Floyd-Warshall Algorithm Works?
Let the given graph be:
Step 1
Follow the steps below to find the shortest path between all the pairs of vertices.
Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the column are indexed as i and j respectively. i and j are the vertices of the graph.
Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is no path from ith vertex to jth vertex, the cell is left as infinity.
Step 2
Now, create a matrix A1 using matrix A0. The elements in the first column and the first row are left as they are. The remaining cells are filled in the following way.
Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is the first vertex. A[i][j] is filled with (A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).
That is, if the direct distance from the source to the destination is greater than the path through the vertex k, then the cell is filled with A[i][k] + A[k][j].
In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex through this vertex k.
For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum of the distance from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7. Since 4 < 7, A0[2, 4] is filled with 4.
Step 3
Similarly, A2 is created using A1. The elements in the second column and the second row are left as they are.
In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in step 2.
Step 4
Similarly, A3 and A4 is also created.
Step 5
A4 gives the shortest path between each pair of vertices.
Floyd-Warshall Algorithm
