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]);
}
}
}
Benefits:
You might think as to what are the benefits of using the Floyd Warshall Algorithm for solving such problems. The benefits are that the algorithm does not require unnecessary steps and processes, is easy to be executed and has the minimum time complexity in the worst case. It has O(n^2) time complexity while other algorithms have O(n^3) time complexity.
Applications:
The Floyd Warshall Algorithm has a number of applications in real life too. It is not only used in mathematical operations like these but is also very useful in daily life problems of networking. Its other applications are:
- All-pairs shortest path: Computing shortest paths between every pair of vertices in a directed graph.
- Transitive closure: Basically for determining reachability of nodes. Transitive closure has many uses in determining relationships between things.
// Transitive closure variant of Floyd-Warshall
// input: d is an adjacency matrix for n nodes.
// reachability of a node to itself e.g. d[i][i] should be initialized to 1.
// output: d[i][j]=1 will mean j can be reached from i.
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]==’1′ && d[k][j]==’1′) d[i][j]=’1′;
- Detecting negative-weight cycles in graphs. (If there is a negative weight cycle, the distance from the start node to itself will be negative after running the algorithm).
- Bipartiteness – (Although you can also do Bipartiteness checking based on single-source shortest paths algorithms like Dijkstra). Basically, you can detect whether a graph is bipartite via parity. Set all edges to a weight of 1, all vertices at an odd shortest-distance away from some arbitrary root V are in one subset, all vertices at an even distance away are in another subset.
- Minimax: This in graph problems involves finding a path between two nodes that minimises the maximum cost along the path. (Example problems include finding feasible paths to take by car with a limited fuel tank and rest stations at every node). See below for the tweak for Floyd-Warshall that enables finding minimax. You can also add in an update to a predecessor matrix in order to keep track of the actual path found.
// Minimax variant of Floyd-Warshall example
// input: d is a distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the minimax path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
- Maximin: The other way around from Minimax – here you have problems where you need to find the path that maximises the minimum cost along a path. (Example problems include trying to maximise the load a cargo truck can take when roads along a path may have a weight limit, or trying to find a network routing path that meets a minimum bandwidth requirement for some application). See below for the tweak for Floyd-Warshall that enables finding maximin.
// Maximin variant of Floyd-Warshall example
// input: d is a distance matrix for n nodes e.g. d[i][j] is the direct distance from i to j.
// the distance from a node to itself e.g. d[i][i] should be initialized to 0.
// output: d[i][j] will contain the length of the maximin path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
- Safest path: Similar in construction of Floyd-Warshall to minimax and maximin – Need to maximise the product of probabilities of survival along a path. Simply change the max to a min to find the most dangerous path.
// Safest path variant of Floyd-Warshall example
// input: p is a probability matrix (probability of survival) for n nodes
// e.g. p[i][j] is the probability of survival moving directly from i to j.
// the probability from a node to itself e.g. p[i][i] should be initialized to 1
// output: p[i][j] will contain the probability of survival using the safest path from i to j.
for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
p[i][j] = max(p[i][j], p[i][k] * p[k][j]);
Given the popularity and importance of this algorithm, learning and solving this one is a must-have.
To explore more about data structures and algorithms, click here
By Deepak Jain
