Floyd Warshall Algorithm

Floyd's or Floyd-Warshall Algorithm is used to find all pair shortest path for a graph. This algorithm works for weighted graph having positive and negative weight edges without a negative cycle.

Problem

Consider the following weighted graph.

Our task is to find the all pair shortest path for the given weighted graph.

Steps

Step 1: Remove all the loops.

Note! Any edge that starts and ends at the same vertex is a loop.

Step 2: Remove all parallel edges between two vertices leaving only the edge with the smallest weight.

Step 3: Create a distance and sequence table.

How we will proceed

• To find the shortest path between any two nodes we will draw two tables namely, Distance Table (D) and Sequence Table (S).
• We can also refer these tables as matrix.
• The Distance table (D) will hold distance between any two vertices.
• The Sequence table (S) will hold the name of the vertices that will help in finding the shortest path between any two vertices.
• If a graph has k vertices then our table D and S will have k rows and k columns.
• We will use the iterative method to solve the problem.

Notations we will be using

k = Iteration number
D_k = Distance table in kth iteration
S_k = Sequence table in kth iteration
d_ij = The distance between vertex i and j

There are 4 vertices in the graph so, our tables (Distance and Sequence) will have 4 rows and 4 columns.

Distance table D

This table holds the weight of the respective edges connecting vertices of the graph. So, if there in an edge u --> v connecting vertex u to vertex v and having weight w then we will fill the distance table D[u][v] = w. If there is no edge connecting any two vertex u to v then in that case we will fill D[u][v] = INFINITY.

From the graph above we will get the following distance table.

INF means INFINITY

Sequence table S

This table holds the vertex that will be used to find the shortest path to reach from vertex u to vertex v.

From the graph above we will get the following sequence table.

INF means INFINITY

Important Condition

We will fill the cell C_ij in distance table D_k using the following condition.

Is d_ij > d_ik + d_kj [in distance table D_k-1]
If YES then fill the cell C_ij in D_k table with the value d_ik + d_kj of D_k-1 table
If NO then fill the cell C_ij in D_k table with the value d_ij of D_k-1 table
where
i = row number
j = column number
k = iteration number
i.e., we will always fill the cell C_ij in D_k table with the smallest value.

Note! If a graph has N vertices then we will be iterating N times.

The graph has 4 vertices so, we will be iterating 4 times.

Solution

After completing the 4 iterations we will get the following distance array.

And the following sequence table

And the required shortest paths.

Code in C

#include <stdio.h>

#define INF 99999
#define MAX 10

void display(int arr[][MAX], int size);
void floyds(int D[][MAX], int S[][MAX], int size);

int main(void) {
	
	//distance array
	/*
		we have created a distance array of size 10x10 (MAX x MAX)
		but we will be using only 4x4 as the graph has 4 vertices
	*/
	int D[MAX][MAX] = {
		{INF, 5, 1, 2},
		{5, INF, 3, INF},
		{1, 3, INF, 4},
		{2, INF, 4, INF}
	};
	
	//sequence array
	/*
		we have created a sequence array of size 10x10 (MAX x MAX)
		but we will be using only 4x4 as the graph has 4 vertices
	*/
	int S[MAX][MAX] = {
		{INF, 2, 3, 4},
		{1, INF, 3, 4},
		{1, 2, INF, 4},
		{1, 2, 3, INF}
	};
	
	int size = 4;		//total number of vertices in the graph
	
	floyds(D, S, size);
	
	return 0;
}

void floyds(int D[][MAX], int S[][MAX], int size) {
	int i, j, k, l;
	
	//arrays to hold data for current iteration
	/*
		we have created arrays of size 10x10 (MAX x MAX)
		but we will be using only 4x4 as the graph has 4 vertices
	*/
	int Dk[MAX][MAX], Sk[MAX][MAX];
	
	//set Dk and Sk to 0
	for(i = 0; i < size; i++) {
		for(j = 0; j < size; j++) {
			if(i == j) {
				Dk[i][j] = INF;
				Sk[i][j] = INF;
			} else {
				Dk[i][j] = 0;
				Sk[i][j] = 0;
			}
		}
	}
	
	
	//iteration
	/*
		since array indexing start from 0 in C programming
		so, we are setting i,j,k,l to 0
		
		note! in the video tutorial above we have used arrays
		starting from index 1
		
		video: https://www.youtube.com/watch?v=X6n30V6qCWU
	*/
	for(k = 0; k < size; k++) {
		
		//step 1:
		//for each iteration we copy the kth row and kth column to
		//the current array
		for(l = 0; l < size; l++) {
			//copy row
			Dk[k][l] = D[k][l];
			Sk[k][l] = S[k][l];
			
			//copy column
			Dk[l][k] = D[l][k];
			Sk[l][k] = S[l][k];
		}
		
		//step 2:	
		//compute the distance and sequence value for
		//current iteration
		for(i = 0; i < size; i++) {
			
			//for kth iteration we skip the kth row
			if(i == k) {
				continue;
			}
				
			for(j = 0; j < size; j++) {
				
				//for kth iteration we skip the kth column
				if(j == k) {
					continue;
				}
				//if i and j are same i.e., referring to same vertex we skip it
				if(i == j) {
					continue;
				}
				
				//checking
				if(D[i][j] > D[i][k] + D[k][j]) {
					Dk[i][j] = D[i][k] + D[k][j];
					Sk[i][j] = (k+1);	//kth iteration, as indexing starts from 0 so, we add 1
				} else {
					Dk[i][j] = D[i][j];
					Sk[i][j] = S[i][j];
				}
			}
		}
		
		//step 3:
		//copy content of Dk and Sk to D and S
		for(i = 0; i < size; i++) {
			for(j = 0; j < size; j++) {
				D[i][j] = Dk[i][j];
				S[i][j] = Sk[i][j];
			}
		}
	}
	
	//print the distance array and sequence array result
	printf("Distance array: \n");
	display(D, size);
	printf("Sequence array: \n");
	display(S, size);
}

void display(int arr[][MAX], int size) {
	int i, j;
	for(i = 0; i < size; i++) {
		for(j = 0; j < size; j++) {
			if(arr[i][j] == INF) {
				printf("%10s ", "INF");
			} else {
				printf("%10d ", arr[i][j]);
			}
		}
		printf("\n");
	}
}

Time complexity

The time complexity of Floyd's or Floyd-Warshall algorithm is O(V³).