- Dijkstra doesn’t work for graphs with negative weight edges, Bellman-Ford works for such graphs.
- Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems.
- But time complexity of Bellman-Ford is $O(VE)$, which is more than Dijkstra.
Steps
- Initialize d’s, π’s, and set s.d = 0 ⇒ $O(V)$
- Loop |V|-1 times through all edges checking the relaxation condition to compute minimum distances ⇒ $(|V|-1) O(E) = O(VE)$
- Loop through all edges checking for negative weight cycles which occurs if any of the relaxation conditions fail ⇒ $O(E)$
The run time of the Bellman-Ford algorithm is $O(V + VE + E) = O(VE)$.
Pseudo Code:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20BELLMAN-FORD(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
for i = 1 to |G.V|-1 # the reason using V-1 is that assuming the maximum edges for the shortest path have the V-1 hops through that path
for each edge (u,v) ∈ G.E # Note: the order of update for eadges is predifined and every iteration use the same order
RELAX(u,v,w)
for each edge (u,v) ∈ G.E
if v.d > u.d + w(u,v)
return FALSE # so no solution if detecting a negative circle
return TRUE
INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex v ∈ G.V
v.d = ∞
v.pi = NIL
s.d = 0
RELAX(u,v,w)
if v.d > u.d + w(u,v)
v.d = u.d + w(u,v)
v.pi = u # pi is the predecessor
Note that if the graph is a DAG (which means no cycles), we can make Bellman-Ford more efficient by first topologically sorting G ($O(V+E)$), performing the same initialization ($O(V)$), and then simply looping through each vertex u in topological order relaxing only the edges in Adj[u] ($O(E)$). This method only takes $O(V + E)$ time.
Reference:
https://www.programiz.com/dsa/bellman-ford-algorithm
https://www-m9.ma.tum.de/graph-algorithms/spp-bellman-ford/index_en.html