'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Dec 7, 2023
Medium

# Floyd Warshall Algorithm

1 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## 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.

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.

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:

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

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.

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.

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.

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

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

## Implementations of Floyd-Warshall Algorithm in Different Programming Languages:

• C

### C

``#include <stdio.h>#define NUM_VERTICES 4#define INFINITY_VAL 99999// Function to print the shortest distances matrixvoid printShortestDistances(int distance[][NUM_VERTICES]);// Applying the Floyd Warshall algorithmvoid 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 distancesvoid 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 functionint 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:

• C++

### C++

``#include <stdio.h>#define NUM_VERTICES 4#define INFINITY_VAL 99999// Function to print the shortest distances matrixvoid printShortestDistances(int distance[][NUM_VERTICES]);// Applying the Floyd Warshall algorithmvoid 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 distancesvoid 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 functionint 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:

• 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:

• Python

### Python

``# Number of nodes in the graphnum_nodes = 4# Define a high value to represent infinityINFINITY = 99999# Solve all-pair shortest path using Floyd Warshall Algorithmdef 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 matrixdef 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 codeif __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:

## 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.

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.

### 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.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems