Dijkstra's algorithm

Why it exists

A route planner, a network router and a game's path finder all need the cheapest way from one place to all others when every road has a cost. Dijkstra's algorithm does it in nearly linear time whenever no cost is negative. It is a greedy algorithm (always finish the closest unfinished vertex) and a close relative of BFS (which is the special case where all costs are equal) and of Prim's algorithm (the same loop with a different key). GATE asks for the distances and the order in which vertices are finished, the running time for each data structure, and why negative edges are not allowed.

Prerequisites

You need graph search (BFS and DFS) and the min-heap (binary heap).

Precise definitions

Weighted directed graph. Each edge $u \to v$ has a weight $w(u, v)$ (a cost or length). The weight of a path is the sum of the weights of its edges. The shortest-path distance $\delta(s, v)$ is the smallest weight of a path from $s$ to $v$ ($\infty$ if there is none). An undirected edge is treated as two directed edges of the same weight.

Optimal substructure. Every subpath of a shortest path is itself a shortest path (otherwise it could be replaced by a shorter one). This is what makes greedy and dynamic programming work.

Triangle inequality. For every edge $u \to v$: $\delta(s, v) \le \delta(s, u) + w(u, v)$.

Relaxation of an edge $u \to v$: if $\text{dist}[u] + w(u, v) < \text{dist}[v]$, set $\text{dist}[v] = \text{dist}[u] + w(u, v)$ and $\text{parent}[v] = u$. A relaxation never makes $\text{dist}[v]$ smaller than the true distance, only closer to it.

Dijkstra's algorithm (all $w \ge 0$). Keep $\text{dist}[v]$ (an upper bound for $\delta(s, v)$, initially $\infty$, and $0$ for $s$) and a set of finished vertices. Repeat: choose the unfinished vertex $u$ with the smallest $\text{dist}$, mark it finished, and relax all edges leaving $u$ (to unfinished vertices). Stop when no unfinished vertex has finite distance.

How it works

The animation runs the real code on a directed graph with edges $0 \to 1\,(4)$, $0 \to 2\,(1)$, $2 \to 1\,(2)$, $1 \to 3\,(1)$, $2 \to 3\,(5)$, $3 \to 4\,(3)$, $1 \to 4\,(8)$, $4 \to 5\,(2)$, $3 \to 5\,(6)$. Watch vertex $1$: its first estimate $4$ (the direct edge) is improved to $3$ once vertex $2$ is finished, because $0 \to 2 \to 1$ costs $1 + 2$.

The same run in a table, round by round, from a C program that prints its state after every round and also counts the relaxations tried:

#include <stdio.h>
 
#define N 6
#define INF 1000000
 
static int w[N][N];                  /* w[u][v] = weight of the edge u -> v, 0 if there is none */
 
static void show(const int dist[]) {
    for (int v = 0; v < N; v++) {
        if (dist[v] >= INF) printf(" inf");
        else printf(" %3d", dist[v]);
    }
}
 
int main(void) {
    int dist[N], parent[N], done[N] = {0}, tried = 0;
    w[0][1] = 4; w[0][2] = 1; w[2][1] = 2; w[1][3] = 1; w[2][3] = 5; w[3][4] = 3; w[1][4] = 8; w[4][5] = 2; w[3][5] = 6;
    for (int v = 0; v < N; v++) { dist[v] = INF; parent[v] = -1; }
    dist[0] = 0;
    for (int round = 1; round <= N; round++) {
        int u = -1;
        for (int v = 0; v < N; v++)
            if (!done[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1) break;
        done[u] = 1;
        for (int v = 0; v < N; v++) {
            if (w[u][v] != 0 && !done[v]) {
                tried++;
                if (dist[u] + w[u][v] < dist[v]) { dist[v] = dist[u] + w[u][v]; parent[v] = u; }
            }
        }
        printf("round %d: take %d (dist %d), distances:", round, u, dist[u]);
        show(dist);
        printf("\n");
    }
    printf("edge relaxations tried: %d (one for each of the 9 edges)\n", tried);
    printf("parents:");
    for (int v = 0; v < N; v++) printf(" %d", parent[v]);
    printf("\n");
 
    /* a negative edge breaks the method: 0 -> 1 (2), 0 -> 2 (3), 2 -> 1 (-2) */
    int m[3][3] = {{0, 2, 3}, {0, 0, 0}, {0, -2, 0}}, d3[3] = {0, INF, INF}, f3[3] = {0};
    d3[1] = 2; d3[2] = 3;
    for (int round = 0; round < 3; round++) {
        int u = -1;
        for (int v = 0; v < 3; v++) if (!f3[v] && d3[v] < INF && (u == -1 || d3[v] < d3[u])) u = v;
        if (u == -1) break;
        f3[u] = 1;
        for (int v = 0; v < 3; v++) if (m[u][v] != 0 && !f3[v] && d3[u] + m[u][v] < d3[v]) d3[v] = d3[u] + m[u][v];
    }
    int e3[3][3] = {{0, 2, 3}, {0, 0, 0}, {0, -2, 0}}, t3[3] = {0, INF, INF};
    for (int pass = 0; pass < 3; pass++)                  /* the true distances, by trying every edge repeatedly */
        for (int u = 0; u < 3; u++)
            for (int v = 0; v < 3; v++)
                if (e3[u][v] != 0 && t3[u] < INF && t3[u] + e3[u][v] < t3[v]) t3[v] = t3[u] + e3[u][v];
    printf("negative edge example: Dijkstra gives %d %d %d, the true distances are %d %d %d\n", d3[0], d3[1], d3[2], t3[0], t3[1], t3[2]);
    return 0;
}

round 1: take 0 (dist 0), distances:   0   4   1 inf inf inf
round 2: take 2 (dist 1), distances:   0   3   1   6 inf inf
round 3: take 1 (dist 3), distances:   0   3   1   4  11 inf
round 4: take 3 (dist 4), distances:   0   3   1   4   7  10
round 5: take 4 (dist 7), distances:   0   3   1   4   7   9
round 6: take 5 (dist 9), distances:   0   3   1   4   7   9
edge relaxations tried: 9 (one for each of the 9 edges)
parents: -1 2 0 1 3 4
negative edge example: Dijkstra gives 0 2 3, the true distances are 0 1 3

The vertices are finished in the order $0, 2, 1, 3, 4, 5$ with distances $0, 1, 3, 4, 7, 9$: non-decreasing. The parents $-, 2, 0, 1, 3, 4$ give the shortest path tree; the shortest path to $5$ is read backwards: $5 \leftarrow 4 \leftarrow 3 \leftarrow 1 \leftarrow 2 \leftarrow 0$, that is $0 \to 2 \to 1 \to 3 \to 4 \to 5$ of weight $1 + 2 + 1 + 3 + 2 = 9$. Every edge was examined once: $9$ relaxation attempts for $9$ edges.

Why it is correct

Invariant. When a vertex $u$ is finished, $\text{dist}[u] = \delta(s, u)$.

Proof sketch. Suppose $u$ is the first vertex finished with $\text{dist}[u] > \delta(s, u)$. Look at a shortest path from $s$ to $u$ and the first vertex $y$ on it that is not finished; its predecessor $x$ on the path is finished, and by the choice of $u$ the distance of $x$ is correct, so relaxing $x \to y$ gave $\text{dist}[y] = \delta(s, y)$. Since all weights are non-negative, $\delta(s, y) \le \delta(s, u) < \text{dist}[u]$. But $u$ was chosen as the unfinished vertex with the smallest $\text{dist}$, so $\text{dist}[u] \le \text{dist}[y]$: a contradiction. $\blacksquare$

The non-negativity is used in the step $\delta(s, y) \le \delta(s, u)$: the rest of the path from $y$ to $u$ cannot make it shorter.

Why a negative edge breaks it

With the edges $0 \to 1\,(2)$, $0 \to 2\,(3)$ and $2 \to 1\,(-2)$, Dijkstra finishes vertex $1$ first (distance $2$) and never revisits it, though $0 \to 2 \to 1$ costs $3 - 2 = 1$.

Do not try to repair negative weights by adding a constant to every weight: a path with more edges is penalised more, so the shortest path can change. Example: $0 \to 3$ costs $5$, while $0 \to 1 \to 3$ costs $2 + 2 = 4$ and is shorter; add $3$ to every edge and the direct edge costs $8$ while the two-edge path costs $10$: the shortest path is now the other one. Use Bellman-Ford when negative weights occur.

Running time

The work is: $V$ times "find the unfinished vertex with the smallest distance", and $E$ relaxations in all (one for each edge, when its tail is finished).

For a dense graph ($E \approx V^2$) the array version, $\Theta(V^2)$, is the best of the first two; for a sparse graph ($E \approx V$) the heap gives $\Theta(V \log V)$. A heap implemented without decrease-key (insert a new entry each time a distance improves and ignore stale entries) has $O(E)$ entries and the same $O(E \log V)$ bound. Space $\Theta(V)$ beyond the graph.

Relatives

• BFS is Dijkstra when every weight is $1$: the queue is the priority queue, because distances come out in non-decreasing order anyway.
• Prim has the same loop; its key is the weight of one edge to the tree, Dijkstra's key is the total distance from $s$ (Kruskal and Prim).
• The shortest paths from one source form a tree (the parents); it is in general not the minimum spanning tree.
• Dijkstra for a single target can stop as soon as the target is finished.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Dijkstra is a greedy algorithm built on the binary heap; with all weights equal it is BFS. It is compared with Bellman-Ford, which allows negative edges, and has the same structure as Prim's algorithm.

PYQs

Let G be any undirected graph with positive edge
weights, and T be a minimum spanning tree of G.
For any two vertices, u and v, let d1(u,v) and d2(u,v)
be the shortest distances between u and v in G and
T, respectively. Which ONE of the options is
CORRECT for all possible G, T, u and v?

Let G be an edge-weighted undirected graph with
positive edge weights. Suppose a positive constant α
is added to the weight of every edge. Which ONE of
the following statements is TRUE about the
minimum spanning trees (MSTs) and shortest paths
(SPs) in G before and after the edge weight update?

Let G be a weighted connected undirected graph
with distinct positive edge weights. If every edge
weight is increased by the same value, then which
of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does
not change

Consider the directed graph shown in the figure
below. There are multiple shortest paths between
vertices S and T. Which one will be reported by
Dijkstra's shortest path algorithm? Assume that, in
any iteration, the shortest path to a vertex v is
updated only when a strictly shorter path to v is
discovered.

Dijkstra's single source shortest path algorithm
when run from vertex a in the above graph,
computes the correct shortest path distance to

Consider a weighted, undirected graph with positive
edge weights and let u v be an edge in the graph. It is
known that the shortest path from the source vertex s
to u has weight 53 and the shortest path from s to v
has weight 65. Which one of the following statements
?

Let G(V,E) be an undirected graph with positive
edge weights. Dijkstra's single source shortest path
algorithm can be implemented using the binary
heap data structure with time complexity:

Self-check

Revision card

References