25
$\begingroup$

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.)

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome! I edited out the redundant code parts; people can click through to Wikipedia on their own, or check the algorithms in their favorite textbooks. Note that your question is a weird one to ask, because a "yes" answer can consist of nothing more. $\endgroup$
    – Raphael ♦
    Jul 29, 2012 at 13:59

4 Answers 4

Reset to default
29
$\begingroup$

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(V^3)$ time, while repeated-Bellman-Ford runs in $O(V^2E)$ 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?)

Improve this answer
$\endgroup$
3
3
$\begingroup$

The Wikipedia page on the shortest path problem describes two different problems: SSSP and APSP.

Single source shortest path (SSSP):

  • Dijkstra's algorithm: solves the single-source shortest path problem.
    • Constraints: Only Negative edges it cannot handle.
    • Unweighted graphs: Dijkstra's is the same as BFS.

  • Bellman–Ford algorithm: solves the single-source problem if edge weights may be negative. This is improvement on Dijkstra where it is now able to handle negative weights as well.

All pair shortest path (APSP):

  • Floyd–Warshall algorithm: solves all pairs shortest paths. Handles both positive and negative edges.
    • Constraints: Cannot handle negative cycles.

Hence, Floyd–Warshall is not the same as BFS, although the underlying methodology is same, dynamic programming.

Improve this answer
$\endgroup$
2
$\begingroup$

All three algorithms are covered in the lecture slides by Prof. Jaehyun Park (Stanford University). Here is the link Shortest Path Algorithms

Improve this answer
$\endgroup$
1
  • $\begingroup$ This doesn't answer the question about the differences and is not self-contained, just a link without summary does not count as good answer. Also it seems redundant, as it does not cover more than existing answers. $\endgroup$
    – Evil
    Aug 20, 2017 at 16:48
2
$\begingroup$

Perhaps this should be a comment rather than an answer, but it is a distinction between these algorithms that other answers don't mention.

People tend to call Floyd's algorithm Floyd-Warshall, but Floyd's and Warshall's algorithms are not the same.

Warshall's paper observes that if you use Floyd's algorithm on a binary incidence matrix, what you're doing is matrix multiplication; hence, it can actually be implemented that way, and e.g. if you can do the vector multiplication in $O(1)$, your algorithm becomes $O(n^2)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.