How Dijkstra's Algorithm Actually Works — Python Implementation with a Min-Heap

The Problem Nobody Explains Properly

Every DSA tutorial shows you the naive O(V²) Dijkstra. Interviewers want the O((V + E) log V) heap version. If you can’t explain why the heap makes it faster, you’re going to lose points.

This article walks through:

Why the naive version is too slow
How a min-heap fixes it
A clean Python implementation you can actually memorize
The one edge case that trips everyone up

Why the Naive Version Is O(V²)

The naive implementation tracks the minimum distance vertex by scanning all unvisited vertices at each step:

# O(V) scan at every step → O(V²) total
min_vertex = min(unvisited, key=lambda v: dist[v])

For a dense graph (E ≈ V²) this is fine. For sparse graphs — which is most real-world graphs — it’s catastrophic.

How a Min-Heap Reduces It to O((V + E) log V)

A min-heap gives you the minimum-distance vertex in O(log V) instead of O(V). Since you push at most E times and pop at most V times:

Push operations: O(E log V)
Pop operations: O(V log V)
Total: O((V + E) log V)

For a sparse graph where E ≈ V, this is O(V log V) vs O(V²) — a massive improvement.

The Python Implementation

import heapq
from collections import defaultdict

def dijkstra(graph: dict[int, list[tuple[int, int]]], src: int, n: int) -> list[int]:
    """
    graph: adjacency list — graph[u] = [(v, weight), ...]
    src:   source vertex (0-indexed)
    n:     total number of vertices
    
    Returns: dist[] where dist[i] = shortest distance from src to i,
             or float('inf') if unreachable.
    """
    dist = [float('inf')] * n
    dist[src] = 0

    # Min-heap: (distance, vertex)
    heap = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)

        # CRITICAL: skip stale entries — this is the #1 bug in student code
        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist

Why `if d > dist[u]: continue`?

Python’s heapq has no decrease-key operation. Instead of updating an existing heap entry, you push a new entry with the better distance. The old (stale) entry stays in the heap.

When you pop a stale entry (old_dist, u), old_dist > dist[u] is true — you’ve already processed u with a better path. Skipping it is correct and free.

Without this check, you’d process u multiple times and push its neighbors again with redundant distances. The algorithm still produces correct results (eventually), but it degrades to O(E log E) worst case.

Quick Test

# Build a weighted directed graph
graph = defaultdict(list)
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
for u, v, w in edges:
    graph[u].append((v, w))

dist = dijkstra(graph, src=0, n=4)
print(dist)  # [0, 3, 1, 4]
# 0→2 (cost 1) → 1 (cost 2) = 3  ✓
# 0→2 (cost 1) → 1 (cost 2) → 3 (cost 1) = 4  ✓

Common Interview Pitfalls

Mistake	Fix
Forgetting the stale-entry check	Always add `if d > dist[u]: continue`
Using `dist[src] = 0` but never pushing `(0, src)` to heap	Initialize heap with source
Assuming undirected graph — adding only one direction	Add both `u→v` and `v→u` for undirected
Negative weights	Dijkstra does not work with negative weights. Use Bellman-Ford instead
Heap contains vertex objects instead of indices	Keep heap entries as `(int, int)` — Python compares tuples lexicographically

Time & Space Complexity

	Complexity
Time	O((V + E) log V)
Space	O(V + E) for graph + O(V) for dist + O(E) for heap

The heap can contain at most E entries (one per edge push), giving O(E) heap space.

What to Say in an Interview

“I’m using a min-heap to always process the closest unvisited vertex. Since Python’s heapq doesn’t support decrease-key, I allow duplicate entries and skip stale ones. Total time complexity is O((V + E) log V) which is optimal for sparse graphs.”

That answer covers correctness, the heap choice rationale, the stale-entry trick, and complexity. That’s a complete answer.