# All Pairs Shortest Path Problem | Floyd Warshall Algorithm

## All Pairs Shortest Path Problem

1. Let G be a directed graph with n vertices and cost be its adjacency matrix
2. The problem is to determine a matrix A such that A(i,j) is the length of a shortest path from ith vertex to jth vertex
3. This problem is equivalent to solving n single source shortest path problems using greedy method
4. Robert Floyd developed a solution using dynamic programming method
5. A shortest path from I to j goes through 0 or more intermediate vertices and terminates at j
6. If k is an intermediate vertex on this shortest path, then the sub paths from i to k and from k to j must be shortest paths from i to k and k to j respectively. This is based on the principle of optimality.
7. The solution matrix is obtained iteration wise by computing A0, A1, A2, … An
A0 is the cost matrix. The next iterations give the matrix Ak which is computed as follows:
Ak(i, j) = min{ Ak-1(i, j), Ak-1(i,k) + Ak-1(k, j) }, k >= 1
8. An algorithm for the all-pairs shortest path problem is given below:
```Algorithm AllPaths(cost, A, n)
// cost[1:n][1:n] is the cost adjacency matrix of a graph with n vertices;
// A[i][j] is the cost of a shortest path from vertex i to vertex j.
// cost[i][i] = 0.0, for 1 <= i <= n.
{
for ( i:=1 to n ) do
{
for ( j:=1 to n ) do
{
A[i][j] := cost[i][j]; // Copy cost into A.
}
}
for ( k:=1 to n ) do
{
for ( i:=1 to n ) do
{
for ( j:=1 to n ) do
{
A[i][j] = min(A[i][j], A[i][k]+A[k][j]);
}
}
}
}
```
1. Time complexity of Floyd Warshall Algorithm is O(n3)