Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Floyd Warshall Algorithm
3.
Working of Floyd-Warshall Algorithm:
4.
Implementations of Floyd-Warshall Algorithm in Different Programming Languages:
4.1.
Code Implementation in C:
4.2.
C
4.3.
Code Implementation in C++:
4.4.
C++
4.5.
Code Implementation in Java:
4.6.
Java
4.7.
Code Implementation in Python:
4.8.
Python
5.
Understanding Time and Space Complexities of Floyd-Warshall Algorithm:
6.
Some Advantages and Disadvantages of Floyd-Warshall Algorithm:
6.1.
Advantages of the Floyd-Warshall algorithm include:
6.2.
Disadvantages of the Floyd-Warshall set of rules include:
7.
Applications of Floyd Warshall Algorithm
8.
Frequently Asked Questions
8.1.
What is the Floyd algorithm?
8.2.
How does Floyd algorithm work?
8.3.
What is the Floyd routing algorithm?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Floyd Warshall Algorithm

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

Introduction

Graphs are one of the most important topics from an interview perspective. Questions related to graphs are frequently asked in interviews of all the major product-based companies. The Floyd Warshall algorithm is for finding the shortest path between all the pairs of vertices in a weighted graph; the algorithm works for both directed and undirected graphs. This algorithm is asked directly in an interview, or the interviewer may give you a real-life situation and will ask you to solve it using graphs. 
 

floyd algorithm

Before moving on to the algorithm, it is recommended to study Graphs first. This article will describe Floyd Warshall's algorithm with a detailed explanation and code in Java.

Floyd Warshall Algorithm

Before moving to the jargon of the algorithm, let's understand the problem statement with a real-life example.

Imagine that you(A) and four of your friends (B, C, D, and E) live in different cities/locations. The distance between each of these cities is known. You want to know the optimal path, i.e., the least distance between each of your friend's places. The problem can be solved by representing each of your friend's places and your place by vertices of directed and weighted graphs, as shown below.  The weights between the edges are the distance between vertices of the graph.

Floyd Warshall Algorithm

Using the Floyd Warshall algorithm, the above problem can be solved very easily. Floyd Warshall will tell you the optimal distance between each pair of friends and will also tell you that the quickest path from friend D to A’s house is via B.
 

Floyd Warshall algorithm is used to find the shortest path between all the vertices of a directed or undirected weighted graph with no negative cycles.. It is also known as Floyd's algorithm, the Roy-warshall algorithm, the Roy-Floyd algorithm.

 

This algorithm follows the dynamic programming approach to find the shortest paths. The algorithm doesn't construct the path itself, but it can reconstruct it with a simple modification.

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

Working of Floyd-Warshall Algorithm:

The Floyd algorithm works by initializing the solution matrix the same as the input graph matrix as the first step. The solution matrix, D[][], is then updated by considering all the vertices as an intermediate vertex(say k).
 

To determine the shortest path between two vertices i and j, there are two possibilities by considering k as the intermediate vertex:
 

  1. If k is not an intermediate vertex, then the value of D[i][j] will remain the same.
  2. If k is an intermediate vertex, then the value of D[i][j] will be updated in the following manner:
D[i][j] is filled with (D[i][k] + D[k][j]) if (D[i][j] > D[i][k] + D[k][j] )

 

Consider a directed weighted graph given below to understand the working of the Floyd warshall algorithm.

directed weighted grap

Step 1: Create a matrix, D0 of dimensions V*V where V is the number of vertices in the graph. The rows and columns of the matrix are indexed as i and j, respectively, where i and j are the graph's vertices.

 

Each cell of D0[i][j] is filled with distance from the vertex to the jth vertex. The cell is filled with infinity if there is no path from the vertex to the jth vertex.

step1

Step 2: Now create another matrix D1 using matrix D0. The elements in the first row and the first column are left as it is. The remaining cells are filled in the following manner by considering the 1 as the intermediate vertex or k = 1. Calculate the distance between the source vertex and the destination vertex by considering 1 as the intermediate vertex.
 

D[i][j] is filled with (D[i][k] + D[k][j]) if (D[i][j] > D[i][k] + D[k][j] )

 

Step2

Step 3: Similarly, D2 is created using D1. The elements in the second column and the second row are left as it is. The remaining elements are filled by considering the value of k equals 2.

step3

Step 4: Create D3 by considering the value of k = 3.

step4

Step 5: D4 will give the shortest path between each pair of vertices.

 

step5

Implementations of Floyd-Warshall Algorithm in Different Programming Languages:

Code Implementation in C:

  • C

C

#include <stdio.h>

#define NUM_VERTICES 4
#define INFINITY_VAL 99999

// Function to print the shortest distances matrix
void printShortestDistances(int distance[][NUM_VERTICES]);

// Applying the Floyd Warshall algorithm
void floydWarshallAlgorithm(int distance[][NUM_VERTICES])
{
int i, j, k;

// Iterating through all vertices to find the shortest paths
for (k = 0; k < NUM_VERTICES; k++) {
for (i = 0; i < NUM_VERTICES; i++) {
for (j = 0; j < NUM_VERTICES; j++) {
// If a shorter path is found through vertex k
if (distance[i][k] + distance[k][j] < distance[i][j])
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}

// Printing the matrix of shortest distances
printShortestDistances(distance);
}

// Function to print the matrix of shortest distances
void printShortestDistances(int distance[][NUM_VERTICES])
{
printf("Shortest distances between vertices:\n");
for (int i = 0; i < NUM_VERTICES; i++) {
for (int j = 0; j < NUM_VERTICES; j++) {
if (distance[i][j] == INFINITY_VAL)
printf("%7s", "INF");
else
printf("%7d", distance[i][j]);
}
printf("\n");
}
}

// Main function
int main()
{
// Weighted graph represented by adjacency matrix
int graph[NUM_VERTICES][NUM_VERTICES] = {
{ 0, 5, INFINITY_VAL, 11 },
{ INFINITY_VAL, 0, 2, INFINITY_VAL },
{ INFINITY_VAL, INFINITY_VAL, 0, 1 },
{ INFINITY_VAL, INFINITY_VAL, INFINITY_VAL, 7 }
};

// Applying the Floyd Warshall algorithm on the graph
floydWarshallAlgorithm(graph);

return 0;
}

 

Output:

output

Code Implementation in C++:

  • C++

C++

#include <stdio.h>

#define NUM_VERTICES 4
#define INFINITY_VAL 99999

// Function to print the shortest distances matrix
void printShortestDistances(int distance[][NUM_VERTICES]);

// Applying the Floyd Warshall algorithm
void floydWarshallAlgorithm(int distance[][NUM_VERTICES])
{
int i, j, k;

// Iterating through all vertices to find the shortest paths
for (k = 0; k < NUM_VERTICES; k++) {
for (i = 0; i < NUM_VERTICES; i++) {
for (j = 0; j < NUM_VERTICES; j++) {
// If a shorter path is found through vertex k
if (distance[i][k] + distance[k][j] < distance[i][j])
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}

// Printing the matrix of shortest distances
printShortestDistances(distance);
}

// Function to print the matrix of shortest distances
void printShortestDistances(int distance[][NUM_VERTICES])
{
printf("Shortest distances between vertices:\n");
for (int i = 0; i < NUM_VERTICES; i++) {
for (int j = 0; j < NUM_VERTICES; j++) {
if (distance[i][j] == INFINITY_VAL)
printf("%7s", "INF");
else
printf("%7d", distance[i][j]);
}
printf("\n");
}
}

// Main function
int main()
{
// Weighted graph represented by adjacency matrix
int graph[NUM_VERTICES][NUM_VERTICES] = {
{ 0, 5, INFINITY_VAL, 11 },
{ INFINITY_VAL, 0, 2, INFINITY_VAL },
{ INFINITY_VAL, INFINITY_VAL, 0, 1 },
{ INFINITY_VAL, INFINITY_VAL, INFINITY_VAL, 7 }
};

// Applying the Floyd Warshall algorithm on the graph
floydWarshallAlgorithm(graph);

return 0;
}

 

Output:

output

Code Implementation in Java:

  • Java

Java

import java.io.*;
import java.lang.*;
import java.util.*;

class FloydWarshallAlgorithm {
final static int INFINITY = 99999; // A large value to represent infinity
final static int NUM_VERTICES = 4; // Number of vertices in the graph

void findShortestPaths(int distanceMatrix[][]) {
int vertexA, vertexB, intermediate;

/* Add each vertex one by one to the set of intermediate vertices.
--> Before each iteration, we have shortest distances between all pairs
of vertices considering only the vertices in the set {0, 1, 2, .. k-1} as intermediate vertices.
--> After each iteration, vertex k is added to the set of intermediate vertices, and the set becomes {0, 1, 2, .. k} */
for (intermediate = 0; intermediate < NUM_VERTICES; intermediate++) {
// Choose each vertex as the source one by one
for (vertexA = 0; vertexA < NUM_VERTICES; vertexA++) {
// Choose each vertex as the destination for the above picked source
for (vertexB = 0; vertexB < NUM_VERTICES; vertexB++) {
// If vertex intermediate is on the shortest path from vertexA to vertexB,
// update the value of distanceMatrix[vertexA][vertexB]
if (distanceMatrix[vertexA][intermediate] + distanceMatrix[intermediate][vertexB]
< distanceMatrix[vertexA][vertexB])
distanceMatrix[vertexA][vertexB] = distanceMatrix[vertexA][intermediate] + distanceMatrix[intermediate][vertexB];
}
}
}

// Print the matrix showing the shortest distances
printSolution(distanceMatrix);
}

void printSolution(int distanceMatrix[][]) {
System.out.println("Shortest distances between every pair of vertices:");
for (int vertexA = 0; vertexA < NUM_VERTICES; ++vertexA) {
for (int vertexB = 0; vertexB < NUM_VERTICES; ++vertexB) {
if (distanceMatrix[vertexA][vertexB] == INFINITY)
System.out.print("INF ");
else
System.out.print(distanceMatrix[vertexA][vertexB] + " ");
}
System.out.println();
}
}

public static void main(String[] args) {
/* Creating a weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int weightMatrix[][] = { { 0, 5, INFINITY, 11 },
{ INFINITY, 0, 2, INFINITY },
{ INFINITY, INFINITY, 0, 1 },
{ INFINITY, INFINITY, INFINITY, 7 } };

FloydWarshallAlgorithm algorithm = new FloydWarshallAlgorithm();

// Calling the algorithm function
algorithm.findShortestPaths(weightMatrix);
}
}

 

Output:

Output

Code Implementation in Python:

  • Python

Python

# Number of nodes in the graph
num_nodes = 4

# Define a high value to represent infinity
INFINITY = 99999

# Solve all-pair shortest path using Floyd Warshall Algorithm
def floydWarshallAlgorithm(graph):
# Initialize the solution matrix with the same values as the input graph
shortest_distances = list(map(lambda i: list(map(lambda j: j, i)), graph))

# Update shortest distances using intermediate nodes
for intermediate_node in range(num_nodes):
for source_node in range(num_nodes):
for destination_node in range(num_nodes):
# If the intermediate node leads to a shorter path, update the distance
shortest_distances[source_node][destination_node] = min(
shortest_distances[source_node][destination_node],
shortest_distances[source_node][intermediate_node] + shortest_distances[intermediate_node][destination_node]
)

printSolution(shortest_distances)

# A utility function to print the solution matrix
def printSolution(solution_matrix):
print("Shortest distances between every pair of nodes:")
for i in range(num_nodes):
for j in range(num_nodes):
if solution_matrix[i][j] == INFINITY:
print("%7s" % ("INF"), end=" ")
else:
print("%7d\t" % (solution_matrix[i][j]), end=' ')
if j == num_nodes - 1:
print()

# Driver code
if __name__ == "__main__":
graph = [[0, 5, INFINITY, 11],
[INFINITY, 0, 2, INFINITY],
[INFINITY, INFINITY, 0, 1],
[INFINITY, INFINITY, INFINITY, 7]
]
# Call the function to perform the Floyd Warshall Algorithm
floydWarshallAlgorithm(graph)


Output:

Output

Understanding Time and Space Complexities of Floyd-Warshall Algorithm:

In the Floyd-Warshall algorithm, 

  • The outermost loop runs for V iterations (where V is the number of vertices). The two inner loops together run for V * V iterations. Since each iteration involves constant time operations, the overall time complexity of the Floyd-Warshall algorithm is O(V^3).
     
  • The distance matrix requires V x V space to store the shortest path distances between all pairs of vertices. Hence, the space complexity of the Floyd-Warshall algorithm is O(V^2), where V is the number of vertices.

Some Advantages and Disadvantages of Floyd-Warshall Algorithm:

Let us now discuss some advantages and disadvantages of using Floyd-Warshall Algorithm:

Advantages of the Floyd-Warshall algorithm include:

The advantages of Floyd-Warshall algorithm are:

  • The algorithm finds the shortest paths between all the pairs of vertices in a graph thus providing a detailed view of the shortest distances among all nodes.
     
  • It is easy to understand and implement.
     
  • It can work on graphs with both positive and negative edge weights, as long as there are no negative cycles.
     
  • The algorithm can adapt to the changes in the edges and weights of the graph. Thus the programmer does not have to start from scratch. This makes it suitable for dynamic graphs.

Disadvantages of the Floyd-Warshall set of rules include:

The disadvantages of Floyd-Warshall algorithm are:

  • The time complexity of the algorithm is very high ( O(V^3) ). This makes it unsuitable for larger graphs.
     
  • The space complexity of the algorithm is also very high ( O(V^2) ). This becomes an issue for larger graphs.
     
  • The algorithm gives the shortest distances but doesn't provide any information about the actual paths taken.
     
  • If the graph contains negative cycles, the algorithm may not work correctly, as it doesn't handle such cycles.

Applications of Floyd Warshall Algorithm

There are many applications of the Floyd Warshall algorithm. Some of them are given below:

  1. It helps in testing whether the graph is bipartite or not.
     
  2. It helps in finding the shortest path in a directed graph.
     
  3. The algorithm helps to find the regular expressions that are accepted by finite automata.
     
  4. It helps in finding the transitive closure of a directed graph.

Frequently Asked Questions

What is the Floyd algorithm?

The Floyd algorithm, or Floyd-Warshall algorithm, computes the shortest paths between all pairs of vertices in a weighted graph.

How does Floyd algorithm work?

Floyd algorithm work iteratively updates shortest path estimates for all vertex pairs, accommodating for weighted edges, until optimal paths are found.

What is the Floyd routing algorithm?

The Floyd routing algorithm refers to the Floyd-Warshall algorithm when applied to computer networking, determining optimal routes between network nodes.

Conclusion

Graphs are an important part of coding interviews. Questions related to graphs are frequently asked in technical interviews of product-based companies. Once you are done with this, it is time to practice more and more questions related to Graphs on Coding Ninjas Studio.  Practice makes perfect !!

 

You may also check out our interview preparation guided path for preparing for your next interview. Do check out Guided Paths on Coding Ninjas Studio for A complete curated preparation guide for coding interviews in tech and product-based companies. You can choose your tracks and start preparing for your next coding interviews.

Previous article
Bellman Ford Algorithm
Next article
Ford-Fulkerson Algorithm for Maximum Flow
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass