Dijkstra's algorithm: shortest paths with non-negative weights

Every time a satellite navigator computes a route, a routing protocol chooses the way for a packet or a video game moves a character towards a goal, there is almost always a variant of the same problem behind it: finding the minimum-cost path in a weighted graph. The best-known algorithm for solving it is the one published by Edsger Dijkstra in 1959, and it is still the reference point when edge weights are not negative.

The problem

Given a graph with weighted edges (distances, times, costs) and a starting vertex s, we want the minimum distance from s to every other vertex, together with the path that achieves it. Breadth-first search solves the case in which all edges weigh the same; with different weights something more is needed.

Relaxation

The elementary operation is the relaxation of an edge (u, v) with weight w: if going through u improves the current estimate for v, update it.

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    parent[v] = u

At the start dist[s] = 0 and all other estimates are infinity. Shortest-path algorithms differ only in the order in which they relax edges.

Dijkstra's strategy

Dijkstra chooses a very precise order: at each step it takes the non-final vertex with the lowest estimate, declares it final and relaxes its outgoing edges. The intuition is the same as the waves in the pond of BFS, but the wave advances by actual distance rather than by number of edges.

To quickly find the vertex with the minimum estimate, a priority queue is used, typically a binary heap:

import heapq

def dijkstra(adj, s):
    dist = {s: 0}
    parent = {s: None}
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue          # entry superseded by a better estimate
        for v, w in adj[u]:
            nd = d + w
            if v not in dist or nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent

The line with continue deserves attention. Python's heapq module does not allow decreasing the priority of an element already inserted; so a new entry is pushed and, when the old one surfaces, it is discarded. This technique is called «lazy deletion», and it is simple and very efficient in practice.

A worked example

Vertices A, B, C, D; edges A–B 4, A–C 1, C–B 2, B–D 1, C–D 5. Start from A.

The shortest path to D is A → C → B → D, of length 4, even though it uses three edges rather than the two of A → C → D.

Why non-negative weights are required

Correctness rests on one statement: when a vertex is extracted with the lowest estimate, no alternative path can do better, because any other path goes through vertices with an estimate at least as large and adds edges of positive or zero weight.

If there is a negative edge, this guarantee breaks: a path that looked longer could become shorter after an edge of weight −5. Dijkstra may then return wrong results without any warning sign. With negative weights, use Bellman-Ford.

Cost

With a binary heap every extraction and every insertion takes logarithmic time. The total is of the order of (n + m) log n, excellent for sparse graphs such as road networks. For dense graphs a version with a plain array, which finds the minimum by scanning all vertices, costs n² and can even be faster.

Practical tips

• Stop early: if only one target t matters, the algorithm can be interrupted as soon as t is extracted from the heap. Its distance is already final.
• Choose the right weight: the same road graph gives different routes if the weight is length, average time or toll cost. They can also be combined, for example time plus a penalty for each turn.
• Beware of floating-point values: comparing sums of decimal numbers can create tiny differences that change the chosen route; where possible, use integers (metres, seconds).
• Huge graphs: for continental networks, preprocessing techniques are added, such as bidirectional search or heuristics, of which A* is the best-known example.

In short

• Dijkstra computes shortest paths from one source in graphs with non-negative weights.
• At each step it finalises the vertex with the lowest estimate and relaxes its edges.
• With a binary heap it costs roughly (n + m) log n.
• With negative edges it can be wrong without noticing: in that case Bellman-Ford is needed.
• Stopping at the target and choosing weights carefully are the simplest optimisations.