Dijkstra’s Algorithm Computes Shortest Paths on Non-Negative Weights
Statement
Let \(G = (V, E)\) be a directed graph with edge weights \(w : E \to \mathbb{R}_{\ge 0}\) and source \(s \in V\). Run Dijkstra’s algorithm from \(s\). When the algorithm terminates, \(D[v] = d(v)\) for every \(v\), where \[ d(v) = \min_{P \,:\, s \to v} \sum_{e \in P} w(e) \] is the true shortest-path distance (\(+\infty\) if \(v\) is unreachable) (Dijkstra 1959; Cormen et al. 2009).
Setup
Recall the algorithm. Maintain \(D[v]\) initialized to \(0\) at \(s\) and \(+\infty\) elsewhere. Maintain a set \(S\) of settled vertices, initially empty. Repeatedly:
- Extract from the priority queue the vertex \(u \notin S\) with smallest \(D[u]\).
- Add \(u\) to \(S\).
- For each edge \((u, v)\), relax: if \(D[u] + w(u, v) < D[v]\), set \(D[v] := D[u] + w(u, v)\).
Note one elementary property used throughout: a relaxation \(D[v] := D[u] + w(u, v)\) only ever happens if it lowers \(D[v]\), so \(D[v]\) is monotonically non-increasing and always equals the length of some path from \(s\) to \(v\) (or remains \(+\infty\)).
Main invariant
Invariant. When a vertex \(u\) is added to \(S\), \(D[u] = d(u)\).
This is the only fact we need; once it holds at the moment of settling, no later relaxation of any edge into \(u\) can decrease \(D[u]\) (by the monotonicity property and the fact that \(d(u)\) is already the minimum).
Proof of the invariant
By induction on the order in which vertices are added to \(S\).
Base case. The first vertex extracted is \(s\) with \(D[s] = 0 = d(s)\).
Inductive step. Suppose the invariant holds for every vertex settled before \(u\). We show \(D[u] = d(u)\) at the moment \(u\) is extracted.
Since \(D[u]\) is achieved by some \(s\)-to-\(u\) path, \(D[u] \ge d(u)\). We now show \(D[u] \le d(u)\).
Assume for contradiction \(D[u] > d(u)\). Let \(P^* = (s = v_0, v_1, \dots, v_k = u)\) be a true shortest \(s\)-to-\(u\) path, so \(\sum_{i=1}^k w(v_{i-1}, v_i) = d(u)\).
Walk along \(P^*\) from \(s\) and let \(y = v_j\) be the first vertex on \(P^*\) that is not in \(S\) at the moment \(u\) is extracted (such a \(y\) exists because \(u\) itself is not in \(S\)). Let \(x = v_{j-1}\) be its predecessor on \(P^*\); then \(x \in S\).
By the inductive hypothesis applied at the time \(x\) was settled, \(D[x] = d(x)\). Immediately after \(x\) was settled, the algorithm relaxed the edge \((x, y)\), ensuring \[ D[y] \le D[x] + w(x, y) = d(x) + w(x, y). \] Because \(P^*\) is a shortest path, every prefix is also shortest, so \(d(x) + w(x, y) = d(v_j)\). Therefore \[ D[y] \le d(v_j). \]
Now use the non-negativity of edge weights. The suffix of \(P^*\) from \(v_j\) to \(u\) has non-negative total weight, so \(d(v_j) \le d(u)\). Combining: \[ D[y] \le d(v_j) \le d(u) < D[u]. \]
But the algorithm always extracts the unsettled vertex with the smallest \(D\) value. Since \(y\) is unsettled and \(D[y] < D[u]\), the algorithm should have extracted \(y\) before \(u\) — contradicting our assumption that \(u\) was just extracted. Hence \(D[u] = d(u)\).
Where non-negativity is used
The crucial step is \(d(v_j) \le d(u)\), which fails when negative-weight edges are allowed: a long path through negative edges can reach a vertex \(u\) with \(d(u) < d(v_j)\), breaking the priority-queue argument. This is why Dijkstra is restricted to non-negative weights, and why Bellman-Ford is needed for graphs with negative edges.
Termination and unreachable vertices
Each vertex is extracted from the priority queue at most once, so the algorithm terminates after at most \(|V|\) extractions. For any vertex \(u\) not extracted, \(D[u]\) remains at its initial value of \(+\infty\), correctly reflecting that \(u\) is unreachable from \(s\) (otherwise some sequence of relaxations along a path from \(s\) would have driven \(D[u]\) below \(+\infty\), and \(u\) would have been a candidate for extraction).