Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
After a lot of Googling, I've found that most sources say that the Dijkstra algorithm is "more efficient" than the Bellman-Ford algorithm. But under what circumstances is the Bellman-Ford algorithm better than the Dijkstra algorithm?
I know "better" is a broad statement, so specifically I mean in terms of speed and also space if that applies. Surely there is some situation in which the Bellman-Ford approach is better than the Dijkstra approach.
Answer
Bellman-Ford algorithm is a single-source shortest path algorithm, so when you have negative edge weight then it can detect negative cycles in a graph.
The only difference between the two is that Bellman-Ford is also capable of handling negative weights whereas Dijkstra Algorithm can only handle positives.
From wiki
However, Dijkstra's algorithm greedily selects the minimum-weight node that has not yet been processed, and performs this relaxation process on all of its outgoing edges; in contrast, the Bellman–Ford algorithm simply relaxes all the edges, and does this |V | − 1 times, where |V | is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra.
Dijkstra is however generally considered better in the absence of negative weight edges, as a typical binary heap priority queue implementation has O((|E|+|V|)log|V|) time complexity [A Fibonacci heap priority queue gives O(|V|log|V| + |E|)], while the Bellman-Ford algorithm has O(|V||E|) complexity