Floyd-Warshall Algorithm solves the all-pairs shortest paths problem. We solve using dynamic programming.

constituents

initialization: d[u,v] = ∞ if u and v are not neighbors; d[u,v] = w(u,v) if u and v are neighbors; d[u,u] = 0.

subproblem: for all pairs \(u,v\), find the cost of the shortest path from \(u\) to \(v\) so that we only use the first \(1 … k-1\) vertices as internal “hops”.

recursion: two cases; for the \(k\) th new vertex introduced, if the shortest path does not go through \(k\) even with \(k\) added, then we can just copy the previous shortest path; if the shortest path goes through \(k\):

1. for all the in edges of \(k\), find the shortest that connects from \(u \to w’\) for each in vertex of \(k\) named \(w’\); find the storstest path that connects from \(w \to v\) for each out vertex of \(k\) named \(w\). Because sub-paths of shortest paths are shortest paths, there we go.
2. take the min between the shortest path from before and the new one involving \(k\)

tada.

requirements

d[u,v] = \infty, for all (u,v)
d[u,u] = 0, for all (u)
d[u,v] = weight(u,v) for (u,v) in E

for k = 1 ... n:
    for u in V:
        for v in V:
            d_prev = d
            d[u,v] = min(d_prev[u,v], d_prev[u,k] + d_prev[k,v])

return d

additional information

all-pairs shortest paths

Instead of Dijikstra’s Algorithm style shortest path, this is for solving the shortest path from every pair of nodes (i.e. instead of a single starting \(s\)).

correctness