Advanced Topic 35 of 51 Algorithms

Bellman-Ford Algorithm

Shortest paths tolerating negative edge weights.

How it works

Bellman-Ford computes shortest paths from a source in graphs that may contain negative edge weights. It relaxes every edge V minus 1 times, because a shortest path has at most V minus 1 edges, in O(VE) time, and an extra pass that still improves a distance reveals a negative cycle reachable from the source. It builds on simple dynamic programming over path lengths.

Where it is used

Distance-vector routing protocols such as RIP, currency arbitrage detection with negative logarithms of exchange rates, graphs with penalties or rewards and difference constraints use Bellman-Ford.

Common pitfall

It is much slower than Dijkstra on non-negative graphs. With a negative cycle, shortest distances are undefined, so the algorithm must report it rather than return numbers. Stopping early when a pass makes no changes saves time. Use infinity carefully to avoid overflow when adding to unreachable nodes.

Where it fits in the course

Bellman-Ford Algorithm is topic 35 of 51 in Algorithms, rated Advanced. It follows Dijkstra's Algorithm. The next topic is Floyd-Warshall Algorithm.

Practice and explore

• Open the interactive lesson, with a mini quiz.
• Take the Algorithms quiz.
• Explore the Graph Traversal visualizer: BFS, DFS and Dijkstra on a weighted graph.

How to study this topic

1. Read the explanation above and restate the definition in your own words.
2. Open the interactive lesson and answer its mini quiz.
3. Read the common pitfall, then write a short example that avoids it.
4. Check your understanding in the Algorithms quiz, and revisit the topic if you miss a question.

Frequently asked questions

Related topics

• Dijkstra's Algorithm (Algorithms)
• Floyd-Warshall Algorithm (Algorithms)
• Topological Sort (Algorithms)
• A* Search (Algorithms)
• Shor's Algorithm (Emerging & Frontier Topics)
• Grover's Algorithm (Emerging & Frontier Topics)