Suggest edit — Floyd-Warshall Algorithm

Title

Name

Note

---
title: "Floyd-Warshall Algorithm"
type: concept
related: [Dijikstra S Algorithm, Dynamic Programming, Floyd Warshall Algorithm]
source: https://www.jemoka.com/posts/kbhfloyd_warshall_algorithm/
confidence: high
status: active
---

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 &hellip; k-1\) vertices as internal &ldquo;hops&rdquo;.
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\):
for all the in edges of \(k\), find the shortest that connects from \(u \to w&rsquo;\) for each in vertex of \(k\) named \(w&rsquo;\); 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. 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&rsquo;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 If there are no negative cycles in a weighted directed graph \(G\), then the Floyd-Warshall algorithm, running on \(G\), returns a matrix \(D^{n}\) such that \(D^{n} [u,v]\).
Runtime Runs in \(O\qty(n^{3})\).