73

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.

Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
crazyCoder
  • 1,552
  • 3
  • 20
  • 25
  • 6
    When there are negative-weighted edges in the graph, because then Dijkstra isn't guaranteed to work. Not only will Bellman-Ford not break for negative-weighted edges, it will also tell you (at least you can derive that information from it) if there is a negative-weighted cycle in the graph. – G. Bach Oct 20 '13 at 20:14

8 Answers8

80

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

VahidNaderi
  • 2,448
  • 1
  • 23
  • 35
Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
  • So there is no advantage in terms of running speed between these two approaches? – crazyCoder Oct 20 '13 at 20:43
  • 16
    I would say that Dijkstra is preferred as the typical implementation with binary heap has Theta((|E|+|V|)log|V|) time complexity, while Bellman-Ford algorithm has O(|V||E|) complexity. – Rahul Tripathi Oct 20 '13 at 20:47
  • 6
    I doubt binary heap is the preferred implementation, Fibonacci heaps give better amortized complexity. – G. Bach Oct 20 '13 at 22:58
  • 1
    Also note than you can use Bellman-Ford-Moore to detect and remove negative weight cycles and then use Dijkstra. This is Johnson's algorithm : http://en.wikipedia.org/wiki/Johnson's_algorithm – Snicolas Dec 07 '13 at 17:30
  • "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." Inuitively , this is the key difference. Greedy vs exhaustive search. – chia yongkang Mar 26 '22 at 04:30
  • @snicolas can you point to an explanation or example of this? My understanding is the Johnson's algorithm depends on Bellman-Ford (aka Bellman-Ford-Moore), and that B-F can only detect negative cycles. I can imagine a repeated application of B-F to find and remove all negative cycles but that's not what Johnson's does. – Chris Johnson Jan 16 '23 at 17:48
15

As already stated in the chosen answer, Bellman-Ford performs the check on all the vertices, Dijkstra only on the one with the best distance calculated so far. Again already noted, this improves the complexity of the Dijkstra approach, however it requires to compare all the vertices to find out the minimum distance value. Being this not necessary in the Bellman-Ford, it is easier to implement in a distributed environment. That's why it is used in Distance Vector routing protocols (e.g., RIP and IGRP), where mostly local information is used. To use Dijkstra in routing protocols, instead, it is necessary first to distribute the entire topology, and this is what happens in Link State protocols, such as OSPF and ISIS.

Saurabh
  • 5,176
  • 4
  • 32
  • 46
Halberdier
  • 1,164
  • 11
  • 15
  • 1
    +1 (on the distributed computation benefits to Bellman-Ford). My only quibble with this answer is that it would be best to clarify what you mean by _"check"_ when you say _"Bellman-Ford performs **the check** on all the **vertices**, Dijkstra only on the one with the best distance calculated so far"_. Do you mean the **relax** operation? (if so, that's technically more than just a check, and it's technically done on edges, not on single vertices). Or maybe do you mean something else? – Amelio Vazquez-Reina Apr 06 '20 at 23:44
  • 1
    Yes, you are right. I meant the relaxation phase. In Dijkstra, only the edges outgoing from the "best" vertex are checked and possibly updated, in Bellman-Ford this is done for all the edges in the network. Probably I should rephrase better. – Halberdier Jun 10 '20 at 08:29
6

There are 4 major difference among them I know:- 1. bellman time complexity is O(VE) and Dijkstra Algo has O(ElogV)in case of maxheap is used.

  1. Bellman does relaxation for n-1 times and Dijkstra Algo only 1 time.
  2. Bellman can handle negative weights but Dijkstra Algo can't.
  3. Bellman visit a vertex more then once but Dijkstra Algo only once.
Apporva Arya
  • 61
  • 1
  • 2
5

The only difference is that Dijkstra's algorithm cannot handle negative edge weights which Bellman-ford handles.And bellman-ford also tells us whether the graph contains negative cycle. If graph doesn't contain negative edges then Dijkstra's is always better.

An efficient alternative for Bellman-ford is Directed Acyclic Graph (DAG) which uses topological sorting.

http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

Rahul Bagad
  • 115
  • 2
  • 7
  • 16
    A DAG is a type of graph, while topological sorting is a component of the algorithm linked to. A DAG is not an algorithm. – hbd Mar 27 '17 at 19:29
2

Dijkstra Algo
Dijkstra algo is not capable to differentiate between Negative edge weight cycle is present in graph or not

1. Positive edge weight:- Dijkstra always PASS if all edge weight in a graph is positive
2. Negative edge wt. and No -ve edge wt. cycle:- Dijkstra always PASS even if we have some edges weight as Negative but NO cycle/loop in graph having negative edge weight.
[i.e No Negative edge weight cycle is present]
3. Negative edge wt. and -ve edge wt. cycle:- Dijkstra may PASS/FAIL even if we have some edges weight as negative along with cycle/loop in graph having negative edge weight.

Ajay
  • 176
  • 6
1

In a normal introduction to algorithm class, you will learn that the only difference between Dijkstra and Bell-man Ford, is that the latter works for negative edges at the cost of more computation time. The discussion on time complexity is already give in the accepted answer.

However I want to emphasize and add a bit more to @Halberdier's answer that in a distributed system, Bellman-Ford is implemented EVEN WHEN ALL EDGES ARE Positive. This is because in a Bellman-Ford algorithm, the entity S does not need to know every weight of every edge in the graph to compute the shortest distance to T - it only needs to know the shortest distance for all neighbors of S to T, plus the weight of S to all its neighbors.

A typical application of such algorithm is in Computer Networking, where you need to find the shortest route between two routers. Dijkstra is implemented in a centralized manner called link state Routing, while Bellman-Ford allows each router to update themselves asynchronously, called distance-vector routing.

I believe no one explains better than Jim Kurose, the author of <Computer Network, a top-down approach>. See his youtube videos below.

Link State routing: https://www.youtube.com/watch?v=bdh2kfgxVuw&list=TLPQMTIwNjIwMjLtHllygYsxMg&index=3

Distance Vector routing: https://www.youtube.com/watch?v=jJU2AVX6gpU&list=TLPQMTIwNjIwMjLtHllygYsxMg&index=4

1
Bellman Ford’s Algorithm Dijkstra’s Algorithm
Bellman Ford’s Algorithm works when there is a negative weight edge, it also detects the negative weight cycle. Dijkstra’s Algorithm may or may not work when there is a negative weight edge. But will definitely not work when there is a negative weight cycle.
The result contains the vertices which contain the information about the other vertices they are connected to. The result contains the vertices containing whole information about the network, not only the vertices they are connected to.
It can easily be implemented in a distributed way. It can not be implemented easily in a distributed way.
It is more time-consuming than Dijkstra’s algorithm. Its time complexity is O(VE). It is less time-consuming. The time complexity is O(E logV).
Dynamic Programming approach is taken to implement the algorithm. Greedy approach is taken to implement the algorithm.
Bellman Ford’s Algorithm has more overheads than Dijkstra’s Algorithm. Dijkstra’s Algorithm has less overheads than Bellman Ford’s Algorithm.
Bellman Ford’s Algorithm has less scalability than Dijkstra’s Algorithm. Dijkstra’s Algorithm has more scalability than Bellman Ford’s Algorithm.

Source 1

zangw
  • 43,869
  • 19
  • 177
  • 214
-7

I do not agree completely, difference is in implementation and complexity, Dijsktra's algorithm is faster (O(n^2)) but difficult to implement, while Bellman Ford complexity is O(n^3) but is easier to implement.

12K
  • 29
  • Bellman Ford has complexity O(n*m) where n is number of vertices, and m is number of edges. I think you are thinking of Floyd Warshall which has complexity O(n^3). – JasoonS Aug 13 '16 at 22:09
  • @JasoonS I think what he meant is |E| = |V|^2 for worst case ( where E is edge and V is vertice ) so technically he is right. – ck reddy Dec 04 '16 at 09:32