Graph

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.

Consider the following weighted graph.

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

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.

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

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.

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.

D_{0} | 1 | 2 | 3 | 4 |

1 | ||||

2 | ||||

3 | ||||

4 |

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

D_{0} | 1 | 2 | 3 | 4 |

1 | - | 5 | 1 | 2 |

2 | 5 | - | 3 | INF |

3 | 1 | 3 | - | 4 |

4 | 2 | INF | 4 | - |

INF means INFINITY

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

S_{0} | 1 | 2 | 3 | 4 |

1 | ||||

2 | ||||

3 | ||||

4 |

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

S_{0} | 1 | 2 | 3 | 4 |

1 | - | 2 | 3 | 4 |

2 | 1 | - | 3 | 4 |

3 | 1 | 2 | - | 4 |

4 | 1 | 2 | 3 | - |

INF means INFINITY

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.

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

D_{4} | 1 | 2 | 3 | 4 |

1 | - | 4 | 1 | 2 |

2 | 4 | - | 3 | 6 |

3 | 1 | 3 | - | 3 |

4 | 2 | 6 | 3 | - |

And the following sequence table

S_{4} | 1 | 2 | 3 | 4 |

1 | - | 3 | 3 | 4 |

2 | 3 | - | 3 | 3 |

3 | 1 | 2 | - | 1 |

4 | 1 | 3 | 1 | - |

And the required shortest paths.

Source Vertex (i) | Destination Vertex (j) | Distance | Shortest Path |

1 | 2 | 4 | 1 --> 3 --> 2 |

1 | 3 | 1 | 1 --> 3 |

1 | 4 | 2 | 1 --> 4 |

2 | 3 | 3 | 2 --> 3 |

2 | 4 | 6 | 2 --> 3 --> 1 --> 4 |

3 | 4 | 3 | 3 --> 1 --> 4 |

```
#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");
}
}
```

The time complexity of Floyd's or Floyd-Warshall algorithm is O(V^{3}).