Dijkstra's Algorithm with a Priority Queue
Implement Dijkstra using heapq, trace the relaxation steps on a weighted graph, and solve cheapest-flights-within-k-stops.
Dijkstra's Algorithm with a Priority Queue is a free Coding Interview Prep lesson on CoddyKit. This is 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, and your progress syncs across the web and the CoddyKit app. The Coding Interview Prep course includes 4 lessons in total.
Shortest Path in Weighted Graphs
Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. It works by greedily processing nodes in order of their current best-known distance — always expanding the nearest unvisited node. The key data structure is a min-heap (priority queue) that efficiently retrieves the node with the smallest distance.
Algorithm Steps Overview
Dijkstra's algorithm: (1) Initialise dist[source] = 0 and dist[all others] = inf. (2) Push (0, source) onto a min-heap. (3) Pop the node u with smallest distance. If it has already been visited with a smaller distance, skip it. (4) For each neighbour v of u: if dist[u] + weight(u,v) < dist[v], update dist[v] and push (dist[v], v) to the heap. (5) Repeat until heap is empty.
Python Implementation with heapq
Python's heapq implements a min-heap. We represent the graph as an adjacency list: graph[u] = [(v, weight), ...]. The heap stores (distance, node) tuples. We use a visited set to skip stale heap entries — entries pushed before a better path was found.
import heapq
def dijkstra(graph, source):
n = len(graph)
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)] # (distance, node)
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distWorked Example
Consider a graph with 5 nodes and edges: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Shortest paths from node 0: to 1 via 0→2→1 costs 3, to 2 costs 1, to 3 via 0→2→1→3 costs 4, to 4 via 0→2→1→3→4 costs 7. Dijkstra finds all of these in one pass, not just the path to a single target.
import heapq
def dijkstra(graph, source):
dist = [float('inf')] * len(graph)
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = [
[(1,4),(2,1)], # 0
[(3,1)], # 1
[(1,2),(3,5)], # 2
[(4,3)], # 3
[] # 4
]
print(dijkstra(graph, 0)) # [0, 3, 1, 4, 7]Why Dijkstra Fails on Negative Weights
Dijkstra's correctness relies on the fact that once a node is popped from the min-heap, its distance is final. This holds only if edge weights are non-negative. With a negative edge u→v of weight -5, after visiting v we might find a path through u that is shorter — but v is already marked visited. A single negative edge can invalidate all subsequent distance calculations.
Cheapest Flights Within K Stops (LeetCode 787)
This problem adds a constraint: at most k stops. Standard Dijkstra doesn't handle step counts natively. Solution: extend the state to (cost, node, stops_remaining). Use Dijkstra with this 3-tuple, or use Bellman-Ford with k+1 relaxation passes. The modified Dijkstra stops when stops_remaining reaches 0, preventing further hops.
import heapq
from collections import defaultdict
def findCheapestPrice(n, flights, src, dst, k):
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
heap = [(0, src, k + 1)] # (cost, node, hops_left)
visited = {} # node -> min hops_left seen at this cost level
while heap:
cost, node, hops = heapq.heappop(heap)
if node == dst:
return cost
if hops == 0:
continue
if visited.get(node, 0) >= hops:
continue
visited[node] = hops
for nxt, w in graph[node]:
heapq.heappush(heap, (cost + w, nxt, hops - 1))
return -1
print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200Time Complexity Analysis
With a binary heap, Dijkstra runs in O((V + E) log V) time: each vertex is popped once (V pops), each edge may trigger a push (E pushes), and each heap operation costs O(log V). With a Fibonacci heap, the bound improves to O(E + V log V), but Python's heapq is a binary heap. For sparse graphs (E ≈ V), the binary heap version is O(V log V); for dense graphs (E ≈ V²) it is O(V² log V).
Reconstructing the Shortest Path
To recover the actual path (not just the distances), maintain a prev array: when updating dist[v], set prev[v] = u. After the algorithm completes, reconstruct the path from source to destination by tracing backwards: start at dst, follow prev pointers until source, and reverse the result.
import heapq
def dijkstra_path(graph, source, target):
n = len(graph)
dist = [float('inf')] * n
prev = [-1] * n
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited: continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct
path, node = [], target
while node != -1:
path.append(node)
node = prev[node]
return dist[target], path[::-1]Using a Dict for Sparse Graphs
When nodes are strings or non-contiguous integers, use a defaultdict(list) for the adjacency list and a regular dict for distances. This is common in LeetCode problems like Network Delay Time where nodes are labelled 1 to n. Remember to use dist = {node: inf for node in all_nodes} and check for unreachable nodes after the algorithm.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Comparison with BFS for Unweighted Graphs
For unweighted graphs, BFS finds shortest paths in O(V + E) — faster than Dijkstra's O((V+E) log V). Dijkstra generalises BFS to weighted graphs by using a priority queue instead of a regular FIFO queue. When all edge weights are equal, Dijkstra degenerates to BFS. Choose BFS for unweighted, Dijkstra for non-negative weights, and Bellman-Ford for negative weights.
Dijkstra with Decrease-Key Optimisation
The textbook Dijkstra uses a priority queue with decrease-key: when a node's distance improves, update its priority in-place. This requires a Fibonacci heap for O(E + V log V) but is hard to implement. The lazy deletion approach used in interviews instead pushes a new entry and skips stale pops — simpler with only a constant-factor overhead. In Python, lazy deletion with heapq is the standard interview implementation.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Dijkstra uses a min-heap to greedily process nodes in order of current best distance, it runs in O((V+E) log V) time and fails on negative-weight edges, and stale heap entries are handled by checking a visited set on pop. Next up we cover Bellman-Ford, which handles negative weights through n-1 relaxation passes.
Learn Coding Interview Prep with an AI tutor — free
Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.
- Courses
- 90
- Lessons
- 360
Frequently Asked Questions
Is the “Dijkstra's Algorithm with a Priority Queue” lesson free?
Yes — the full text of “Dijkstra's Algorithm with a Priority Queue” is free to read here on the web. 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. The Coding Interview Prep course includes 4 lessons in total.
What will I learn in “Dijkstra's Algorithm with a Priority Queue”?
Implement Dijkstra using heapq, trace the relaxation steps on a weighted graph, and solve cheapest-flights-within-k-stops. 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, so you can start here or from the beginning and move at your own pace. This is lesson 1 of 4.
How long does the “Dijkstra's Algorithm with a Priority Queue” 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's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction