1
$\begingroup$

I often read that Floyd-Warshall is a good fit for dense graphs and Johnson's for sparse ones. While it's easy to see why Johnson outperforms Floyd-Warshall on sparse graphs, I'm noticing that Johnson's with Fibonacci Heaps does no worse than Floyd-Warshall in terms of asymptotic runtime.

More specifically, from what I see, for dense graphs we have:

  • Floyd-Warshall runs in $O(V^3)$
  • Johnson's algorithm with a Fibonacci Heap runs in $O(VE + V^2\text{lg}V$) which for a dense graph would also be $O(V^3)$

If so, what are the exact benefits of Floyd-Warshall over Johnson's? Is it runtime differences in practice? Space complexity? Something else?

To put it more bluntly (at the risk of oversimplifying this matter) could one say e.g. "Always use Johnson's over Floyd-Warshall"?.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The five lines of code for Floyd-Warshall fit on the back of a beer coaster. On the other hand I need two hours and a blackboard to start explaining Fibonacci heaps. $\endgroup$
    – Hendrik Jan
    Apr 11 '20 at 17:54

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.