CLRS includes two dynamic programming algorithms for solving the same problem: all-pairs shortest paths.

The kernels of these algorithms (side-by-side) look almost identical, except that they seem to exploit two different dynamic programming relationships about this problem.

What's the intuition behind the difference between these two dynamic programming relationships?

To be clear, the code for EXTEND-SHORTEST-PATHS is actually used by the routine below, with a total runtime of $O(n^4)$ which is slower than Floyd-Warshall above, which runs in $O(n^3)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.