Floyd Warshall Algorithm
ABOUT THE ALGORITHM
This blog is going to discuss a famous algorithm that is used to find the shortest path in a directed weighted graph with positive and negative edges weights, the Floyd Warshall algorithm. This algorithm is an example of dynamic programming
Floyd Warshall is also known as the all-pair shortest path algorithm.
Executing this algorithm once will search the summed weights among all the pairs of the vertices of the respected graph.
This algorithm compares all possible paths in the graph among all the vertices pairs.
ALGORITHM
First, from the given graph we construct an initial distance graph. D0. It gives the direct distance between the vertices.
Then then the D0 matrix is updated, considering all vertices as an intermediate vertex.
The aim is to pick one vertex and update the shortest path, which includes the selected vertex as the intermediate vertex in the shortest path. And one by one do this for all the vertices.
K is the intermediate vertex, when we select this k value we have already considered {0,1,2,3…k-1} as the intermediate vertex.
For all the pairs (i,j) form the source and destination nodes.
This has two possibilities:
a) When k is not the intermediate vertex. Then the shortest path from vertex i to vertex j. value of A[i][j] stays the same.
b) K as intermediate vertex for shortest path i to j. A[i][j], its value is updated to A[i][k] + A[k][j] if A[i][j] > A[i][k] + A[k][j]
SOLVING AN EXAMPLE
We will be solving the following figure using the Floyd Warshall algorithm for the shortest path.
STEP 1:
We will make a matrix of this form in all the coming steps, matrix for different k, intermediate vertex. Matrix of dimension n*n where n is the number of vertices. the row and column are represented by i and j respectively. Where i and j are the vertices of the graph.
We’ll build the D0 matrix, this matrix is the initial distance matrix, direct distance from all the vertices.
we write all the weights in the form it is given. Here, the diagonal elements that are the self-loop will have the value equal to 0. Vetices with a direct edge will have a distance equal to the weights that are given. for vertices that are not having any direct edge will have the value infinite.
STEP 2
Now we build the D1 matrix.
For the D1 matrix, we have one vertex, vertex 1, through which we can go to another vertex to have the shortest path.
the D1 matrix for this graph is
Here for A[i][j]=A[3][2] we go from vertex 3 to vertex 1 and from vertex 1 to vertex 2, so the distance value is reduced to 12 from infinite.
similarly, we fill in all the other elements. We update the values where we can and keep the rest of the values the same.
STEP 3
Making the D2 matrix
Now for this graph, we have 2 vertices to go through, vertex 1 and vertex 2, for the shortest path.
Here if we see A[4,3] is having a direct distance value but we have a chance to reduce the value. So, we go frame vertex 4 to vertex 2 and from vertex 2 to vertex 3, giving the lowest value 3.
similarly, we find all the other elements in matrix D2.
STEP 4
Building the matrix D3, now we have three vertices to go through for the shortest path. vertex 1, vertex 2 and vertex 3.
For example, we have updated the value for A[4,1] from infinite to 7, by going from vertex 4 to vertex 2 and from vertex 2 to vertex 3 and from vertex 3 to vertex 1 making the shortest path 7.
Similarly, fill in all the elements.
STEP 4
building the final matrix 4
This is the final matrix because the total matrix possible is n, that is the total number of vertices, and this is excluding the initial distance matrix D0.
Here we see that A[3,2] value is reduced and a new shortest distance is updated. we went from vertex 3 to vertex 1to vertex 4 to vertex 2.
And similarly filling in all the other values for the matrix.
TIME AND SPACE COMPLEXITY
Using this algorithm, you can find the shortest path between any two nodes in O(V3) time.
The Floyd-Warshall algorithm is also unique because it works regardless of whether or not your graph has negative edge weights (as long as there are no negative cycles).
Here’s psuedo-code:
Let dist be a |V| x |V| array of minimum distances initialized to infinity (INF)
For each vertex v
dist[v][v] ← 0
For each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
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] // if using this vertex as an intermediate point gives us a shorter path, update the minimum distance for the pair of vertices (i, j).
