Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

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.

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:

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

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:

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

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

FloydWarshallAlgorithm algorithm = new FloydWarshallAlgorithm();

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

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:

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:

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