Floyd-Warshall Algorithm
Published: 2021-05-06 11:11:24

The Floyd-Warshall algorithm is used for finding all pairs shortest path. This algorithm is used to find the shortest path between every pair of vertices in a given edge graph.

Let **G = (V,E)** be a directed graph with **n** vertices. Let cost be a cost adjacency matrix for G such that **cost(i,i) = 0, 1<=i<=n.**

**Cost(i,j) = length or cost of edge (i,j)**, if(i,j) ∈ E(G)  and cost(i,j)= ∞  if (i,j) ∉ E(G)

All-pairs shortest path problems is to determine a matrix A such that A(i,j) is the length of a shortest path from i to j

Let **k** be the highest intermediate vertex between i to j path, then i to k path is a shortest  path in graph **G** going through no vertex with index greater than k-1. Similarly k to j path is a shortest path in graph **G** going through no vertex with index greater than k-1.

First we need to find highest intermediate vertex **k**  then we need to find the two shortest paths from  i to k and k to j.

Then we use A^k(i,j) to represent the length of a shortest path from i to j going through no vertex of index greater than **k**, we obtain

**A^0(i,j)=cost(i,j)**

If it goes through highest intermediate vertex **k** then
       
**A^k(i,j) = A^k-1(i,k)+A^k-1(k,j)**

If it does not then highest intermediate vertex is
 
**A^k(i,j) = A^k-1(i,j)**



To get a recurrence for $A^{k}$(i,j) we need to combine both 

**A^k(i,j) =min{ A^k-1(i,j), A^k-1(i,k)+A^k-1(k,j)}, where k>=1**

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bz7xh2qxamobhcw0pyd7.png)

**Note: For selected intermediate vertex the path that belongs to that vertex remains same**

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zk54rp3v7nldq8qdtwz8.png)

By taking the above matrix we can get  $A^{1}$ matrix.


A^1(2,3) = min{A^0(2,3),A^0(2,1)+A^0(1,3)}

* **$A^{1}$(2,3) = min{2,8+∞} = 2**

A^1(2,4) = min{A^0(2,4),A^0(2,1)+A^0(1,4)}

* **A^1(2,4) = min{∞,8+7} = 15**

A^1(3,2) = min{A^0(3,2),A^0(3,1)+A^0(1,2)}

* **A^1(3,2) = min{∞,5+3} = 8**

A^1(3,4) = min{A^0(4,3),A^0(3,1)+A^0(1,4)}

* **A^1(3,4) = min{1,5+7} = 1**

A^1(4,2) = min{A^0(4,2),A^0(4,1)+A^0(1,2)}

* **$A^{1}$(4,2) = min{∞,2+3} = 2**

A^1(4,3) = min{A^0(4,3),A^0(4,1)+A^0(1,3)}

* **A^1(4,3) = min{∞,2+∞} = 2**

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tchn7kohh17ndwji9795.png)

## Similarly;

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s107bcw6fztbsn93mamm.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9hjgdj5mrr37cexoipnk.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q7suc62nx80ahwnkx6kj.png)

**Algorithm**

```
for(k=1;k<=n;k++)
{
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
    {
      if(a[i][j]>a[i][k]+a[k][j])
      {
        a[i][j] = a[i][k]+a[k][j];
      }
    }
  }
}
```

### Program ###
```
#include<stdio.h>
void floyd(int a[4][4], int n)
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(a[i][j]>a[i][k]+a[k][j])
				{
					a[i][j]=a[i][k]+a[k][j];
				}
		    }
	    }
	}
	printf("All Pairs Shortest Path is :\n");
		for(int i=1;i<=n;i++)
	    {
	    	for(int j=1;j<=n;j++)
	    	{
	    		printf("%d ",a[i][j]);
			}
	    	printf("\n");
		}
}
int main()
{
	int cost[4][4] = {{0, 3, 999, 4}, {8, 0, 2, 999}, {5, 999, 0, 1}, {2, 999, 999, 0}}; 
	int n = 4;

	floyd(cost,n);
}
```

### Output ###

*enter no of vertices :4
The Cost of Adjacency Matrix is :
0 3 9999 7
8 0 2 9999
5 9999 0 1
2 9999 9999 0
All Pairs Shortest Path is :
0 3 5 6
5 0 2 3
3 6 0 1
2 5 7 0*