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 supports directed negative edge weights by repeatedly relaxing every edge. When no reachable negative cycle exists, a cheapest route can be chosen simple and therefore uses at most V-1 edges. Repeated passes eventually propagate all such routes.

The prototype may enumerate simple paths, but path enumeration alone cannot detect a route whose cost decreases without bound. Reachable cycles require a separate check.

Letting improvements cross another edge

Relax an edge only when its starting vertex is reachable. After V-1 passes, one additional possible improvement signals a source-reachable negative cycle. A pass with no change proves further passes cannot help, allowing early termination. In-place relaxation may propagate more than one edge in one pass; V-1 complete passes are still sufficient.

Reachability is part of the error condition. A negative cycle in another disconnected component cannot affect this source's distances and must not throw. A reachable negative self-loop is already a cycle witness. Skip null distances before adding a weight: JavaScript would otherwise coerce null to zero and invent reachability.

Keep finite costs as exact safe-integer Numbers under this lesson's input domain, and preserve null only for absence. Do not output Infinity as an unreachable marker. Parallel edges are handled by the same relaxation rule without discarding potentially cheaper costs.

const distance = [0, null, 5];
const [from, to, weight] = [1, 2, -9];
console.log(distance[from] === null); // true: this edge cannot relax yet
console.log(distance[to]); // 5: an unreachable origin must not invent a cheaper route

Recognising an endlessly cheaper cycle

Final repeated relaxation costs O(V + VE) time with O(V) distance state beyond edges. Use it for negative-weight single-source paths or as a simple correctness baseline. For nonnegative sparse graphs, Dijkstra is usually a better fit. Global cycle detection and all-pairs distances have broader scope than this single-source contract.

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