I know this question is a bit redundant but I am trying to understand a subtle difference between Dijkstra Algorithm and Floyd-Warshall Algorithm. Can I say running Floyd-Warshall is equivalent to running Dijkstra on every vertex in the graph? In other word, Dijkstra will output the optimal path from a single source to other vertices at one runtime while Floyd algorithm does what Dijkstra does but for all vertices in at one runtime so Floyd does not require a source as an input.

Thank you

  • $\begingroup$ "subtle difference" -- they work completely differently, what's subtle about that? $\endgroup$ – Raphael Nov 26 '15 at 22:57
  • 4
    $\begingroup$ Closely related question. $\endgroup$ – Raphael Nov 26 '15 at 22:58

Bth algorithm proceed in different ways.

First you are right in that Floyd Warshall computes all pairs of shortest paths in one run.

If you want to compute all pairs of paths, in the general case (without knowing special property about the graph that could be exploited), running floyd warshall, is more efficent O(n^2) than running n times dijstra O(n^3 + n^2*log(n)).

So for this purpose, in terms of the computations performed, they are different, but in terms of the results, you would obtain the same.

| cite | improve this answer | |
  • 1
    $\begingroup$ Floyd-Warshall time complexity is $O(|V|^3)$. $\endgroup$ – Renato Sanhueza Nov 26 '15 at 18:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.