Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Code
3.
Benefits
4.
Applications
5.
Frequently Asked Questions
5.1.
What is the Floyd-Warshall algorithm used for?
5.2.
How does the Floyd-Warshall algorithm work?
5.3.
What is the time complexity of the Floyd-Warshall algorithm?
5.4.
What are the advantages of using the Floyd-Warshall algorithm?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Floyd Warshall Algorithm At a Glance

Author Nilesh Kumar
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Introduction to Floyd Warshall

 

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. 

What is algorithm

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.

Floyd algorithm

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:

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.
graph 2

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:

Formulae

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.

Adjacency Marix

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]);
        }
    }
}
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Check out this problem - Frog Jump

Frequently Asked Questions

What is the Floyd-Warshall algorithm used for?

The Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices in a graph. This can be useful in a variety of applications, such as in network routing, where it can be used to find the most efficient way to send data between different points in a network.

How does the Floyd-Warshall algorithm work?

The Floyd-Warshall algorithm works by computing the shortest path between all pairs of vertices in a graph. It does this by maintaining a table of the shortest distances between pairs of vertices, and then updating that table using dynamic programming.

What is the time complexity of the Floyd-Warshall algorithm?

The time complexity of the Floyd-Warshall algorithm is O(n^3), where n is the number of vertices in the graph. This makes it less efficient than other algorithms for finding the shortest path between pairs of vertices, such as Dijkstra's algorithm, which has a time complexity of O((E+V)logV).

What are the advantages of using the Floyd-Warshall algorithm?

The main advantage of using the Floyd-Warshall algorithm is that it is able to find the shortest path between all pairs of vertices in a graph, whereas other algorithms are only able to find the shortest path between a single pair of vertices. This makes it useful in applications where you need to find the shortest path between all pairs of vertices, such as in network routing.

Conclusion

In this blog, we have discussed the Floyd Warshall Algorithm at a glance along with code and benefits. You can also refer

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Learning!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass