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\left(n^{3}\right).