Students often learn Dijkstra as 'BFS but with a priority queue', which is accurate and explains nothing. The interesting question is why the substitution is necessary — and the answer tells you exactly when each algorithm is the right one.
What BFS is really exploiting
Both algorithms work the same way: repeatedly take the closest unfinalised node, mark it finalised, and relax its edges. The correctness of that greedy step needs one thing — that the node you pull really is the closest remaining. Get that wrong and you finalise a node before its shortest path has been found.
In an unweighted graph, BFS gets it for free. Nodes enter the queue in non-decreasing order of distance, because every edge adds exactly one. A plain FIFO queue is therefore already a priority queue whose priorities happened to arrive in sorted order.
BFS's queue is a priority queue that gets to be free, because all the priorities happen to arrive in order.
Where weights break it
Now let edges carry different costs. Take A → B with weight 10 and A → C with weight 1, then C → B with weight 2. BFS enqueues B and C in that order and would finalise B at distance 10, before ever discovering that going through C reaches B at distance 3. Insertion order no longer matches distance order, so the greedy step is no longer justified.
The heap restores the property by force: it hands back the smallest tentative distance regardless of when it was inserted.
The stale-entry line
That continue is not an optimisation, it is the whole lazy-deletion strategy. Binary heaps do not support decrease-key efficiently, so instead of updating an existing entry you push a new one and ignore outdated pops. The heap may hold O(E) entries rather than O(V), which is why the bound is O(E log E) — equivalently O(E log V), since E is at most V².
Why negative weights kill it
Dijkstra's greedy step assumes that once a node is finalised, no later path can improve it — which requires that extending a path never reduces its cost. A negative edge violates that directly: a longer route can come back cheaper, and a node finalised early is simply wrong. No amount of care with the heap fixes it; the assumption is gone.
Bellman–Ford drops the greedy step entirely and relaxes every edge V−1 times, which costs O(VE) and tolerates negative weights — and detects negative cycles, because a V-th round that still improves something proves one exists.
Choosing between them
- →Unweighted, or all weights equal — BFS. O(V + E), no heap.
- →Weights in {0, 1} — 0-1 BFS with a deque. Push zero-weight edges to the front. Still O(V + E).
- →Non-negative weights — Dijkstra with a binary heap. O(E log V).
- →Negative weights possible — Bellman–Ford. O(VE), plus negative-cycle detection.
- →All-pairs on a small dense graph — Floyd–Warshall. O(V³), trivial to write.
The 0-1 case is worth knowing
It shows the principle clearly. With only weights 0 and 1, a deque suffices: zero-weight relaxations go to the front, one-weight to the back, and the deque stays sorted by construction. You have rebuilt exactly the property BFS had for free, using the cheapest structure that can still hold it. The heap is what you fall back to when no such trick exists.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.