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.

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.

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.

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*