Dijkstra with a Heap
Greedy shortest paths on non-negative edges.
Dijkstra with a Heap is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Shortest-Path Problem
You want the cheapest route from one node to every other node. Dijkstra solves this when every edge weight is zero or positive.
The Greedy Idea
Dijkstra is greedy: it always expands the unvisited node with the smallest known distance, trusting that distance is final.
Why a Min-Heap
To grab the closest node fast, you need a min-heap. It hands you the smallest distance in log n time instead of a slow scan.
import heapqStart With Distances
Set every distance to infinity, then make the source zero. Unreached nodes simply stay at infinity forever.
dist = [float('inf')] * n
dist[src] = 0Seed the Heap
Push the source as a tuple of (distance, node). Putting distance first lets the heap order entries by cost automatically.
pq = [(0, src)]Pop the Closest Node
Each loop, pop the smallest (d, u). That d is the shortest distance to u, so its work is done once popped.
d, u = heapq.heappop(pq)Skip Stale Entries
A node may sit in the heap with an old, larger distance. Skip it when d is worse than the stored distance.
if d > dist[u]:
continueRelax the Neighbors
Relaxation means trying to improve a neighbor: if going through u is cheaper, update its distance and push it.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))Lazy Deletion Trick
Python heaps cannot update a key, so you push duplicates and ignore stale ones. This lazy style keeps the code short and fast.
The Running Time
With a binary heap, Dijkstra runs in O((V + E) log V). That easily handles graphs with hundreds of thousands of edges.
Watch the Edge Weights
Dijkstra breaks on negative edges, since a popped distance may not be final. For those, reach for Bellman-Ford instead.
Quick Check
You pop (d, u) but d is greater than dist[u]. What should you do?
Recap: Dijkstra With a Heap
You init distances, push (dist, node), pop the closest, skip stale pops, and relax neighbors. That is Dijkstra in O((V+E) log V). 🚀
Frequently asked questions
Is the “Dijkstra with a Heap” lesson free?
Yes — the full text of “Dijkstra with a Heap” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Dijkstra with a Heap”?
Greedy shortest paths on non-negative edges. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Dijkstra with a Heap” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra with a Heap
- 0-1 BFS with a Deque
- Bellman-Ford & Negative Edges
- Floyd-Warshall All-Pairs