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 edge repeatedly. A shortest simple path uses at most V-1 edges, so V-1 complete passes suffice when no reachable negative cycle exists. A further possible improvement witnesses such a cycle. An early pass with no change proves later passes cannot help.

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.

std::optional<Int> unreachable;
// Relax (u,v,w) only when distance[u] is engaged.

Recognising an endlessly cheaper cycle

An unreachable negative cycle is irrelevant to a single-source result. Relaxing from a numeric infinity sentinel can accidentally make it appear reachable after subtracting a negative weight. Optional reachability prevents that mistake. Parallel edges and self-loops need no special selection logic; a negative reachable self-loop is a cycle witness. O(VE) runtime is slower than Dijkstra but permits negative weights. Retain exact signed costs and do not substitute floating-point infinity for finite integer answers. The prototype may enumerate simple paths and separately inspect reachable cycles, because path enumeration alone cannot detect unbounded improvement.

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.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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