difference between Bellman Ford and Dijkstra's algorithm

Question

   2           1
1----------2---------4
|          |         |
|3         |3        |1
|    6     |         |
3---------5 ---------

Ok, so this is the graph. My source node is 1 and destination node is 5

My question is.

Are both the algorithms going to give the same output or not? That is, will both return 1->2->4->5? (Except that negative weights are not allowed in dijkstra's)

Thanks in advance for help.

Answer 1

Bellman-Ford algorithm is a single-source shortest path algorithm, which allows for negative edge weight and can detect negative cycles in a graph.

Dijkstra algorithm is also another single-source shortest path algorithm. However, the weight of all the edges must be non-negative.

For your case, as far as the total cost is concerned, there will be no difference, since the edges in the graph have non-negative weight. However, Dijkstra's algorithm is usually used, since the typical implementation with binary heap has Theta((|E|+|V|)log|V|) time complexity, while Bellman-Ford algorithm has O(|V||E|) complexity.

If there are more than 1 path that has minimum cost, the actual path returned is implementation dependent (even for the same algorithm).