All-Pairs Shortest Paths

Say we want to find the shortest path between every pair of vertices in G. Edge lengths could be negative, but there are no negative cycles.

Floyd-Warshall

This algorithm uses Dynamic Programming. The subproblems are:

• $dist(i,j,k)=\text{shortest path from i to j, where intermediate vertices can only be in (1,2,...k)}$
• The answer is $dist(i,j,|V|)$
• $dist(i,j,k+1)=min\{dist(i,j,k),dist(i,k+1,k)+dist(k+1,j,k)\}$
  • So we either use $k+1$ or not
• The base case is just limiting $k$ to be 0 where we get $l(i,j)$ if $i,j\in E$ or $\infty$ if $i,j\notin E$.
• Note that here, k just refers to a node in the graph that we are allowed to use

procedure floyd-warshall(G, ℓ)

Input: Directed graph G = (V, E); edge lengths ℓ_e with no negative cycles.
Output: For all u, v ∈ V, where |V| = n, dist(u, v, n) is the shortest path distance from u to v

for i = 1, ..., n:
    for j = 1, ..., n:
        dist(i, j, 0) = ∞

for all (i, j) ∈ E:
    dist(i, j, 0) = ℓ(i, j)

for k = 1, ..., n:
    for i = 1, ..., n:
        for j = 1, ..., n:
            dist(i, j, k) = min {
                dist(i, j, k - 1),
                dist(i, k, k - 1) + dist(k, j, k - 1)
            }

The runtime here is $O(n^3)$.