Reading a Relaxation Trace
In a weighted digraph, relaxing an edge means comparing the best cost currently recorded at its tail with the cost of taking that edge. The calculation is simple, but its meaning depends on the current labels: a value obtained early in a scan may improve later, and a value that does not change during one scan is not thereby known to be shortest. A careful trace records the edge order, each candidate value, and every resulting change.
Throughout, the examples use finite directed graphs with real edge weights. A directed walk from \(s\) to \(v\) is a sequence of vertices beginning at \(s\), ending at \(v\), and following directed edges; its cost is the sum of those edge weights. A directed path is a directed walk with no repeated vertices. The shortest-path distance \(d(s,v)\) is the infimum of the costs of all directed walks from \(s\) to \(v\); it is \(\infty\) if \(v\) is unreachable and may be \(-\infty\) if a reachable negative-weight cycle can be used repeatedly.
The comparison is strict. A candidate equal to the current label does not change the label or its predecessor. A finite label is called tentative when it is a current estimate that has not been certified as the shortest-path distance. In this tutorial, a label is finalized only when there is a valid reason to know it equals \(d(s,v)\); merely finishing a chosen list of edge relaxations is not such a reason.
What Relaxation Guarantees
Proof. We prove the walk claim by induction on the number of relaxations performed. Initially, the only finite label is \(\ell(s)=0\), witnessed by the length-zero walk at \(s\), whose cost is \(0\). Suppose the claim holds before a relaxation of \(u\to v\) with weight \(w\). If \(\ell(u)=\infty\), or if the candidate is not strictly smaller than \(\ell(v)\), no label changes, so every finite label still has its existing walk witness. Otherwise \(\ell(u)\) is finite and, by the induction hypothesis, is the cost of a walk from \(s\) to \(u\). Appending \(u\to v\) gives a walk to \(v\) of cost \(\ell(u)+w\), exactly the new label. The other labels are unchanged. Thus every finite label is always a walk cost. Since \(d(s,v)\) is the infimum of all such walk costs, \(\ell(v)\ge d(s,v)\). Finally, an update replaces \(\ell(v)\) only by a strictly smaller value, and a non-update leaves it unchanged, so labels never increase. \(\square\)
This theorem explains why labels are useful but not automatically exact: each finite label is supported by a real walk, but another walk may be cheaper. If a reachable negative cycle makes \(d(s,v)=-\infty\), no finite label can equal that distance. When there is no reachable negative cycle, reachable vertices have finite shortest-path distances, but a trace still needs evidence that a label has attained one.
Proof. We use induction on \(i\). Before any edge is relaxed, \(\ell(v_0)=\ell(s)=0\), which is the cost of the length-zero prefix. Suppose just before relaxing \(v_{i-1}\to v_i\), the tail label is at most the cost of the prefix ending at \(v_{i-1}\). Adding the edge weight \(w(v_{i-1}v_i)\) shows that the candidate is at most the cost of the prefix ending at \(v_i\). Relaxation either installs that candidate or retains a label no larger than it. Therefore the asserted bound holds after this relaxation. The argument does not require consecutive processing: intervening relaxations cannot increase the tail label. \(\square\)
The proposition gives an upper bound from a path, not an equality: a label might already be smaller because a different walk was found. It also shows why processing the edges of a path in the right order can carry a useful value forward, while processing them in another order can delay that information.
Tracing Labels and Predecessors
Worked Example: A Negative Edge and a Repeated Relaxation
Let \(V=\{s,a,b,t\}\) and let the weighted directed edges be \(s\to a\) of weight \(2\), \(s\to b\) of weight \(5\), \(a\to b\) of weight \(-4\), \(b\to t\) of weight \(3\), and \(a\to t\) of weight \(6\). Use source \(s\). Process the edges in this exact order: \(s\to b\), \(b\to t\), \(s\to a\), \(a\to b\), \(a\to t\), and then process \(b\to t\) once more.
Initially, \((\ell(s),\ell(a),\ell(b),\ell(t))=(0,\infty,\infty,\infty)\). The candidate is the current tail label plus the edge weight. The table records the labels after each edge; a dash means the edge causes no update.
| Edge processed | Candidate | Update | Labels \((s,a,b,t)\) afterward |
|---|---|---|---|
| \(s\to b\), weight \(5\) | \(0+5=5\) | \(\ell(b):\infty\to5\) | \((0,\infty,5,\infty)\) |
| \(b\to t\), weight \(3\) | \(5+3=8\) | \(\ell(t):\infty\to8\) | \((0,\infty,5,8)\) |
| \(s\to a\), weight \(2\) | \(0+2=2\) | \(\ell(a):\infty\to2\) | \((0,2,5,8)\) |
| \(a\to b\), weight \(-4\) | \(2+(-4)=-2\) | \(\ell(b):5\to-2\) | \((0,2,-2,8)\) |
| \(a\to t\), weight \(6\) | \(2+6=8\) | No update: \(8=8\) | \((0,2,-2,8)\) |
| \(b\to t\), weight \(3\), repeated | \(-2+3=1\) | \(\ell(t):8\to1\) | \((0,2,-2,1)\) |
The final predecessor pointers are \(\operatorname{pred}(a)=s\), \(\operatorname{pred}(b)=a\), and \(\operatorname{pred}(t)=b\). The associated walk to \(t\) is \(s,a,b,t\), of cost \(2+(-4)+3=1\). To check that the final labels are shortest distances, list the source-to-\(b\) possibilities: the direct route has cost \(5\), while \(s,a,b\) has cost \(2+(-4)=-2\). The source-to-\(t\) paths have costs \(5+3=8\), \(2+6=8\), and \(2+(-4)+3=1\). Thus the minimum costs are \(\ell(a)=2\), \(\ell(b)=-2\), and \(\ell(t)=1\); all three labels are certified as exact in this graph.
This trace illustrates why an edge may need to be processed again: when \(b\to t\) was first used, the label at \(b\) was \(5\); after \(a\to b\) lowered that label to \(-2\), the earlier calculation for \(t\) no longer represented the best route through \(b\). An edge relaxation uses the current tail label, not a value remembered from a previous step.
Worked Example: A Tentative Label Can Improve Later
Let \(V=\{s,a,b,t\}\), with directed edges \(s\to t\) of weight \(10\), \(s\to a\) of weight \(2\), \(a\to t\) of weight \(3\), \(s\to b\) of weight \(4\), and \(b\to t\) of weight \(1\). Starting from \(s\), process the edges in exactly that order.
The initial labels are \((0,\infty,\infty,\infty)\), in the order \((s,a,b,t)\). Relaxing \(s\to t\) gives candidate \(0+10=10\), so \(\ell(t)=10\) and \(\operatorname{pred}(t)=s\). This value is tentative: it is the cost of a route found so far, not a proof that no cheaper route exists. Next, \(s\to a\) gives \(0+2=2\), so \(\ell(a)=2\). Relaxing \(a\to t\) gives \(2+3=5\), improving \(\ell(t)\) from \(10\) to \(5\) and setting \(\operatorname{pred}(t)=a\). Then \(s\to b\) gives \(0+4=4\), so \(\ell(b)=4\). Finally, \(b\to t\) gives \(4+1=5\). Because the comparison is strict and \(5\) is not less than the current label \(5\), neither the label nor its predecessor changes.
The final labels are \((0,2,4,5)\). The two paths to \(t\) through \(a\) and \(b\) each cost \(2+3=5\) and \(4+1=5\), respectively; the direct path costs \(10\). These are all the source-to-\(t\) paths, so \(d(s,t)=5\). The predecessor pointer records the route through \(a\), one of the two shortest paths. In particular, the earlier label \(10\) was not finalized just because it was finite, and the final tie did not force a predecessor change.
Why Edge Order Matters
Worked Example: One Scan Can Miss a Better Route
Let \(V=\{s,a,b,c\}\), with directed edges \(s\to c\) of weight \(9\), \(s\to a\) of weight \(1\), \(a\to b\) of weight \(2\), and \(b\to c\) of weight \(2\). Start with \((\ell(s),\ell(a),\ell(b),\ell(c))=(0,\infty,\infty,\infty)\). Make one scan in this order: \(s\to c\), \(b\to c\), \(a\to b\), \(s\to a\).
Relaxing \(s\to c\) gives \(0+9=9\), so \(\ell(c)=9\). At \(b\to c\), the tail label is still \(\infty\), so this edge makes no change. Relaxing \(a\to b\) also makes no change because \(\ell(a)=\infty\). Finally \(s\to a\) gives \(0+1=1\), so \(\ell(a)=1\). After the scan, the labels are \((0,1,\infty,9)\). In particular, the scan has not found the route to \(c\) through \(a\) and \(b\).
Now scan the same ordered list again. The edge \(s\to c\) proposes \(0+9=9\), which ties the current label. The edge \(b\to c\) proposes no finite value yet, since \(\ell(b)=\infty\). The edge \(a\to b\) proposes \(1+2=3\), so \(\ell(b)\) becomes \(3\). The edge \(s\to a\) proposes \(0+1=1\), which ties the current label. The second scan ends with labels \((0,1,3,9)\), still without updating \(c\), because \(b\to c\) was processed before \(a\to b\) in this scan.
A third scan in that same order begins with \(s\to c\), which ties at \(9\), and then \(b\to c\) has candidate \(3+2=5\). This improves \(\ell(c)\) to \(5\), with \(\operatorname{pred}(c)=b\). The remaining edges tie their existing labels: \(a\to b\) proposes \(1+2=3\), and \(s\to a\) proposes \(0+1=1\). The final labels are \((0,1,3,5)\). The only source-to-\(c\) paths are the direct path of cost \(9\) and \(s,a,b,c\), of cost \(1+2+2=5\), so \(5\) is the shortest-path distance.
Common mistake. After the first scan in the example, it is wrong to conclude that \(c\)'s shortest-path distance is \(9\) because its label did not change again during that scan. The calculation \(\ell(b)+2=\infty+2\) is not a finite candidate: at the time that edge was processed, \(b\) had not yet received its label. Later, \(a\to b\) sets \(\ell(b)=1+2=3\), and a subsequent relaxation of \(b\to c\) gives \(3+2=5<9\). The correction is to distinguish the current tentative value \(9\) from a certified distance, and to recognize that a scan's edge order may delay information.
When checking a trace, write down the labels immediately before each relaxation. Using a tail label from a later step, or silently reordering the edges, changes the computation. Also record whether an edge is being processed once or revisited: a repeated relaxation can use a newly improved tail label and produce a different candidate.
Check Your Understanding
For each question, show the candidate values in the stated order and distinguish the resulting tentative labels from any distances you can certify.
- Let \(V=\{s,x,y\}\), with edges \(s\to x\) of weight \(6\), \(s\to y\) of weight \(2\), and \(y\to x\) of weight \(1\). Starting from \(s\), trace the order \(s\to x,\ s\to y,\ y\to x\). What is the final label at \(x\), and which path witnesses it?
- In the preceding graph, what happens to the predecessor of \(x\) if \(y\to x\) is relaxed before \(s\to x\)? Explain why both orders can give the same final shortest-path distance.
- Give an example of a finite label that is not yet certified as a shortest-path distance. State what additional calculation or argument would certify it.
- Prove that if a relaxation does not produce a strict improvement, the destination label and its predecessor pointer both remain unchanged under the rule in the definition.
- For the graph in the third worked example, explain why two scans in the stated order do not yet update \(c\), even though the path of cost \(5\) exists.