Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?

I’ve been studying the three and I’m stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.

  1. Dijkstra algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails in cases like this.

  2. Floyd-Warshall algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles.

  3. Bellman-Ford is used like Dijkstra, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall except for one source, right? (This is the one I am least sure about.)

Answer

Dijkstra’s algorithm is used only when you have a single source and
you want to know the smallest path from one node to another, but fails
[in graphs with negative edges]

Dijkstra’s algorithm is one example of a single-source shortest path or SSSP algorithm. Every SSSP algorithm computes the shortest-path distances from a chosen source node s to every other node in the graph. Moreover, it computes a compact representation of all the shortest paths from s to every other node, in the form of a rooted tree. In the Wikipedia code, previous[v] is the parent of v in this tree.

The behavior of Dijkstra’s algorithm in graphs with negative edges depends on the precise variant under discussion. Some variants of the algorithm, like the one in Wikipedia, always runs quickly but do not correctly compute shortest paths when there are negative edges. Other variants, like the one in Jeff Erickson’s lecture notes always compute shortest paths correctly (unless there is a negative cycle reachable from the source) but may require exponential time in the worst case if there are negative edges.

Floyd-Warshall’s algorithm is used when any of all the nodes can be a
source, so you want the shortest distance to reach any destination
node from any source node. This only fails when there are negative
cycles.

That’s correct. Floyd-Warshall is one example of an all-pairs shortest path algorithm, meaning it computes the shortest paths between every pair of nodes. Another example is “for each node v, run Dijkstra with v as the source node”. There are several others.

Bellman-Ford is used like Dijkstra’s, when there is only one source.
This can handle negative weights and its working is the same as
Floyd-Warshall’s except for one source, right?

Bellman-Ford is another example of a single-source shortest-path algorithm, like Dijkstra. Bellman-Ford and Floyd-Warshall are similar—for example, they’re both dynamic programming algorithms—but Floyd-Warshall is not the same algorithm as “for each node v, run Bellman-Ford with v as the source node”. In particular, Floyd-Warshall runs in O(V3) time, while repeated-Bellman-Ford runs in O(V2E) time (O(VE) time for each source vertex).

For further details, consult your favorite algorithms textbook. (You do have a favorite algorithms textbook, don’t you?)

Attribution
Source : Link , Question Author : Community , Answer Author : M.S. Dousti

Leave a Comment