Relax distances without finalizing too early
Bellman–Ford computes shortest paths from a source while allowing negative edge weights. Initialize the source distance to zero and all other distances to infinity. For an edge u→v, replace d[v] when a finite d[u]+w improves it, recording u as a predecessor. This operation is relaxation. Unlike Dijkstra’s finalization step, vertices remain eligible for later improvements. An edge out of an unreachable vertex must not create a finite candidate merely through arithmetic on an infinity sentinel. Negative weights are allowed, but a reachable negative cycle requires separate handling.
A small graph and scan order
Let s→a have weight 4, s→b weight 5, and a→b weight −2. The final distances are 4 for a and 2 for b. An in-place edge scan that sees s→a before a→b may discover b’s improved distance in the same pass. Another edge order may need a later pass. Consequently, a pass in an in-place implementation does not necessarily mean that information has advanced by exactly one edge. Distinguish the bounded-edge dynamic-programming proof from the exact sequence of updates performed by the code you are tracing.
Why the extra pass matters
Without a reachable negative cycle, a shortest path can be chosen without repeated vertices, using at most V−1 edges. Repeating complete relaxation passes V−1 times therefore captures the necessary improvements. A further successful relaxation implies a negative cycle reachable from the source. A negative cycle in an unreachable component does not invalidate this source’s distances. Nor does one reachable negative cycle necessarily invalidate every vertex: unbounded improvement affects vertices that can be reached through that cycle. Report the relevant reachability scope instead of treating a cycle warning as an undifferentiated failure of the whole graph.
Analyze work and numeric safety
The basic full-edge-scan version uses O(VE) worst-case time and O(V) extra space for distances and predecessors. A pass with no changes permits early termination. Queue-based variants can reduce practical work, but do not automatically have a linear worst-case guarantee. Guard infinity arithmetic and integer overflow, which can manufacture false improvements. Floating-point weights introduce additional rounding questions. Before following predecessor links to reconstruct a path, establish reachability and rule out a relevant negative cycle; otherwise reconstruction can loop or present a path for a distance that has no finite minimum.