I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm:

Let $dp[i][j][n]$ denote the shortest path from $V_i$ to $V_j$ using at most $n$ vertices. Use $dp[i][j][n] = \min_{V_k\text{ adjacent to } V_i} (e_{ik}+dp[k][j][n-1], dp[i][j][n-1])$ to compute all values of $dp[i][j][n]$.

This above algorithm runs in $O(EV^2) = O(V^4)$, and it's clearly slower than Floyd-Warshall. But I don't intuitively see why that should be the cases (since both look pretty similar) -- i.e what this algo is doing "dumbly"/recalculating which is useless/can be speed up.

Can somebody provide some intuition for why this is slower ? Or in general intuition about why you should expect to find all pair of distances in $O(V^3)$, not in something like $O(V^4)$ or greater ?

  • To elaborate more on what sort of answers is wanted (from codeforces.com/blog/entry/63685?#comment-475381) " If I am asked to come up with an algorithm to find all pair distances, either I'll come up the most obvious one (Dijkstra from each vertex, total ) or the DP mentioned in that SE thread with complexity O(EV2), but DP on the middle vertex index will be the last thing that would come to my mind. We were asking for the intuition/insight behind how can someone come up with that." – alxchen Dec 6 at 16:05
  • It might be that the graph is complete -- in which case every vertex is adjacent to each $v_i$. If you're asking why we should "expect" that we actually can find all distances in $O(n^3)$ time (with F-W), I can only say that I agree that it's surprising -- which is what makes F-W a great example of how effective dynamic programming can be. – j_random_hacker Dec 6 at 17:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.