bellman-ford algorithm

Summary

Bellman-Ford algorithm

• depends on how the edges are ordered

Time complexity

• average case: - relax all edges V-1 times

Early termination

• best case: - one pass to relax every edge, one pass to check
• any directed tree: bellmanford(0)

• first is shortest: bellmanford(0)

the best case is when the outgoing edges are relaxed following a topological ordering

• worse case: - only edge that can be relaxed is the last of every pass
• reversed: bellmanford(3)

Invariant

• at the kth pass, all the nodes k jumps from the source will have the correct shortest path

Concept

Algorithm

1. try to relax all the edges in the graph
2. repeat V-1 times

void bellmanford(int s) {
	dist.set(s, 0);
	
	for (int i = 0; i < V-1; ++i) { // V-1 times -> O(VE)
		for (int u = 0; u < V; ++u) // these two loops = O(E)
			if (dist.get(u) != INF) // important check, if not we risk INF + INF
				for (int[] v_w : AL.get(u)) { // e = [ v, w ]
					int v = v_w[0];
					int w = v_w[1];
					if (dist.get(u) + w >= dist.get(v)) 
						continue; // not improving, skip
					dist.set(v, dist.get(u) + w); // relax operation
				}
	}
}

any node visitable from the source is at most V-1 jumps from the source

• 6 vertex graph: bellmanford(0) - finished after 1 pass

Early termination

• keep track of whether any relaxations are done in each pass
• no relaxation implies that no other nodes can be reached form the source and all distances are the shortest

void bellmanford(int s) {
	dist.set(s, 0);
	
	for (int i = 0; i < V-1; ++i) {
		boolean modified = false; // check for relaxation
		
		for (int u = 0; u < V; ++u)
			if (dist.get(u) != INF)
				for (int[] v_w : AL.get(u)) {
					int v = v_w[0];
					int w = v_w[1];
					if (dist.get(u) + w >= dist.get(v)) 
						continue;
					dist.set(v, dist.get(u)+w);
					modified = true; // ack that relaxation has occurred
				}
		if (!modified) break; // early termination
	}
}

Dynamic programming

• DAG only
• apply topological sort to get an optimal order for the edges
• run one pass of Bellman-Ford using that order

Negative cycle detection

• after V-1 passes of bellman-ford
• do one more round, if edges can still be relaxed, then there is a negative weight cycle

Application