Floyd Warshall Algorithm

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.

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.

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:

If k is not an intermediate vertex, then the value of D[i][j] will remain the same.
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.

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.

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

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:

Code Implementation in 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;
}

You can also try this code with Online C Compiler

Run Code

Output:

Code Implementation in 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;
}

You can also try this code with Online C++ Compiler

Run Code

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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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.

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:

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

Frequently Asked Questions

What is the purpose of the Floyd-Warshall algorithm?

The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of vertices in a weighted graph. It efficiently computes the shortest distances, even with negative weights, making it useful for routing, network analysis, and solving problems involving the transitive closure of graphs.

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

The Floyd-Warshall algorithm is a powerful tool for solving all-pairs shortest path problems in weighted graphs. Its ability to handle graphs with negative weights, and its straightforward implementation, make it valuable in various applications, such as network optimization and graph analysis. Despite its O(n³) time complexity, it remains practical for moderately sized graphs, offering a comprehensive solution for finding shortest paths between all vertex pairs. Mastery of this algorithm enhances your understanding of graph theory and dynamic programming.

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.