Bellman Ford

• Based on Dijkstra’s
  • However it’s not greedy
• Allows for it to find paths with negative edge weights
• Can also detect when there is a negative edge weight cycle, however it can’t produce an answer when one is present
  • Negative weight cycle = When the weights of a cycle sum up to a negative number
• $O(EV)$

Algoritm

• Relaxes all edges at each iteration
  • Performs exactly |V| iterations
• The ith iteration finds any S-Ps with i edges
• Last iteration reveals presence of negative weight cycle
  • Should be checking that nothing changes
• The order in which you relax the edges can affect performance
  • Could have the final solution after 1 iteration, however without a way to escape the loop it would loop V times anyway

// Step 1: Initialize graph and map for distances and predecessors

// Step 2: Relax edges repeatedly 
repeat |V| - 1 times:  
	for each edge (u,v) with weight w in edges do
		if distance[u] + w < distance[v] then 
			distance[v] = distance[u] + w
			predecessor[v] = u 

// Step 3: Check for negative-weight cycles
for each edge (u,v) with weight w in edges do
	if distance[u] + w < distance[v] then
		error "Graph contains a negative-weight cycle"