Bellman-Ford Algorithm

This is basically Dijkstras Algorithm but slower and more robust (can work with negative edges).

procedure bellman-ford(G,l,s)
Input: a graph G = (V, E) (directed or undirected); edge lengths l_e for each e in E (with no negative cycles); and a start vertex s in V
Output: For all u reachable from s, dist(u) is set to the distance from s to u  
	for all u in V:
		dist(u) = inf
	dist(s) = 0
	repeat |V| -1 1 times  
		for all edges e in E:
			update(e)  
	end

Where update is defined as…

procedure update(u,v)
Input: an edge (u,v) in E and the values dist(u), dist(v) and l(u,v)
Output: An updated distance for vertex v
	dist(v) = min{dist(v), dist(u)+l(u,v)}

This gives the correct dist to v if:

1. u is the second last vertex on the shortest path from s to v
2. dist(u) is set correctly dist(v) is always an overestimate, or is correct (no matter what edges update is performed on).

A sequence of at most $V-1$ updates are needed before dist(v) is correct.

Note that we can also add in prev pointers to keep track of the path as we go.

The runtime here is $O(V\cdot E)$

Negative Cycles

This is when a weight in a cycle is less than the sum of the other weights so we have a cycle that approaches $-\infty$. We can modify bellman-ford to detect the presence of negative cycles.

1. Perform $V$ iterations of the repeat loop instead of $V-1$
2. If some dist value changes in the $Vth$ iteration, there is a negative cycle