Why This Matters
Shortest-path bugs often come from using Dijkstra on a graph that violates its assumptions. The edge-weight condition is not a detail; it is the proof.
Decision Rule
Use Dijkstra when all edge weights are nonnegative. Use Bellman-Ford when negative edges may appear or when the task asks whether a reachable negative cycle exists.
Comparison Table
| Feature | Dijkstra | Bellman-Ford |
|---|---|---|
| Edge weights | requires nonnegative weights | allows negative weights |
| Negative cycle detection | no | yes, if reachable from source |
| Common complexity | O((V + E) log V) with heap | O(VE) |
| Core operation | extract minimum then relax outgoing edges | relax every edge repeatedly |
| Best use | routing with nonnegative costs | arbitrage-style cycles, constraint systems |
Worked Example
Suppose edges are S -> A = 2, S -> B = 5, and B -> A = -10. Dijkstra can settle A too early at distance 2, then later discover a better path S -> B -> A = -5.
Bellman-Ford repeatedly relaxes all edges, so it can correct earlier distance estimates and then run one extra pass to detect a reachable negative cycle.
Common Mistakes
| Mistake | Correction |
|---|---|
| Thinking Dijkstra works with "only a few" negative edges. | One negative edge can break the settled-distance invariant. |
| Using Bellman-Ford when all weights are nonnegative and performance matters. | Dijkstra is usually the better fit. |
| Treating a negative edge as a negative cycle. | A negative cycle is a cycle whose total weight is negative. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which algorithm detects reachable negative cycles? | Bellman-Ford. |
| Why is Dijkstra faster on many sparse graphs? | The heap extracts the next best frontier vertex efficiently. |
| What assumption makes Dijkstra's settled set valid? | Nonnegative edge weights. |
Exercises
- Beginner: Choose the algorithm for a road map with positive distances.
- Beginner: Choose the algorithm for currency exchange with possible arbitrage.
- Beginner: Explain why negative cycle means no finite shortest path.
- Intermediate: Build a tiny graph where Dijkstra fails because of a negative edge.
- Intermediate: Implement Bellman-Ford negative-cycle detection.
- Challenge: Explain how difference constraints reduce to shortest paths with Bellman-Ford.
References
- MIT OpenCourseWare. 6.006 Lecture 16: Dijkstra, Fall 2011: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-16-dijkstra/
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015: https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/