Algorithms and data structures · Intermediate

Bellman–Ford: relax edges when weights can be negative

Trace repeated edge relaxation and explain why an extra successful pass detects a reachable negative cycle.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Relax distances without finalizing too early
  2. A small graph and scan order
  3. Why the extra pass matters
  4. Analyze work and numeric safety
  5. Ask Logeia about this articleCheck your understanding

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.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path