Edge relaxation
= Edge relaxation
{title2=$d(v)\gets\min\{d(v),d(u)+w_{uv}\}$}
Edge relaxation tests whether extending a recorded route by one <directed edge> improves a <tentative distance>. For a single source $s$ and an original <directed edge> $u\to v$ of weight $w_{uv}$, form the candidate $q=d(u)+w_{uv}$. If $d(u)$ is finite and $q<d(v)$, replace $d(v)$ by $q$ and record the <shortest-path predecessor> $\pi(v)=u$. Otherwise leave both unchanged. The <minimum> formula in the header gives the resulting label in either case. The authored implementation uses this strict comparison and records the incoming <directed edge>.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/DijkstraSP.java[Sedgewick and Wayne, DijkstraSP.java, relax method]{ref}
\Image[/edge-relaxation-trace.png]
{title=<Edge relaxation> lowers discovered-route costs, including across a negative-weight <directed edge>}
The table lists labels \i[after] each specified operation, keeping $d(s)=0$ throughout this constructed acyclic <graph>. Relaxing $a\to t$ first offers $6+2=8$. Relaxing $b\to a$ then offers $2-1=1$, lowering $a$ from $6$ to $1$; revisiting $a\to t$ now offers $1+2=3$. Finally $b\to t$ offers $2+7=9$, so the label $3$ stays. Changing a label can make a previously checked outgoing <directed edge> worth checking again. This trace illustrates the operation itself, with a deliberately specified order, rather than a run of the <Dijkstra algorithm>.
A single <edge relaxation> does not require nonnegative weights: its candidate is the cost of a real extended <directed walk>, even when the last <directed edge> has negative weight. Nonnegative weights are needed by the <Dijkstra algorithm> to make its selected minimum <tentative distance> permanent. The <Bellman-Ford algorithm> permits negative weights and revisits labels; its authored implementation also checks for reachable negative-cost <directed cycles>.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/DijkstraSP.java[Sedgewick and Wayne, DijkstraSP.java, nonnegative-weight precondition]{ref}https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BellmanFordSP.java[Sedgewick and Wayne, BellmanFordSP.java, signed weights and cycle detection]{ref}
For the all-to-one convention of the <Bellman inequalities>, relax the same original <directed edge> $i\to j$ by $d_i\gets\min\{d_i,c_{ij}+d_j\}$. This prepends $i\to j$ to a discovered route from $j$ to $r$, and improves the tail label $d_i$, not the head label $d_j$. Skip the operation when $d_j=\infty$. In exact arithmetic, a full pass over all relevant <directed edges> with no improvement establishes all their <Bellman inequalities>; combined with the discovered-route <upper bounds>, this certifies finite distances. One unsuccessful operation establishes only that this particular candidate did not improve its label at that moment.