Dijkstra¶
Also known as: Shortest Path with Weights, Priority-Queue BFS
BFS explores in rings because every step costs the same. When steps cost different amounts, replace the queue with a priority queue so you always expand the cheapest-known node next. That one substitution is the whole algorithm.
Before you start¶
- Top K Elements (you already know priority queues — this is their application to pathfinding)- Graph Traversal (BFS on unweighted graphs — Dijkstra is BFS with a priority queue)
What 'solved properly' looks like
Target: O(E log V). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You start at the source node with distance 0. You use a min-heap (priority queue) keyed by distance, always pulling out the node with the smallest known distance. For each neighbour, you compute the new distance through the current node. If it's smaller than any previously known distance, you update it and push the neighbour onto the heap. When a node is popped, you've found its shortest path — because any other path would require a longer first step.
Why it matters: Dijkstra is the foundation of all weighted shortest-path algorithms. GPS navigation, network routing, and video-game pathfinding all use variants of it. Understanding it means understanding why BFS fails on weighted graphs and how a priority queue fixes it.
When to reach for it¶
Reach for it when edges carry non-negative weights (including zero) and you need the minimum cost or time to reach a destination — network delay, cheapest route, a grid where moving between cells has a cost.
When not to use it
It breaks on negative edge weights — that's Bellman-Ford's job. If every weight is identical, plain BFS is simpler and faster, so check before reaching. And if there's a constraint on the number of hops (like "within K stops"), Dijkstra alone is insufficient — the state needs to carry the hop count.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Network Delay Time | LeetCode | Medium | 25 mins | teaching |
| 2 | Path with Minimum Effort | LeetCode | Medium | 30 mins | teaching |
| 3 | Cheapest Flights Within K Stops | LeetCode | Medium | 35 mins | consolidation |
| 4 | Swim in Rising Water | LeetCode | Hard | 40 mins | challenge |
Already know this? Test out.
If you can solve Swim in Rising Water cleanly in one sitting — using Dijkstra (or a priority-queue BFS) on a grid with varying elevations — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.