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 DSA 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 DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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.
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, and the DSA 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 DSA Interview Prep course, upgrade to CoddyKit PRO.
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 DSA 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 DSA Interview Prep?
No prior experience is required. DSA 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'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 DSA Interview Prep lesson?
Yes. Every DSA 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