-2
$\begingroup$

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

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Floyd-Warshall time complexity is $O(|V|^3)$. $\endgroup$ Nov 26, 2015 at 18:08

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