Let G = (V, E) be a directed graph with n vertices. Let cost be the cost adjacency matrix for G, such that $\mathrm{cost}(i,i)=0$, 1 ≤ i ≤ n.

• $\mathrm{cost}(i,j)$ is the length (cost) of the edge ⟨i, j⟩ if (i, j) ∈ E(G).
• $\mathrm{cost}(i,j)=\infty$ if i ≠ j and ⟨i, j⟩ ∉ E(G).

The all pairs shortest path problem is to determine a matrix A such that $A(i,j)$ is the length of a shortest path from i to j. For every edge ⟨i, j⟩ we have $C(i,j)\ge 0$, and we require G to have no cycles with negative length.

A shortest i to j path in G, i ≠ j, originates at i, goes through some intermediate vertices and terminates at j. If k is some intermediate vertex, then the paths from i to k and from k to j must also be shortest paths.

Dynamic programming approach

If k is an intermediate vertex on a shortest i to j path with the highest index, then the i to k path is a shortest i to k path in G going through no vertex with index greater than k − 1. Similarly, the k to j path is a shortest k to j path in G going through no vertex of index greater than k − 1.

Let $A^k(i,j)$ represent the length of a shortest path from i to j going through no vertex of index greater than k. Then:

The recurrence used by the algorithm is:

Why negative cycles are not allowed

The recurrence would give

Instead we see that

because the path 1, 2, 1, 2, 1, 2, …, 1, 2, 3 can repeat the cycle (1, 2, 1), which has a length of −1.

Computing Aⁿ

Aⁿ can be computed by first computing A¹, A², then A³ and so on. Since there is no vertex in G with index greater than n, $A(i,j)=A^n(i,j)$. The function AllPaths computes $A^n(i,j)$.

Algorithm AllPaths(cost, A, n)

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];
    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]);
}

Time complexity: $\Theta \left(n^3\right)$, since there are three nested loops of n iterations each.

Example

Computing A¹ (using vertex 1 as the intermediate vertex)

Computing A² (using vertex 2 as the intermediate vertex)

Computing A³ (using vertex 3 as the intermediate vertex)

A³ is the final matrix: it gives the shortest distance between every pair of vertices. For example, the shortest path from vertex 2 to vertex 1 has length 5, found through vertex 3 (2 + 3).