Shortest Paths: Dijkstra

What problem are we solving?

Imagine a map. There are places (cities, intersections, computers on a network) and roads between them. Each road has a cost: how long it takes, how many miles it is, how much it charges. You start at one place and you want to know the cheapest total cost to reach every other place.

That is the single-source shortest paths problem. “Single-source” means we pick one starting place (the source) and compute the shortest distance from it to everyone else, all at once.

Dijkstra’s algorithm solves this when every road cost is non-negative (zero or positive, never below zero). Almost all real distances, times, and prices are non-negative, so this covers a huge number of practical cases.

Before we go further, a few terms, because we assume you have never programmed:

• Graph: a collection of nodes (also called vertices — the “places”) and edges (the “roads” connecting them).
• Weighted edge: an edge that carries a number, its weight or cost. Here the weight is a distance.
• Directed vs undirected: an edge can be one-way (directed) or two-way (undirected). We will use a directed graph, meaning an edge from A to B does not automatically let you go from B to A.
• Path: a sequence of edges you follow to get from one node to another. Its length is the sum of the weights of its edges.
• Shortest path: among all possible paths from the source to a node, the one with the smallest total length.

The example graph

We will use this small directed, weighted graph throughout. Node A is our source.

graph LR
    A -->|4| B
    A -->|1| C
    C -->|2| B
    B -->|1| D
    C -->|5| D
    D -->|3| E
    B -->|1| E

Read A -->|4| B as: there is a road from A to B that costs 4. Notice there are two ways to reach B from A:

• Direct: A -> B costs 4.
• Through C: A -> C -> B costs 1 + 2 = 3.

So the shortest distance to B is 3, not 4. A greedy “always take the smallest single road” idea would wrongly pick the direct edge of 4 if it looked only one step ahead. Dijkstra avoids that mistake, and we will see exactly how.

The core idea: finalize the closest node first

Dijkstra keeps, for every node, its best known distance so far from the source. At the start we know only that the source is at distance 0 from itself, and everything else is unknown, which we represent as infinity (a stand-in for “no path found yet”).

The algorithm repeats one move:

1. Among all nodes not yet finalized, pick the one with the smallest known distance.
2. Finalize it. Its known distance is now guaranteed to be the true shortest distance and will never change.
3. Relax its outgoing edges (defined below), possibly improving the known distances of its neighbors.

“Finalize” means we lock in that node’s answer. The key insight (this is why the algorithm is correct) is: the closest unfinalized node cannot be improved by any future step, because all edge weights are non-negative. Any other route to it would have to pass through some node that is even farther away, and adding non-negative edges can only make it longer, never shorter.

What “relaxation” means

Relaxing an edge from node u to node v with weight w asks one question:

Is going to v through u cheaper than the best route to v we already knew?

In numbers: if dist[u] + w < dist[v], then we found a better route, so we update dist[v] = dist[u] + w. Otherwise we leave v alone. The word “relax” comes from loosening an over-estimate down toward the true value.

Why we need a priority queue (min-heap)

Step 1 above says “pick the smallest-distance unfinalized node.” If we searched the whole list every time, that search would be slow. Instead we use a min-heap, also called a priority queue: a structure that always hands back the smallest item quickly.

• Min-heap: a container where the operation “remove the smallest element” and “add an element” both take about log N time, where N is how many items are inside. You do not get the items in sorted order all at once; you just always get the current minimum on demand.

Python has one built in: the heapq module. We store pairs (distance, node). Because the distance is first in the pair, the heap compares by distance and always gives us the node with the smallest tentative distance.

The Python code

Every line is explained in the comments. This is complete and runnable in Python 3.

import heapq  # the built-in min-heap (priority queue) module

def dijkstra(graph, source):
    # graph is a dict: node -> list of (neighbor, weight) pairs.
    # Start every distance at infinity, meaning "no path known yet".
    dist = {node: float("inf") for node in graph}
    dist[source] = 0  # distance from the source to itself is 0

    # The heap holds (distance, node). It starts with just the source.
    heap = [(0, source)]

    while heap:  # keep going until there is nothing left to process
        d, u = heapq.heappop(heap)  # remove the smallest-distance node

        # Skip stale entries (explained in the pitfalls section):
        # if d is worse than the best we already recorded, ignore it.
        if d > dist[u]:
            continue

        # Relax every edge leaving u.
        for v, w in graph[u]:
            new_dist = d + w
            if new_dist < dist[v]:      # found a cheaper route to v
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))  # remember to visit v

    return dist

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("D", 1), ("E", 1)],
    "C": [("B", 2), ("D", 5)],
    "D": [("E", 3)],
    "E": [],
}

print(dijkstra(graph, "A"))
# -> {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 4}

The graph dictionary is an adjacency list: for each node it lists the edges going out of it as (neighbor, weight) pairs. graph["A"] = [("B", 4), ("C", 1)] means A has a road of cost 4 to B and a road of cost 1 to C.

Watching it run: a full step-by-step trace

This is the heart of the lesson. Below, dist is the current best-known distance map, and the heap is shown as the set of (distance, node) pairs waiting to be processed. INF means infinity (unknown). A node is finalized the moment we pop it and it is not stale.

Starting state: dist = {A:0, B:INF, C:INF, D:INF, E:INF}, heap [(0,A)].

Heap empty, so we stop. Final answer: A:0, B:3, C:1, D:4, E:4.

Trace through the logic once by hand. Notice step 2: we finalized C (distance 1) before B, and that is exactly what let us discover the cheaper A -> C -> B route of 3, correcting the naive direct estimate of 4 from step 1. Also notice steps 4 and 7 popped stale entries and correctly did nothing.

Line the nodes up in the order they were finalized and the distances only ever climb, never drop:

graph LR
    A["A finalized dist 0<br/>step 1"] --> C["C finalized dist 1<br/>step 2"]
    C --> B["B finalized dist 3<br/>step 3"]
    B --> D["D finalized dist 4<br/>step 5"]
    D --> E["E finalized dist 4<br/>step 6"]

Nodes come out of the heap in non-decreasing distance order: 0, 1, 3, 4, 4. This ordering is what makes “finalize the closest” safe.

Why non-negative weights are required

The correctness argument was: when we finalize the closest unfinalized node, no future path can beat its current distance, because any other path would extend through nodes that are farther out, and extra edges only add non-negative amounts. If a negative edge existed, that promise breaks: a node could look far away now, then a later negative edge could drag its true distance below a value we already finalized, and Dijkstra would have locked in a wrong answer.

Small broken example: A -> B costs 2, A -> C costs 5, and C -> B costs -4. Dijkstra finalizes B at 2 (it is closer than C at 5). But the real shortest path to B is A -> C -> B = 5 + (-4) = 1, which is smaller. Dijkstra never revisits a finalized node, so it reports 2 and is wrong.

For graphs with negative edges you need a different algorithm (Bellman-Ford). Dijkstra simply does not apply there.

Complexity: time and space

Let V be the number of nodes (vertices) and E be the number of edges.

Time: O((V + E) log V). The derivation, counting the actual work:

• Each node is popped and finalized at most once. That is up to V pops. Each pop from the heap costs O(log V) (the heap holds at most O(E) items, and log E is O(log V) because E is at most V^2, so log E <= 2 log V). Total for pops: O(V log V).
• Each edge is relaxed at most once when its source node is finalized. A successful relaxation pushes one new pair onto the heap, costing O(log V). Across all edges that is O(E log V).
• Add them: O(V log V + E log V) = O((V + E) log V).

In plain words: we do a little bit of log V work for every node we pull out and for every edge we improve, and there are V nodes and E edges, so the total is those counts times log V.

Space: O(V + E). We store the dist map (O(V)), the graph’s adjacency list (O(V + E)), and the heap. The heap can hold a stale entry per relaxation, so up to O(E) items. Everything together is O(V + E).

Common pitfalls

• Stale heap entries. When we find a cheaper route to a node, we push a new (distance, node) pair but we do not remove the old, larger one (standard heaps have no cheap “remove arbitrary item”). So the heap can contain out-of-date pairs. The guard if d > dist[u]: continue handles this: when we pop a pair whose distance is worse than the best we already recorded, we skip it. Forgetting this guard does not give a wrong final answer here, but it wastes work re-relaxing edges. Always include it.
• Negative edges. As shown above, Dijkstra is simply incorrect with any negative weight. Do not use it there. If someone hands you costs that can be negative (refunds, elevation drops), reach for Bellman-Ford instead.
• Forgetting a node is reachable. If a node has no path from the source, its distance stays INF (infinity) in the result. That is correct and expected, not a bug.
• Undirected graphs need both directions. If a road is two-way, you must add both A -> B and B -> A to the adjacency list. Our example is directed, so we did not.
• Comparing pairs. We put distance first in (distance, node) on purpose. The heap compares tuples left to right, so it orders by distance. If you accidentally put the node first, it would order alphabetically by node name instead, which is wrong.

Practice

1. Add an edge A -> E with weight 10 to the example graph and re-run the trace by hand. Does the shortest distance to E change? Confirm with the code.
2. Change the edge C -> B weight from 2 to 6. Now which route to B is shorter, direct or through C? Predict the final dist map, then verify with the code.
3. Extend the dijkstra function to also return the actual path (the sequence of nodes) to each destination, not only the distance. Hint: keep a parent dictionary that records, for each node, which neighbor relaxed it, then walk backward from the target to the source.