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

Compute directed shortest costs with negative edges and reject only negative cycles reachable from the chosen source. An unreachable cycle cannot influence any source route.

Simple-path enumeration is expensive and separately detecting cycles complicates a baseline. Repeated relaxation shares improvements across routes. The extra pass is meaningful only when a candidate starts from a reachable vertex.

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.

Each relaxation extends a known route by one edge. Without a reachable negative cycle, a shortest simple path has at most V-1 edges. An improvement on a further full pass proves a source-reachable negative cycle. Do not relax from unreachable distance. Final O(VE) time and O(V) distance storage.

Null reachability must guard relaxation before numeric addition:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Long fromDistance = null;
        long edgeWeight = -4;
        boolean canRelax = fromDistance != null;
        assert !canRelax;
        fromDistance = 3L;
        assert fromDistance + edgeWeight == -1;
    }
}

An unreachable endpoint has no numeric cost to extend; treating absence as zero invents routes into disconnected components. After V-1 full passes, a further reachable improvement demonstrates a negative cycle rather than a merely late ordinary path.

Recognising an endlessly cheaper cycle

Bellman–Ford is useful when negative costs are legitimate and reachable-cycle detection matters. Its O(VE) bound is higher than Dijkstra, so the extra generality should match the actual edge-cost contract.

Directed weights may be negative. Return Long minimum costs and null for unreachable vertices. Reject n <= 0, invalid source/endpoints, or a source-reachable negative cycle. An unreachable negative cycle must not raise.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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