From Relaxation to a Shortest-Path Algorithm
Edge relaxation improves a distance label when a newly considered route gives a smaller cost. Dijkstra’s algorithm organizes these improvements so that, under a nonnegative-weight condition, it can permanently finalize distances one vertex at a time. The method applies to directed graphs; the direction of each edge matters, because a route may use an edge only in its stated direction.
Let \(G=(V,E)\) be a finite directed graph with a weight \(w(e)\) assigned to each edge \(e\). A directed path from \(s\) to \(v\) is a sequence beginning at \(s\), ending at \(v\), and following the direction of every edge. Its cost is the sum of the weights of its edges. The shortest-path distance from \(s\) to \(v\), written \(\operatorname{dist}(s,v)\), is the minimum cost of such a path, or \(\infty\) if no path exists. In this tutorial, every edge weight satisfies \(w(e)\ge 0\).
At initialization, \(D(s)=0\) and \(D(v)=\infty\) for every \(v\ne s\); no vertex is settled. To process an unsettled vertex \(u\), examine each outgoing edge \(uv\) whose endpoint \(v\) is unsettled. Relax that edge by replacing \(D(v)\) with \(\min\{D(v),D(u)+w(uv)\}\). If there is a tie for the smallest unsettled label, either tied vertex may be selected.
Set \(D(s)=0\), all other labels to \(\infty\), and the settled set to empty.
Choose an unsettled vertex with minimum label. If that label is \(\infty\), stop.
Mark the selected vertex \(u\) settled. For each outgoing edge \(uv\) to an unsettled vertex, replace \(D(v)\) by \(D(u)+w(uv)\) if that value is smaller than \(D(v)\).
Continue with Step 2. When the algorithm stops, finite labels are shortest-path distances; vertices still labelled \(\infty\) are unreachable from \(s\).
Relaxation is a comparison: if \(D(u)+w(uv)\) is not smaller than the current \(D(v)\), the label stays as it is. In particular, equal-cost alternatives do not require an update. The algorithm’s stopping rule matters: if the smallest unsettled label is \(\infty\), no remaining vertex can be reached from the source.
Worked Traces
Worked Example: Several Improvements Before a Vertex Is Settled
Take the directed graph \(V=\{s,a,b,c,t\}\), with edge set and weights \(s\to a:4\), \(s\to b:1\), \(b\to a:2\), \(a\to c:1\), \(b\to c:5\), \(a\to t:7\), \(c\to t:3\), and \(b\to t:10\). Begin at \(s\). Each table row gives the labels after the listed vertex has been selected and its outgoing edges relaxed.
| Action | \(D(s)\) | \(D(a)\) | \(D(b)\) | \(D(c)\) | \(D(t)\) |
|---|---|---|---|---|---|
| Initialize | 0 | \(\infty\) | \(\infty\) | \(\infty\) | \(\infty\) |
| Select \(s\) | 0 | 4 | 1 | \(\infty\) | \(\infty\) |
| Select \(b\) | 0 | 3 | 1 | 6 | 11 |
| Select \(a\) | 0 | 3 | 1 | 4 | 10 |
| Select \(c\) | 0 | 3 | 1 | 4 | 7 |
| Select \(t\) | 0 | 3 | 1 | 4 | 7 |
After selecting \(s\), the outgoing edges give \(D(a)=0+4=4\) and \(D(b)=0+1=1\). The minimum unsettled label is \(1\), so select \(b\). Its edge to \(a\) gives \(1+2=3<4\), updating \(D(a)\) to \(3\); its edge to \(c\) gives \(1+5=6\); and its edge to \(t\) gives \(1+10=11\). Next select \(a\), whose label is \(3\). The edge to \(c\) gives \(3+1=4<6\), and the edge to \(t\) gives \(3+7=10<11\). Select \(c\), now with label \(4\): its edge to \(t\) gives \(4+3=7<10\). Finally, \(t\) is selected with label \(7\), and there are no outgoing edges to relax.
Check: the route \(s\to b\to a\to c\to t\) has cost \(1+2+1+3=7\), matching \(D(t)\). The final labels also satisfy the edge inequalities: for example, \(D(a)=3\le D(b)+2=3\), \(D(c)=4\le D(a)+1=4\), and \(D(t)=7\le D(c)+3=7\). The table shows why a label is only tentative until its vertex is selected: \(D(a)\) falls from \(4\) to \(3\), and \(D(t)\) falls from \(11\) to \(7\).
Worked Example: Unreachable Vertices and a Zero-Weight Edge
Let \(V=\{s,p,q,z\}\), with directed weighted edges \(s\to p:2\), \(p\to q:0\), and \(q\to p:1\). Vertex \(z\) has no incident edges. Run the algorithm from \(s\).
| Action | \(D(s)\) | \(D(p)\) | \(D(q)\) | \(D(z)\) |
|---|---|---|---|---|
| Initialize | 0 | \(\infty\) | \(\infty\) | \(\infty\) |
| Select \(s\) | 0 | 2 | \(\infty\) | \(\infty\) |
| Select \(p\) | 0 | 2 | 2 | \(\infty\) |
| Select \(q\) | 0 | 2 | 2 | \(\infty\) |
| Stop: minimum label is \(\infty\) | 0 | 2 | 2 | \(\infty\) |
Selecting \(s\) gives \(D(p)=0+2=2\). Selecting \(p\) gives \(D(q)=2+0=2\); a zero-weight edge is allowed and can produce an equal label at two different vertices. When \(q\) is selected, the edge back to \(p\) proposes \(2+1=3\), which is not smaller than \(D(p)=2\), so there is no update. There is no finite label for \(z\), so the algorithm stops rather than selecting it.
Check: the paths from \(s\) to \(p\) and \(q\) have costs \(2\) and \(2+0=2\), respectively. No edge leads to \(z\), so \(z\) is unreachable and its distance is \(\infty\).
Worked Example: Ties in the Minimum Label
Let \(V=\{r,u,v,w\}\), with directed weighted edges \(r\to u:0\), \(r\to v:0\), \(u\to v:0\), \(v\to w:2\), and \(u\to w:2\). Starting at \(r\), both \(u\) and \(v\) have minimum label \(0\) after \(r\) is processed. Choose \(u\) first.
| Action | \(D(r)\) | \(D(u)\) | \(D(v)\) | \(D(w)\) |
|---|---|---|---|---|
| Initialize | 0 | \(\infty\) | \(\infty\) | \(\infty\) |
| Select \(r\) | 0 | 0 | 0 | \(\infty\) |
| Select \(u\) | 0 | 0 | 0 | 2 |
| Select \(v\) | 0 | 0 | 0 | 2 |
| Select \(w\) | 0 | 0 | 0 | 2 |
Relaxing \(u\to v\) proposes \(0+0=0\), equal to the current label \(D(v)=0\), so it does not change. Relaxing \(u\to w\) sets \(D(w)=0+2=2\). Then select \(v\); its edge to \(w\) proposes \(0+2=2\), again equal to the current label. Either choice between \(u\) and \(v\) is valid.
Check: the routes \(r\to u\to w\) and \(r\to v\to w\) each have cost \(0+2=2\). The labels \(D(u)=0\) and \(D(v)=0\) are attained by the direct edges from \(r\), so the final labels agree with these route costs.
Why the Algorithm Works
Proof. First, the algorithm terminates: each selection settles one previously unsettled vertex, and no vertex is selected twice. There are only \(|V|\) vertices, so after at most \(|V|\) selections, either the algorithm stops because the minimum unsettled label is \(\infty\), or every vertex is settled.
Every finite label maintained by the algorithm is the cost of some directed route from \(s\) to its vertex. This holds initially for \(s\), whose empty route has cost \(0\). Whenever relaxation creates a finite label \(D(v)=D(u)+w(uv)\), it extends a route represented by \(D(u)\) with the edge \(uv\). Thus no finite label can be less than the true shortest-path distance to its vertex.
We now show that whenever a vertex \(u\) is selected with finite label, that label equals its shortest-path distance. Use induction on the number of selections with finite labels. The first such vertex is \(s\), with label \(0=\operatorname{dist}(s,s)\). Suppose the claim holds for all previously selected vertices, and consider the next selected vertex \(u\). Choose a shortest path from \(s\) to \(u\). A shortest path can be taken to have no repeated vertices: deleting a section between two occurrences of the same vertex removes a closed route of nonnegative cost, so does not increase the path cost.
Starting along this path from \(s\), let \(x\) be the first vertex not yet settled. Such a vertex exists because \(u\) is not settled before its selection. Let \(y\) be the vertex immediately before \(x\) on the path. The source is already settled, so \(y\) is settled. When \(y\) was selected, the algorithm relaxed the edge \(yx\); because \(x\) was then unsettled, this gave \(D(x)\) a label at most the cost of the path prefix from \(s\) through \(x\). Nonnegative weights imply that this prefix cost is at most the cost of the whole shortest path to \(u\). Since \(u\) has the minimum label among unsettled vertices at its selection, \(D(u)\le D(x)\). Therefore \(D(u)\le\operatorname{dist}(s,u)\). The route interpretation established above gives the reverse inequality, so \(D(u)=\operatorname{dist}(s,u)\).
It remains to account for vertices left unsettled when the algorithm stops. The stopping rule means that all their labels are \(\infty\). If any such vertex were reachable, a path from \(s\) to it would have a first unsettled vertex whose predecessor on that path was settled. Relaxing the edge between them would have assigned the first unsettled vertex a finite label. That contradicts stopping with all unsettled labels infinite. Thus every vertex left unsettled is unreachable. Conversely, a reachable vertex receives a finite label when the first edge leaving the settled portion of a path to it is relaxed, so it cannot be left with label \(\infty\). The finite labels and the unreachable-vertex labels are therefore exactly as claimed. \(\square\)
The nonnegative-weight hypothesis is used in the proof when comparing a shortest path’s prefix cost with its full cost. A negative edge can make that prefix comparison fail: a route that first appears expensive may become cheaper after a later negative edge. Dijkstra’s selection rule is not justified in that setting.
Common Pitfall: Applying the Method to a Negative Edge
Consider the directed graph \(V=\{s,a,b\}\) with weighted edges \(s\to a:2\), \(s\to b:5\), and \(b\to a:-10\). This graph violates the hypothesis. If the algorithm is applied anyway, it first assigns \(D(a)=2\) and \(D(b)=5\), then selects \(a\) and settles it. After selecting \(b\), the route through \(b\to a\) has cost \(5+(-10)=-5\), but \(a\) has already been settled and its label is not changed. The algorithm would report \(2\) for \(a\), although the route \(s\to b\to a\) has cost \(-5\). The correction is not to change the selection order informally; it is to use an algorithm whose hypotheses allow negative weights.
For nonnegative weights, keep three distinctions clear: labels are tentative until selection, ties may be resolved either way, and an infinite minimum label signals that the remaining vertices are unreachable. The algorithm’s guarantee depends on all edge weights being nonnegative, including edges that have not yet been examined.
Check Your Understanding
For each question, state the relevant labels or condition explicitly.
- In the first worked example, what label does relaxing \(b\to a\) propose, and why does it replace the earlier label of \(a\)?
- Why can a vertex with label \(\infty\) be left unsettled when the algorithm stops?
- In the third worked example, why does the edge \(u\to v\) not change \(D(v)\)?
- Which step in the correctness proof uses the nonnegative-weight assumption?
- Give a directed graph with a negative edge on which settling the current minimum label can prevent the algorithm from finding a shortest distance.