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 ?

  • $\begingroup$ 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." $\endgroup$
    – katana_0
    Dec 6, 2018 at 16:05
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2018 at 17:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.