Introduction
Algorithms are an essential part of today’s life. It helps ease down our tough calculations or processes. Floyd Warshall is also an Algorithm used in edge-weighted graphs. The basic use of Floyd Warshall is to calculate the shortest path between two given vertices.
An Algorithm is defined as a set of rules or instructions that help us to define the process that needs to be executed step-by-step. It teaches the machine to solve problems using the same rules.
In real life, you can say it can help in finding out the shortest route one should take to travel from one location to another in the minimum time. In such an example, the locations will act as vertices while the time required to travel using different routes will amount to the weight given to that route or edge.
So how does it work? The Floyd Warshall Algorithm uses the concept of Dynamic programming which says that for every step taken, the program needs to make a decision. In dynamic programming, we perform small operations simultaneously and then add them up to give us the final result. So what are the decisions the algorithm makes? Consider the following example of an edge-weighted graph:
Note here that the edges do not have any negative weights. Now when we start with the algorithm, we need to make sure that we first can make a corresponding matrix that shows us the correct weights. Create a matrix A1 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.
Rules to keep in mind while making the matrix are:
- In case of a self loop, write 1 at the diagonal for the edge number.
- In case no edge is present between two vertices, write infinity.
So we will start with the edge 1. One thing to keep in mind is the row and column of the edge you are choosing need to be ignored. In this case, the first row and column are left as they are. So are the diagonals since we don’t have any diagonals here. Now look for an edge between 2 and 4. There is not any. Thus in A0, we have A[2,4]=infinity. But now, apply Floyd Warshall and look for the edge taking 1 as intermediate. We use the given formula to find out the shortest distance between edge 2 and 4:
Now we put the values and we have, for A1[2, 4], the direct distance from vertex 2 to 4 is infinity and the sum of the distance from vertex 2 to 4 through vertex 1 (i.e. from vertex 2 to 1 and from vertex 1 to 4) is 15 . Since 15 < infinity, A1 [2, 4] is filled with 15.
A0[2,4] A0[2,1]+A0[1,4]
infinity > 8 + 7
Since we have a value less than the previous value, we replace infinity at A[2,4] with 15, that is the shortest Path found using Floyd Warshall Algorithm between edges 2 and 4. We go on finding the same way for each path using each edge as the intermediate. 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 before. Now let us check for A2[1,3].
A1[1,3] A1[1,2]+A1[2,3]
infinity > 3 + 2
Now since 5 is the smaller path, we replace infinity from A1[1,3] to 5 in A2[1,3]. The last matrix formed gives us the shortest paths possible between any two edges of the graph. Here A4 is the answer to our problem.
Code
Now one wonders how to write the algorithm. Once again look at the methodology used. Before k-th phase of n edged graph (k=1…n), A[i][j] for any vertices i and j stores the length of the shortest path between the vertex I and vertex j, which contains only the vertices {1,2,…,k−1} as internal vertices in the path. The decision needed to take is to choose the shortest path using the intermediate edge.
for (int k = 0; k < n; ++k)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
A[i][j] = min(A[i][j], d[i][k] + A[k][j]);
}
}
}
46+ registered 