[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhfloyd_warshall_algorithm.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Floyd-Warshall Algorithm" source: https://www.jemoka.com/posts/kbhfloyd_warshall_algorithm/ --- 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\): 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. 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 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})\).