DSA & Algorithms
Part 18 of 21 · DSA Interview PatternsShortest Paths — Dijkstra, Bellman-Ford & When Not To Use Them
Dijkstra vs Bellman-Ford vs BFS-on-unweighted; negative edges and when not to.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You need a cheapest path
Prefer
Match the algorithm to the weights
Unweighted means BFS. Non-negative means Dijkstra. Negative edges mean Bellman-Ford. Dijkstra is wrong if any edge is negative.
- Binary-heap Dijkstra is O((V+E) log V).
- Bellman-Ford is O(VE), and K relaxations cap the number of edges.
- Stale heap entries must be skipped.
Alternative
Dijkstra on a graph that has a negative edge
The finalized-node assumption breaks. The distances can be wrong.
- Running Dijkstra because it is the one you remember.
- Forgetting the extra pass that detects a negative cycle.
- Pushing a neighbor again when the heap entry is already stale.
Classify the weights first
The picture is a decision, not three algorithms side by side.
- 1
Look at the weights
Missing, equal, non-negative, or negative. - 2
Pick BFS or Dijkstra
Only when no edge can improve a popped node. - 3
Otherwise Bellman-Ford
V-1 rounds, then one more round for a negative cycle.
Overview
Dijkstra vs Bellman-Ford vs BFS-on-unweighted; negative edges and when not to.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Pick algorithm by graph weight properties: BFS unweighted; Dijkstra non-negative; Bellman-Ford negatives; never Dijkstra with negatives.
Recognition cues
- network delay time
- cheapest flights within K stops (Bellman-like / DP)
- path with minimum effort
- negative cycle detection
Mental model
Decisions
- ?
1. What are the weights?
- next2. Unweighted or equal?
- ?
2. Unweighted or equal?
- yes3. BFS
- no4. Any negative edge?
- 3
3. BFS
- ?
4. Any negative edge?
- no5. Dijkstra
- yes6. Bellman-Ford
- 5
5. Dijkstra
- 6
6. Bellman-Ford
- next7. Extra pass finds a neg cycle
- 7
7. Extra pass finds a neg cycle
Lesson map
Shortest Paths — Dijkstra, Bellman-Ford & When Not To Use Them
Dijkstra vs Bellman-Ford vs BFS-on-unweighted; negative edges and when not to.
Architecture. 1. What are the weights? Ready. 2. Unweighted or equal? Ready. 3. BFS Ready. 4. Any negative edge? Ready. 5. Dijkstra Ready. 6. Bellman-Ford Ready. 7. Extra pass finds a neg cycle Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB Q["1. What are the weights? Ready"] U["2. Unweighted or equal? Ready"] BFS["3. BFS Ready"] N["4. Any negative edge? Ready"] Dij["5. Dijkstra Ready"] BF["6. Bellman-Ford Ready"] Cyc["7. Extra pass finds a neg cycle Ready"] Q -->|continues| U U -->|yes| BFS U -->|no| N N -->|no| Dij N -->|yes| BF BF -->|continues| Cyc
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- BFS: O(V+E).
- Dijkstra binary heap: O((V+E) log V).
- Bellman-Ford: O(VE).
- Floyd-Warshall all-pairs: O(V^3).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Network Delay Time
- Cheapest Flights Within K Stops
- Path With Minimum Effort
- Swim in Rising Water
- Shortest Path in Binary Matrix
- Find the City With the Smallest Number of Neighbors at a Threshold Distance
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
When BFS?
Answer
Unweighted or uniform weight edges.
Dijkstra requirement?
Answer
Non-negative edge weights.
Bellman-Ford use?
Answer
Negatives; also K-relaxations for at most K edges.
Neg cycle?
Answer
If a relaxation still improves after V-1 passes, a negative cycle is reachable from the source (seed every dist with 0 to find one anywhere).
A*?
Answer
Dijkstra ordered by g + h; optimal only with an admissible heuristic (consistent to avoid reopening nodes); common in map routing.
Why not Dijkstra on neg?
Answer
Assumption that popped node is finalized breaks.