Dijkstra

Edsger Dijkstra designed this method in 1956, in about twenty minutes, he said, sitting at a café in Amsterdam. It finds the shortest times from one start to every vertex when no edge is negative, and it is still the method behind route planners today.

Settle the nearest

Breadth-first search reaches vertices in order of distance. Dijkstra’s method does the same with weights. It keeps a best time so far for every vertex, and splits the vertices into two groups: settled vertices, whose time is final, and the rest. At each step it picks the vertex that is not settled and has the smallest time, settles it, and relaxes its edges (lesson 1).

1. Set every time to ∞, except the start’s, which is 0.
2. Pick the unsettled vertex u with the smallest time. If its time is ∞, stop: the rest cannot be reached.
3. Settle u. Relax every edge u → v: if time(u) + w is less than time(v), lower time(v) and make u its parent.
4. Repeat from step 2 until every vertex is settled.

This is a greedy method (GRDY-1): it makes the choice that looks best now and never takes it back. Step through the figure. The heap on the right holds the candidates; ink stations are settled.

Why a settled time is final

Suppose u is the unsettled vertex with the smallest time t, and take any route P from s to u. P starts inside the settled group (s is settled first) and ends outside it, so at some point it leaves the group: let x → y be the first edge of P from a settled x to an unsettled y. When x was settled, the edge x → y was relaxed, so time(y) ≤ δ(s, x) + w(x, y), which is the length of P up to y. Because u was picked, t ≤ time(y). And the rest of P, from y to u, has no negative edge, so it adds 0 or more. Putting these together:

Every route to u is at least t long, and t is the length of a real route, so t is the true distance. Settling u keeps the invariant true, and by induction every vertex is settled with its true distance. The proof used “no edge is negative” exactly once, in the last step; the last section of this lesson shows what happens without it.

With heapq

Step 2, finding the smallest time, is the slow part. A heap (HEAP-4) finds it in O(log V). Python’s heapq has no way to lower the priority of an entry already in the heap, so the usual Python version uses lazy removal, as HEAP-4 described: when a time goes down, push a new entry and leave the old one where it is. When an entry comes out, check whether it is out of date, and if so, skip it.

import heapq
import math

def dijkstra(adj, s):            # adj[u]: list of (v, w), w >= 0
    dist = [math.inf] * len(adj)
    parent = [-1] * len(adj)
    dist[s] = 0
    heap = [(0, s)]               # (time, vertex): smallest time first
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue              # an old entry: u is settled already
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                parent[v] = u
                heapq.heappush(heap, (d + w, v))
    return dist, parent

The tuples compare by time first, then by vertex number when times tie, so the heap never has to compare anything else. If vertices are objects that cannot be compared, use (time, count, vertex) with a counter, as in HEAP-4.

The line if d > dist[u]: continue matters for speed. Without it, an old entry for u makes the loop read all of u’s edges again. A vertex with many edges that is offered a better time many times is then handled many times, each time reading every edge: PATH-P3 has a test built for that. A list done of settled vertices does the same job.

One target. If only the time to t is wanted, stop when t comes out of the heap: its time is final then. The route is rebuilt by following parent back from t, as in GRPH-2.

What it costs

Each edge is relaxed once (when its start is settled) and can push one entry, so the heap holds at most E entries. Each push and pop costs O(log E), and log E ≤ 2 log V, because E is at most V² (V times V). In all, O((V + E) log V).

• Without a heap. Looking through all V vertices for the smallest time costs O(V) per step, so O(V²) in all. For a dense graph, where E is close to V², that is as good as the heap version, and simpler. For a sparse graph of 100,000 vertices it is about 10¹⁰ steps (ten thousand million): far too slow.
• Decrease-key. A heap that can lower an entry in place (it keeps a list of where each vertex sits in the heap) holds at most V entries instead of E. With a Fibonacci heap, lowering costs O(1) on average and the total is O(E + V log V), the best known bound for this method. In Python, lazy removal with heapq is faster in practice than any heap written by hand.

Why negative edges break it

Switch the figure to “A negative edge”. B is settled at 2 because 2 is the smallest time in the heap. Later, C (at 3) has an edge of −2 to B, which would give 1. But B is settled and never looked at again, and D, settled from B, is wrong too. In the proof, “the rest of P adds 0 or more” is false: a longer route can become cheaper after its last edge.

Two tempting fixes do not work. Adding a constant to every weight to make them all positive changes which route is shortest: a route with more edges gets the constant more times. Allowing settled vertices to be lowered again (dropping the settled check) does give right answers when there is no negative cycle, but a vertex can then be handled many times, and on bad inputs the number of steps grows exponentially. With negative edges, use Bellman–Ford (lesson 4), or Johnson’s reweighting (lesson 5) for all pairs.

Now try PATH-P3, The fastest journey.