1Understand
The idea
Dijkstra's algorithm always expands the closest unfinished node, taken from a priority queue. With non-negative weights, the first time a node is popped its distance is final. Skip stale heap entries whose distance is larger than the best known, and the whole search runs in O(E log V).
Intuition
Dijkstra always expands the closest unfinished node, taken from a priority queue. With non-negative weights, the first time a node is popped its distance is final.
Skip stale heap entries whose distance is larger than the best known, Python's heapq has no decrease-key, so lazy deletion is normal. Negative weights need Bellman-Ford instead.
The result is shortest distances (and parents, if you store them) from the source.
What you will be able to do
- Skip stale heap entries
- Know why negative weights break it
When to use it
- Weighted edges, cheapest / fastest route
- Network delay time
- Minimum effort path on a grid
2See it
Walkthrough
Dijkstra from s
Edges 0-1:1, 0-2:4, 1-2:1, relax with a min-heap.
1 / 5
dist[0]=0; push (0, node). Greedy: finalize the closest unsettled node.
Live template
Line 1 active
Complexity: time O((V + E) log V), space O(V + E)
O((V + E) log V) with a binary heap. BFS only if all weights are equal. Floyd-Warshall O(V³) for all pairs on dense graphs. Negative edges → Bellman-Ford O(VE).
Read the walkthrough as text
Classic diamond. Nodes A,B,C,D with edges A→B:1, A→C:4, B→C:2, B→D:5, C→D:1. Source A.
- Dist: A0, others ∞. Pop A; relax B→1, C→4.
- Pop B (dist 1); relax C→min(4,1+2)=3, D→6.
- Pop C (dist 3); relax D→min(6,3+1)=4.
- Pop D with 4, final. Path A-B-C-D.
Never re-process a node after it was popped with its best distance.
3Recognise it
Kinds of problems (5)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Single-source shortest paths
Example. Dijkstra from source s to all nodes with non-negative weights.
How. Min-heap (dist, node); relax neighbours when d+w improves; skip stale pops.
Minimum effort / bottleneck path
Example. Minimise maximum edge weight on a path.
How. Dijkstra on max edge so far, or union-find on sorted edges until connected.
Shortest path with at most k stops (Bellman-Ford style)
Example. Cheapest flight with ≤ k layovers.
How. Relax all edges for k+1 rounds, or DP[stops][v] from previous layer.
Shortest path on a weighted grid
Example. Minimum effort path in a grid of heights.
How. Dijkstra with 4-neighbour moves and effort = max step height difference.
All-pairs shortest paths (Floyd–Warshall)
Example. Min distance between every pair of nodes.
How. Triple loop: for each via k, relax dist[i][j] through k; k is outermost.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Stale entries processed
Why it happens. Old (dist, node) pairs look harmless if you still relax edges.
How it fails. Pop (5, u) when dist[u] already 3, redundant relaxations explode queue size.
Fix. On pop: `if d > dist[u]: continue` before relaxing neighbours.
BFS on weighted graph
Why it happens. BFS found shortest paths on unweighted grids before.
How it fails. Weights 1 and 10: BFS treats both as one step, path cost 2 instead of 11.
Fix. Non-uniform weights need Dijkstra (or Bellman-Ford if negatives).
Negative weights
Why it happens. Dijkstra is the default “shortest path” algorithm.
How it fails. Edge weight −5 makes Dijkstra pick wrong order, distances never corrected.
Fix. Negative weights → Bellman-Ford or SPFA; not plain Dijkstra.
Intermediate node in the inner loop
Why it happens. Nested i,j inside k still visits all triples.
How it fails. k innermost: paths using intermediate high-index nodes never considered in later k.
Fix. Floyd-Warshall: k (intermediate) is the outer loop, then i, j.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.