Dijkstra’s algorithm

Eight towns joined by roads of different lengths, searched from town 0. Watch the nearest unsettled town settle, again and again.

⋯98    dist[START] = 0;99    heap_push((struct item){ 0, START, -1 });100    while (size > 0) {101        struct item x = heap_pop();102        if (done[x.v])103            continue;104        done[x.v] = true;105        parent[x.v] = x.from;106        for (const struct wnode *e = adj[x.v]; e != NULL; e = e->next) {107            int nd = x.key + e->w;108            if (!done[e->to] && (dist[e->to] < 0 || nd < dist[e->to])) {109                dist[e->to] = nd;110                heap_push((struct item){ nd, e->to, x.v });111            }112        }113    }114    printf("dist:");115    for (int v = 0; v < V; v++)116        printf(" %d", dist[v]);117    int path[V];118    int len = 0;119    for (int v = 7; v != -1; v = parent[v]) {120        path[len] = v;121        len++;122    }123    printf("\nroute to 7:");124    for (int i = len - 1; i >= 0; i--)125        printf(" %d", path[i]);126    printf("\n%d pushes\n", pushes);127    for (int u = 0; u < V; u++) {

Settling the nearest town

Breadth-first search finds the routes with the fewest steps. When roads have lengths, the fewest roads is not the shortest route: here, two roads take 0 to 3 for 9 or 10, but three roads take it there for 8.

Dijkstra’s algorithm keeps a distance for every town, the length of the shortest route found so far. A town is settled when its distance is known to be final. Each round it settles the unsettled town with the least distance, then tries every road out of that town to see whether it gives a shorter route to the town at its far end.

The code and its cost

Relaxation

Trying a road from u to v of length w is called relaxing it:

When the road gives a shorter route, v’s distance falls and u becomes v’s parent, the town it is reached from. In dijkstra.c, dist[v] is −1 until a first route is found:

int nd = x.key + e->w;
if (!done[e->to] && (dist[e->to] < 0 || nd < dist[e->to])) {
    dist[e->to] = nd;
    heap_push((struct item){ nd, e->to, x.v });
}

Settling the nearest

The towns waiting to be settled sit in a binary heap, as in binary heaps. Each item is a distance, a town and the town it came from, ordered by distance, and by town number when two distances are equal. The loop takes the least item and settles its town:

while (size > 0) {
    struct item x = heap_pop();
    if (done[x.v])
        continue;
    done[x.v] = true;
    parent[x.v] = x.from;
    ...relax every road out of x.v...
}

From town 0: 0 settles at 0 and offers 2 at 2 and 1 at 4. Town 2 settles at 2 and offers 1 a shorter route, 2 + 1 = 3, as well as 3 at 10 and 4 at 12. Town 1 settles at 3 and offers 3 at 3 + 5 = 8. So a town’s first distance is not always its last: town 1 started at 4 and town 3 at 10.

Why the nearest is safe

Suppose u is the unsettled town with the least distance. Any other route to u must leave the settled towns somewhere, through a town whose distance is already at least d[u], and then add roads of length 0 or more. So no route found later can be shorter than d[u], and settling u is safe. Once a town is settled, its distance never changes.

The heap, and stale items

When town 1 falls from 4 to 3, its old item (4, 1) is still in the heap. Finding and changing it would mean searching the heap, so the program pushes a new item (3, 1) instead, and leaves the old one. The old one comes out later, when town 1 is already settled, and is skipped. These are stale items. From town 0 there are 12 pushes, the start and 11 improvements, and 12 pops, 4 of them stale.

Reading the route back

The parents form a tree of shortest routes from the start. The route to 7 is read backwards, from 7 to its parent and on to the start, then printed the right way round:

dist: 0 3 2 8 10 13 14 14
route to 7: 0 2 1 3 4 5 7
12 pushes

The cost

Each road is relaxed from the end that settles first; from the other end it leads to a settled town and is skipped. So there is at most one push per road, plus the start: at most E + 1 pushes, and as many pops. A heap operation takes about log₂ of the heap’s size, and the heap never holds more than E + 1 items. Since E is less than V², log E is less than 2 log V, and the whole search takes O((V + E) log V). Without a heap, scanning an array of distances for the nearest town takes O(V²), which is better when nearly every pair of towns is joined.

Negative road lengths

The argument for settling the nearest needs every length to be 0 or more. Take three towns s, a and b with roads s → a of length 2, s → b of length 3 and b → a of length −2. The algorithm settles s, then a at 2, then b at 3, and never looks at a again; but the route s, b, a has length 1.

Two other algorithms cope with negative lengths. Bellman–Ford relaxes every road V − 1 times, which is enough for any shortest route, since one has at most V − 1 roads; it takes O(VE), and if a road can still be relaxed after that, there is a cycle of negative total length and no shortest route exists. Floyd–Warshall finds the shortest distance between every pair of towns with three nested loops, trying each town k in turn as a stop between i and j: O(V³).

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic dijkstra.c -o dijkstra
./dijkstra
gcc -std=c11 -Wall -Wextra -pedantic -DSTART=4 dijkstra.c -o dijkstra4
./dijkstra4

Worked example

By hand from town 0. Settle 0; 2 gets 2 and 1 gets 4. Settle 2; 1 falls to 3, 3 gets 10, 4 gets 12. Settle 1; 3 falls to 8. Skip (4, 1). Settle 3; 5 gets 14 and 4 falls to 10. Skip (10, 3). Settle 4; 6 gets 14 and 5 falls to 13. Skip (12, 4). Settle 5; 7 gets 14. Skip (14, 5). Settle 6; through 6, town 7 would cost 14 + 2 = 16, no better. Settle 7. The route to 7 costs 2 + 1 + 5 + 2 + 3 + 1 = 14.

Fewest roads is not least cost. The two-road routes to 3 are 0–1–3, 4 + 5 = 9, and 0–2–3, 2 + 8 = 10. The three-road route 0–2–1–3 costs 2 + 1 + 5 = 8.

A negative length. In the three towns above, the algorithm reports 2 for a, though 1 is possible: it settled a before the cheaper route through b was seen.

Two checks. Why was town 1’s first distance not final? (Town 2 was nearer and offered a shorter road to 1.) Which towns have 4 as their parent? (5 and 6.)

Where it’s used

Route planning. Finding the shortest or quickest route in a map of roads, where the lengths are distances or travel times.

Computer networks. Link-state routing protocols have each router run a shortest-path search over a map of the network’s links.

Games. Path-finding for characters, often with A*, a variant that adds to each key an estimate of the distance still to go, so that the search heads towards the goal.

Any problem that asks for the least total cost over a network of costs that are never negative has the same shape.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.