Bellman-Ford algorithm

Suppose we are trying to solve the problem of how to Find path in undirected graph where we have no negative weight cycles.

In this case you can guarantee that paths will only visit each vertex at most once. So they will use at most edges. So it is enough to solve the subproblem.

Let be the length of the shortest path between and that use at most edges.

Base case: with for .

Recursion: Let .

Solution:

Pseudocode

For this let

D(0,s) = 0
D(0,z) = inf for all z /= s
for i=1 -> n-1
	for all z in V
		D(i,z) = D(i-1,z)
		for (y,z) in E:
			D(i,z) = min(D(i,z), w(y,z) + D(i-1,y))
return D(n-1, . )

The update equation used in the pseudocode is called the Bellman-Ford equation. This has applications in distributed path finding algorithms.

Run time

This takes as you could rewrite this psudo-code like this:

D(0,s) = 0
D(0,z) = inf for all z /= s
for i=1 -> n-1
	D(i,z) = D(i-1,z) for all z
	for all (x,y) in E
		D(i,y) = min(D(i,y), w(x,y) + D(i-1,x))
return D(n-1, . )