Bellman-Ford Algorithm

Negative Weights & Cycles

1:00

How to find single-source shortest paths on graphs with negative edge weights, and how to detect negative cycles using one extra relaxation pass.

By the end, you can

Explain why Dijkstra fails with negative edge weights and what Bellman-Ford does differently.
Apply the relaxation rule by hand for a given edge and current distances.
Trace Bellman-Ford round by round on a small graph and read the distance table after each pass.
State why V−1 rounds are always sufficient for graphs without negative cycles.
Identify when early termination is safe and why it is correct.
Describe how the V-th pass detects a negative cycle and distinguish a negative edge from a negative cycle.
Compare Bellman-Ford and Dijkstra on time complexity and applicability, and choose the right one for a given scenario.
Explain the currency-arbitrage application and why a negative cycle in the transformed graph means a risk-free profit.

Up next in Algorithms & Graph Algorithms