Page 31Dynamic Programming

31 — Floyd–Warshall

All-pairs shortest paths as DP over intermediate vertex k.

APSP DP table

At step k, decide whether path i→k→j improves i→j.

D^(k)[i][j] = min(D^(k−1)[i][j], D^(k−1)[i][k] + D^(k−1)[k][j])

for k = 0 to n-1: for i = 0 to n-1: for j = 0 to n-1: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Time: O(n³), Space: O(n²). Useful for dense graphs and all-pairs shortest paths.