Floyd Warshall Algorithm (2024)

'; var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd(ad_id); });

The Floyd-Warshall algorithm is a graph algorithm that is deployed to find the shortest path between all the vertices present in a weighted graph. This algorithm is different from other shortest path algorithms; to describe it simply, this algorithm uses each vertex in the graph as a pivot to check if it provides the shortest way to travel from one point to another.

Floyd-Warshall algorithm works on both directed and undirected weighted graphs unless these graphs do not contain any negative cycles in them. By negative cycles, it is meant that the sum of all the edges in the graph must not lead to a negative number.

Since, the algorithm deals with overlapping sub-problems – the path found by the vertices acting as pivot are stored for solving the next steps – it uses the dynamic programming approach.

Floyd-Warshall algorithm is one of the methods in All-pairs shortest path algorithms and it is solved using the Adjacency Matrix representation of graphs.

Floyd-Warshall Algorithm

Consider a graph, G = {V, E} where V is the set of all vertices present in the graph and E is the set of all the edges in the graph. The graph, G, is represented in the form of an adjacency matrix, A, that contains all the weights of every edge connecting two vertices.

Algorithm

Step 1 − Construct an adjacency matrix A with all the costs of edges present in the graph. If there is no path between two vertices, mark the value as ∞.

Step 2 − Derive another adjacency matrix A₁ from A keeping the first row and first column of the original adjacency matrix intact in A₁. And for the remaining values, say A₁[i,j], if A[i,j]>A[i,k]+A[k,j] then replace A₁[i,j] with A[i,k]+A[k,j]. Otherwise, do not change the values. Here, in this step, k = 1 (first vertex acting as pivot).

Step 3 − Repeat Step 2 for all the vertices in the graph by changing the k value for every pivot vertex until the final matrix is achieved.

Step 4 − The final adjacency matrix obtained is the final solution with all the shortest paths.

Pseudocode

Floyd-Warshall(w, n){ // w: weights, n: number of vertices for i = 1 to n do // initialize, D (0) = [wij] for j = 1 to n do{ d[i, j] = w[i, j]; } for k = 1 to n do // Compute D (k) from D (k-1) for i = 1 to n do for j = 1 to n do if (d[i, k] + d[k, j] < d[i, j]){ d[i, j] = d[i, k] + d[k, j]; } return d[1..n, 1..n];}

Example

Consider the following directed weighted graph G = {V, E}. Find the shortest paths between all the vertices of the graphs using the Floyd-Warshall algorithm.

Solution

Step 1

Construct an adjacency matrix A with all the distances as values.

$$A=\begin{matrix}0 & 5& \infty & 6& \infty \\\infty & 0& 1& \infty& 7\\3 & \infty& 0& 4& \infty\\\infty & \infty& 2& 0& 3\\ 2& \infty& \infty& 5& 0\\\end{matrix}$$

Step 2

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A=\begin{matrix}0 & 5& \infty & 6& \infty \\\infty & & & & \\3& & & & \\\infty& & & & \\2& & & & \\\end{matrix}$$

$$A_{1}=\begin{matrix}0 & 5& \infty & 6& \infty \\\infty & 0& 1& \infty& 7\\3 & 8& 0& 4& \infty\\\infty & \infty& 2& 0& 3\\ 2& 7& \infty& 5& 0\\\end{matrix}$$

Step 3

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{2}=\begin{matrix} & 5& & & \\\infty & 0& 1& \infty& 7\\ & 8& & & \\ & \infty& & & \\ & 7& & & \\\end{matrix}$$

$$A_{2}=\begin{matrix}0 & 5& 6& 6& 12 \\\infty & 0& 1& \infty& 7\\3 & 8& 0& 4& 15\\\infty & \infty& 2& 0& 3\\2 & 7& 8& 5& 0 \\\end{matrix}$$

Step 4

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{3}=\begin{matrix} & & 6& & \\ & & 1& & \\3 & 8& 0& 4& 15\\ & & 2& & \\ & & 8& & \\\end{matrix}$$

$$A_{3}=\begin{matrix}0 & 5& 6& 6& 12 \\4 & 0& 1& 5& 7\\3 & 8& 0& 4& 15\\5 & 10& 2& 0& 3\\2 & 7& 8& 5& 0 \\\end{matrix}$$

Step 5

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{4}=\begin{matrix}& & & 6& \\& & & 5& \\& & & 4& \\5 & 10& 2& 0& 3\\& & & 5& \\\end{matrix}$$

$$A_{4}=\begin{matrix}0 & 5& 6& 6& 9 \\4 & 0& 1& 5& 7\\3 & 8& 0& 4& 7\\5 & 10& 2& 0& 3\\2 & 7& 7& 5& 0 \\\end{matrix}$$

Step 6

Considering the above adjacency matrix as the input, derive another matrix A₀ by keeping only first rows and columns intact. Take k = 1, and replace all the other values by A[i,k]+A[k,j].

$$A_{5}=\begin{matrix}& & & & 9 \\& & & & 7\\ & & & & 7\\& & & & 3\\2 & 7& 7& 5& 0 \\\end{matrix}$$

$$A_{5}=\begin{matrix}0 & 5& 6& 6& 9 \\4 & 0& 1& 5& 7\\3 & 8& 0& 4& 7\\5 & 10& 2& 0& 3\\2 & 7& 7& 5& 0 \\\end{matrix}$$

Analysis

From the pseudocode above, the Floyd-Warshall algorithm operates using three for loops to find the shortest distance between all pairs of vertices within a graph. Therefore, the time complexity of the Floyd-Warshall algorithm is O(n³), where ‘n’ is the number of vertices in the graph. The space complexity of the algorithm is O(n²).

Implementation

Following is the implementation of Floyd Warshall Algorithm to find the shortest path in a graph using cost adjacency matrix -

#include <stdio.h>void floyds(int b[3][3]) { int i, j, k; for (k = 0; k < 3; k++) { for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if ((b[i][k] * b[k][j] != 0) && (i != j)) { if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) { b[i][j] = b[i][k] + b[k][j]; } } } } } for (i = 0; i < 3; i++) { printf("Minimum Cost With Respect to Node: %d\n", i); for (j = 0; j < 3; j++) { printf("%d\t", b[i][j]); } }}int main() { int b[3][3] = {0}; b[0][1] = 10; b[1][2] = 15; b[2][0] = 12; floyds(b); return 0;}

Minimum Cost With Respect to Node: 001025Minimum Cost With Respect to Node: 127015Minimum Cost With Respect to Node: 212220

#include <iostream>using namespace std;void floyds(int b[][3]){ int i, j, k; for (k = 0; k < 3; k++) { for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if ((b[i][k] * b[k][j] != 0) && (i != j)) { if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) { b[i][j] = b[i][k] + b[k][j]; } } } } } for (i = 0; i < 3; i++) { cout<<"Minimum Cost With Respect to Node:"<<i<<endl; for (j = 0; j < 3; j++) { cout<<b[i][j]<<"\t"; } }}int main(){ int b[3][3]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { b[i][j] = 0; } } b[0][1] = 10; b[1][2] = 15; b[2][0] = 12; floyds(b); return 0;}

Minimum Cost With Respect to Node:00 10 25Minimum Cost With Respect to Node:127 0 15Minimum Cost With Respect to Node:212 22 0

import java.util.Arrays;public class Main { public static void floyds(int[][] b) { int i, j, k; for (k = 0; k < 3; k++) { for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if ((b[i][k] * b[k][j] != 0) && (i != j)) { if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) { b[i][j] = b[i][k] + b[k][j]; } } } } } for (i = 0; i < 3; i++) { System.out.println("Minimum Cost With Respect to Node:" + i); for (j = 0; j < 3; j++) { System.out.print(b[i][j] + "\t"); } } } public static void main(String[] args) { int[][] b = new int[3][3]; for (int i = 0; i < 3; i++) { Arrays.fill(b[i], 0); } b[0][1] = 10; b[1][2] = 15; b[2][0] = 12; floyds(b); }}

Minimum Cost With Respect to Node:00 10 25Minimum Cost With Respect to Node:127 0 15Minimum Cost With Respect to Node:212 22 0

import numpy as npdef floyds(b): for k in range(3): for i in range(3): for j in range(3): if (b[i][k] * b[k][j] != 0) and (i != j): if (b[i][k] + b[k][j] < b[i][j]) or (b[i][j] == 0): b[i][j] = b[i][k] + b[k][j] for i in range(3): print("Minimum Cost With Respect to Node:", i) for j in range(3): print(b[i][j], end="\t")b = np.zeros((3, 3), dtype=int)b[0][1] = 10b[1][2] = 15b[2][0] = 12#calling the methodfloyds(b)

Minimum Cost With Respect to Node: 001025Minimum Cost With Respect to Node: 127015Minimum Cost With Respect to Node: 212220