Bellman–Ford algorithm

The source starts at zero and other distances at infinity. Relaxing u to v checks whether the cost through u improves v, updating its distance and predecessor when appropriate.

The basic form repeatedly scans all edges, allowing improvements to propagate through successive passes. Enough passes account for shortest paths without negative-cycle repetition. Unlike standard Dijkstra, it does not permanently settle one current minimum at every step.

References: [1]

A negative edge reduces a path’s cost without necessarily destroying its minimum. Without a relevant negative cycle, a shortest path can be taken without repeated vertices and uses at most V−1 edges, motivating a finite number of relaxation passes.

Continued improvements beyond the necessary passes require checking for a reachable negative cycle. If that cycle can lead to a destination, repeated traversal lowers its cost indefinitely; reporting the obstruction is more accurate than returning a supposedly final finite distance.

References: [1]

A queue-based form processes vertices whose distances have changed, revisiting outgoing edges that can propagate improvements. An in-queue mark avoids duplicate scheduling, while correct negative-cycle detection must remain in place.

Queue optimization can reduce practical work, but the general worst-case bound remains O(VE). A fast sample does not establish a universal linear guarantee. Cycles unreachable from the source also differ from reachable obstructions, so results and diagnostics must state their query scope.

References: [1]