## What is Floyd Warshalls Algorithm?

Image Reference: Geeks for Geeks

Let the vertices of G be V = {1, 2........n} and consider a subset {1, 2........k} of vertices for some k. For any pair of vertices i, j ? V, considered all paths from i to j whose intermediate vertices are all drawn from {1, 2.......k}, and let p be a minimum weight path from amongst them. The Floyd-Warshall algorithm is known to exploits a link between path p and shortest paths from i to j with all intermediate vertices in the set {1, 2.......k-1}. The link depends on whether or not k is an intermediate between vertex of path p.

If k is not the intermediate vertex of path p, then all intermediate vertices of path p are in the set {1, 2........k-1}. Thus, the shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2.......k-1} is also the shortest path i to j with all intermediate vertices in the set {1, 2.......k}.
If k is the intermediate vertex of path p, then we break p down into i ? k ? j.

Let dij(k) be the weight of the shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2.......k}.

A recursive definition for floyd warshall is given as:

## Floyd Warshalls Flowchart:

Image Reference: Geeks for Geeks

## Floyd Warshalls Pseudo Code:

FLOYD - WARSHALL (W)
1. n = rows [W].
2. D0 = W
3. for k = 1 to n
4. do for i = 1 to n
5. do for j = 1 to n
6. do dij(k) = min (dij(k-1),dik(k-1)+dkj(k-1) )
7. return D(n)
## Floyd Warshalls Implementation in Java:

import java.util.*;
import java.lang.*;
import java.io.*;
class AllPairShortestPath
{
/*final static int */ final static int INF = 99999, V = 4;
void floydWarshall(int graph[][])
{
int dist[][] = new int[V][V];
int i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
for (i = 0; i < V; i++)
{
for (j = 0; j < V; j++)
{
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
void printSolution(int dist[][])
{
System.out.println("The following matrix shows the shortest "+
"distances between every pair of vertices");
for (int i=0; i< V; ++i)
{
for (int j=0; j< V; ++j)
{
if (dist[i][j]==INF)
System.out.print("INF ");
else
System.out.print(dist[i][j]+" ");
}
System.out.println();
}
}
// Driver program to test above function
public static void main (String[] args)
{
/* Let us create the following weighted graph
10
(0)------->(3)
| /|\
5 | |
| | 1
\|/ |
(1)------->(2)
3 */
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
AllPairShortestPath a = new AllPairShortestPath();
// Print the solution
a.floydWarshall(graph);
}
}
## Output:

The Following matrix shows the shortest distances between every pair of vertices:
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0