Bellman–Ford shortest paths

A workflow simulator charges for some transitions and credits others. A route that looks expensive partway through may become cheap after a later credit, so settling that intermediate cost too early can miss the best result.

Bellman–Ford repeatedly revisits the edges instead. It also exposes a more serious modelling issue: a reachable cycle that earns more credit each time around has no finite cheapest route through it.

Allowing credits in a workflow cost model

Bellman–Ford relaxes every directed edge repeatedly. After i passes, distances cover paths of at most i edges. Without a reachable negative cycle, a cheapest path can be simple, so n-1 passes suffice.

Letting improvements cross another edge

Consider edges listed as 1 → 2: -2, 0 → 1: 4, and 0 → 2: 7. The first pass can't use the first edge yet; later edges make 1 reachable. The next pass improves 2 from seven to two. Edge order can let an in-place pass propagate farther, so the guarantee is at least one more edge of progress, not exactly one.

value := func(n int) *int { return &n }
edges := [][3]int{{1, 2, -2}, {0, 1, 4}, {0, 2, 7}}
distance := []*int{value(0), nil, nil}
for pass := 0; pass < 2; pass++ {
	for _, edge := range edges {
		u, v, weight := edge[0], edge[1], edge[2]
		if distance[u] == nil {
			continue
		}
		candidate := *distance[u] + weight
		if distance[v] == nil || candidate < *distance[v] {
			distance[v] = value(candidate)
		}
	}
}
fmt.Println(*distance[1], *distance[2]) // 4 2 after both passes.

Recognising an endlessly cheaper cycle

A further improvement from a reachable vertex proves a reachable negative cycle. An isolated negative cycle does not affect this source. Never relax from an unreachable sentinel; adding a negative edge to an invented infinity can manufacture a false route. The slower algorithm supports signed edge weights. Build private working state. The Go API uses nil for absence and assumes finite cost arithmetic fits int.

Initializing V distances and scanning E edges up to V-1 times takes O(V+VE) time, plus an extra cycle-detection scan. Distances use O(V) state beyond the edge list. A pass with no changes can stop early. Negative edges in an unreachable component must remain unreachable from this source.

Running more passes cannot turn the simulator’s reachable negative cycle into a finite cheapest route.