Variants of Floyd-Warshall

Floyd-Warshall can solve related problems by changing the update rule. Minimax path: replace $\min$ with $\max$ and addition with $\min$ to find paths where the maximum edge is minimized. Maximin path: replace $\min$ with $\max$ and addition with $\max$ to find paths where the minimum edge is maximized.

The same $O(n^3)$ structure solves different improvement problems. This shows the power of the dynamic programming formulation.

Space complexity is $O(n^2)$ for the data structures used.