Dijkstra's algorithm — shortest paths when edges have different costs

BFS finds the shortest path perfectly, but only when every edge costs the same — the moment edges have different weights, BFS's level-by-level guarantee breaks, and Dijkstra's algorithm is the real, structural fix: always expand the cheapest known path first.

Advanced

4 min read

Why BFS's shortest-path guarantee breaks the moment edges have weights

BFS visits nodes in strict distance order (1 hop, then 2 hops, then 3...) —
this ONLY produces correct shortest paths when every edge costs the SAME.

With weighted edges, a path using MORE edges can still be CHEAPER overall:
  A --1--> B --1--> C   (2 hops, total cost 2)
  A --------5-------> C  (1 hop, total cost 5)
BFS would visit C via the 1-hop edge FIRST (fewer hops), reporting cost 5 —
but the actual shortest path is the 2-hop route, costing only 2

BFS's correctness for shortest paths relies entirely on "fewer hops always means cheaper" — true only when every edge has the same weight (or no weight at all). The instant edges can have different costs, a path with more edges can legitimately be cheaper than a path with fewer, and BFS's level-by-level traversal has no way to account for that — it would report the 1-hop path as "found first" without ever comparing its actual cost against the cheaper 2-hop alternative.

Dijkstra's core idea: always expand the cheapest known path so far

import heapq
 
def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance_so_far, node) — a MIN-HEAP, always pops the smallest distance first
 
    while pq:
        dist, node = heapq.heappop(pq)
        if dist > distances[node]:
            continue  # a CHEAPER path to this node was already found and processed — skip this stale entry
 
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
 
    return distances

Dijkstra's algorithm uses a priority queue (the min-heap from the heaps-and-priority-queues lesson) instead of BFS's plain queue, always processing whichever unvisited node currently has the smallest known distance from start — this is the direct, structural fix for BFS's blind spot: by always expanding the genuinely cheapest known path next, a shorter-but-more-expensive path can never get "locked in" before a longer-but-cheaper alternative gets its fair chance to be discovered and compared.

The `if dist > distances[node]: continue` line — a real, necessary check

# A node can be pushed onto the heap MULTIPLE times, at different distances,
# before the cheapest one is actually popped and processed — once the
# CHEAPEST entry for a node has been processed, every LATER (more expensive)
# entry for that same node still sitting in the heap is now stale and
# must be skipped, not reprocessed as if it were new information

Because a node can be discovered multiple times through different paths before the algorithm gets around to processing it, the heap can end up holding several entries for the same node at different distances — once the cheapest entry is popped and processed, any later, more expensive entry for that same node is now stale information that should be skipped, not treated as a fresh update. Skipping this check doesn't produce wrong answers, but it does real, unnecessary extra work — re-processing a node's neighbors using an already-superseded, worse distance.

The one requirement Dijkstra genuinely needs: no negative edge weights

Dijkstra's "always expand the cheapest known path" logic assumes that once
a node is processed at its minimum distance, NOTHING found later could
possibly make it cheaper — a NEGATIVE edge weight breaks this assumption
directly, since a later, seemingly-worse path could suddenly become
cheaper by traversing a negative edge

Dijkstra's core assumption — that the first time a node is processed, its distance is final and correct — depends on every edge weight being non-negative; a negative edge could make an already-processed, "finalized" node's distance retroactively wrong, since a path through that negative edge might beat the distance Dijkstra already locked in. This is exactly why a graph with negative weights needs a genuinely different algorithm (Bellman-Ford, which tolerates negative edges by relaxing every edge repeatedly instead of trusting a greedy "cheapest so far" choice) — not a variation on Dijkstra, but a structurally different approach.

Dijkstra's algorithm — shortest paths when edges have different costs

Why BFS's shortest-path guarantee breaks the moment edges have weights

Dijkstra's core idea: always expand the cheapest known path so far

The if dist > distances[node]: continue line — a real, necessary check

The one requirement Dijkstra genuinely needs: no negative edge weights

Further reading

The `if dist > distances[node]: continue` line — a real, necessary check