1

I'm trying to understand why anyone would prefer Floyd-Warshal over Dijkstra:

  • Dijkstra gives a correct result, using an understandable system, combined with backtracking.
  • Floyd-Warshal makes an entire list and filters in there.

The only thing I can imagine, is the case of enormous graphs, where Dijkstra only gives a solution when found, resulting in a very large time for giving a result. Floyd-Warshal, however, already starts spitting out different possibilities and tries to improve those bit by bit (e.g. based on heuristics). But if this were true, then wouldn't that be the case for Dijkstra too?

Or are there other reasons I'm not thinking of here?

For your information: the graphs I'm dealing with, are the "typical" graphs where a vehicle needs to go from one place to another, the weights of the edges are equal to the distances between the vertices (which are the points I travel by). The edges might be directional or not, both are possible (maybe this makes a difference?).

Dominique
  • 1,705
  • 2
  • 14
  • 24
  • 1
    "Floyd-Warshal, however, already starts spitting out different possibilities and tries to improve those bit by bit (e.g. based on heuristics). But if this were true, then wouldn't that be the case for Dijkstra too?" I don't understand that reasoning at all. If this is the distinguishing feature, why would it be the case for the other algorithm too? – Kilian Foth Jan 20 '23 at 09:19
  • @KilianFoth: thanks for your quick reaction. I'm a complete newbie in graph theory and I've been given the assignment to compare both algorithms. The general idea I have is that Dijkstra is very fast and it gives a correct result, while Floyd-Warshal is slower and takes a lot of resources and time. So, the only advantage I can imagine, is that Floyd-Warshal gives intermediate results, which might be helpful, while Dijkstra only gives a result at the end. Do you know if this is correct or are there other possible differences in favour of Floyd-Warshal? – Dominique Jan 20 '23 at 09:27

1 Answers1

3

Dijkstra's algorithm solves the "Single-Source-Shortest-Path" problem and can fail with negative edge weights.

Floyd-Warshall solves the "All-Pairs-Shortest-Path-Problem" and handles negative edge weights correctly.

And not to forget: Floyd-Warshall is simpler to implement (ok, that may be opinionated).

When your graph has only positve edge weights, and you are only looking for a path from one fixed starting point, Dijkstra's algorithm will be more efficient. When you need all shortest paths between all pairs of vertices, however, Floyd-Warshall might be faster than running Dijkstra's algorithm multiple times (for each starting point once). However, in terms of efficiency, both approaches can be implemented in time complexity O(V³).

When your graph has negative edge weights, Dijkstra is not an option.

You find more information here:

Doc Brown
  • 199,015
  • 33
  • 367
  • 565