Bellman-Ford Algorithm

[box-lin]

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.

Bellman-Ford Algorithm

• For a start node, relax each edge for V -1 times. Relaxation is defined as if d[u] + c(u,v) < d[v] then d[v] = d[u] + c(u,v).
• Time: O(EV)
• Space: O(V)

d = [math.inf] * len(V)
d[start] = 0
for i in [0, V-1]:
   for u,v in edges:
       # Relaxation
       if d[u] + c(u,v) < d[v]:
             d[v] = d[u] + c(u,v)

# detect for negative cycle
for i in [0, V-1]:
   for u,v in edges:
       # Relaxation
       if d[u] + c(u,v) < d[v]:
             # has a negative cycle
             d[v] = -math.inf  

Problems that can be solve by Bellman-Ford Algorithm

• 1514 Path with Maximum Probability