Shortest Path (Dijkstra)

BFS finds the shortest path in an unweighted graph because every edge "costs" the same one step. The moment edges have different weights — flight durations, road distances, network latencies — BFS breaks: a path with more edges can still be cheaper overall than a path with fewer, heavier ones. Dijkstra's algorithm solves shortest path for weighted graphs (as long as no edge weight is negative) by always expanding the closest unvisited node next, using a min-heap to efficiently find that node.

The Problem BFS Can't Solve

A --1-- B
|       |
10      1
|       |
C ------D
   1

BFS from A would report B and C as equally "close" (both one edge away) and never realize that A→B→D→C (cost 1+1+1=3) is far cheaper than A→C directly (cost 10). BFS counts edges, not weights — it has no concept of "cost" at all.

Dijkstra's Algorithm With heapq

Keep a dist dict initialized to infinity for every node (0 for the source). Python's heapq module turns a plain list into a min-heap — it always keeps the smallest item accessible at index 0, popped with heapq.heappop. We push (distance, node) tuples, since Python compares tuples element-by-element, so the heap naturally orders by distance first. Pop the smallest-distance node, and for each of its neighbors, if going through the current node gives a shorter path than what's currently recorded, update it — this update step is called relaxation.

import heapq

def dijkstra(adj, source):
    dist = {node: float("inf") for node in adj}
    dist[source] = 0

    # min-heap of (distance, node): smallest distance is always popped first
    heap = [(0, source)]

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

        if d > dist[node]:
            continue  # stale entry, a shorter path was already found

        for neighbor, weight in adj[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist              # relax: found a shorter path
                heapq.heappush(heap, (new_dist, neighbor))

    return dist

Trace-Through on the Example Graph

Using A=0, B=1, C=2, D=3 and edges A-B(1), A-C(10), B-D(1), C-D(1), starting from A:

Initial:        dist = {A:0, B:inf, C:inf, D:inf}     heap: [(0,A)]

Pop (0,A):      relax B: 0+1=1  < inf -> dist[B]=1     heap: [(1,B), (10,C)]
                relax C: 0+10=10 < inf -> dist[C]=10
dist = {A:0, B:1, C:10, D:inf}

Pop (1,B):      relax D: 1+1=2  < inf -> dist[D]=2     heap: [(2,D), (10,C)]
dist = {A:0, B:1, C:10, D:2}

Pop (2,D):      relax C: 2+1=3  < 10 -> dist[C]=3      heap: [(3,C), (10,C)]
dist = {A:0, B:1, C:3, D:2}

Pop (3,C):      no shorter path found through C         heap: [(10,C)]
dist = {A:0, B:1, C:3, D:2}

Pop (10,C):     10 > dist[C]=3 -> stale entry, skipped  heap: []

Final shortest distances from A:  B=1, C=3, D=2

Notice C's shortest distance ends up as 3 (via A→B→D→C), not 10 (the direct A-C edge) — exactly the case a plain BFS-by-edge-count would have missed.

Time complexity: O((V + E) log V) — each of the up to E edge relaxations does a heap push/pop costing O(log V), and every vertex is popped from the heap at least once. Space complexity: O(V + E) for the adjacency list plus O(V) for the distance dict and heap contents.

The Key Limitation: Negative Weights

For graphs that may contain negative edge weights (but no negative cycles), Bellman-Ford is the standard alternative — it relaxes every edge V-1 times instead of relying on a heap's greedy ordering, which correctly handles negative weights at the cost of a slower O(V·E) runtime. It's not covered in depth here since Dijkstra covers the overwhelming majority of interview shortest-path questions, but it's worth knowing the name and the trade-off it exists for.