• V = number of vertices, E = number of edges
• All edge weights must be non-negative — the correctness argument fails otherwise
• The graph may be directed or undirected
• Unreachable vertices retain a distance of infinity
• O((V + E) log V) time with a binary heap, O(V + E) space

Breadth-first search finds shortest paths when every edge costs the same. This problem is what happens when that assumption is removed, and understanding precisely which part of the BFS argument breaks is what makes the replacement make sense.

BFS is correct because of a ring argument: everything one edge from the source is discovered first, then everything two edges away, and so on. A vertex first appears in the ring matching its true distance. That argument silently assumes one edge equals one unit of cost.

Now give edges weights. Consider three vertices with a direct edge from 0 to 2 of weight 10, and a two-edge route 0 to 1 to 2 costing 1 each.

BFS reaches vertex 2 in one hop and reports a distance of one edge. But the cheapest route costs 2, using two edges. Fewest edges and cheapest total are simply different questions, and BFS answers the wrong one.

So the frontier can no longer be ordered by hop count. It must be ordered by accumulated cost.

Here is the idea the whole algorithm rests on.

Keep a tentative best-known distance for every vertex, starting at 0 for the source and infinity elsewhere. Now repeatedly take the unsettled vertex with the smallest tentative distance and declare that distance final.

That declaration needs justifying, and the argument is short enough to give in an interview.

Let u be the unsettled vertex with the smallest tentative distance d. Suppose some cheaper path to u exists. That path starts at the source, which is settled, and ends at u, which is not, so somewhere along it there is a first unsettled vertex — call it x, possibly u itself. The portion of the path from the source to x consists entirely of settled vertices, so x's tentative distance is already at most the cost of that portion. And since u was chosen as the smallest tentative distance among unsettled vertices, x's tentative distance is at least d.

So the path costs at least d up to x, plus the weight of the remaining segment from x to u. Because every weight is non-negative, that remaining segment costs at least 0, so the whole path costs at least d. No cheaper path exists, and d is final.

Notice exactly where non-negativity entered: it is what guarantees the rest of the path cannot reduce the total. With a negative edge available, a longer route could dip below d after passing through x, and the entire argument collapses. This is not a technicality — it is the whole reason the algorithm is restricted to non-negative weights.

The updating step has a standard name. Relaxing an edge from u to v with weight w means asking whether routing through u improves the known distance to v:

if dist[u] + w < dist[v], then dist[v] becomes dist[u] + w.

Each time a vertex is settled, every edge leaving it is relaxed. That is the only way distances ever improve.

To always know which unsettled vertex is nearest, keep candidates in a min-heap — a structure whose smallest element is always available at the top, with insertion and removal costing O(log n).

import heapq

def dijkstra(adj, source, V):
    dist = [float('inf')] * V
    dist[source] = 0
    heap = [(0, source)]                      # (distance, vertex)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                          # stale entry: a better route was found later
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:                  # relax
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Cost: each edge can push at most one heap entry, so the heap holds up to E items and each push and pop costs log E, which is O(log V) since E is at most V². Total O((V + E) log V) time and O(V + E) space.

Worth knowing: without a heap, scanning all V vertices each round to find the nearest gives O(V²), which is actually faster on a dense graph where E approaches V². The heap version wins on sparse graphs, which is the common case.

Directed edges (0,1,4), (0,2,1), (2,1,2), (1,3,3), (2,3,8), source 0.

Distances start at [0, ∞, ∞, ∞] and the heap holds (0, 0).

Final: [0, 3, 1, 6]. Vertex 1 was reached more cheaply by a two-edge route than by its direct edge, and vertex 3 likewise.

Signals: shortest, cheapest, fastest, minimum cost or time over a graph whose edges carry non-negative weights. Road networks, network latency, flight prices, grids where cells cost different amounts to enter.

Three boundaries are worth being able to state.

Equal weights. If every edge costs the same, plain BFS gives the same answer with no heap and no log factor. Reaching for Dijkstra there is overkill, though not wrong. A special case worth knowing: when weights are only 0 and 1, a deque — pushing zero-weight neighbours to the front and one-weight to the back — gives O(V + E). That is called 0-1 BFS.

Negative weights. The greedy argument fails, as shown above, and the algorithm returns wrong answers without complaining. Use Bellman-Ford, which relaxes every edge V-1 times and also detects negative cycles.

All pairs. Running Dijkstra from every vertex costs O(V × (V + E) log V). On a dense graph, Floyd-Warshall's O(V³) is simpler and often faster.

One more upgrade worth naming: when there is a single known destination rather than all of them, A\* adds an optimistic estimate of the remaining distance to each heap key. As long as that estimate never overstates the true remainder, the answer stays optimal while the search is pulled toward the goal and touches far fewer vertices.

Train the reflex: the moment edges carry unequal non-negative costs and the question asks for a minimum total, stop counting hops. Order the frontier by accumulated cost, settle the nearest vertex, and relax its edges.