= Tentative distance
{title2=$d(v)$}
A tentative distance $d(v)$ is the cheapest cost so far recorded by a <shortest path problem> <algorithm>. For the single-source convention, initialize $d(s)=0$ and $d(v)=\infty$ elsewhere. Every finite label is the cost of a discovered route from $s$ to $v$, so
$$
\delta(s,v)\le d(v).
$$
It is an <upper bound> supplied by an actual route, not a guess that might be too low. The <loop invariant> follows directly from <edge relaxation>: extending a discovered route to $u$ by $u\to v$ supplies another discovered route. The usual label initialization and this safety property are stated and proved in the authored MIT notes.https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/6277a1f06100c26a7ff21031af6757b5_MIT6_006F11_lec16.pdf[MIT 6.006, Lecture 16, p. 1: relaxation safety]{ref}
In the trace under <edge relaxation>, $d(t)=10$ first records the direct <directed path> $s\to t$. Later $d(t)=8$ records $s\to a\to t$, and finally $d(t)=3$ records $s\to b\to a\to t$. Each label is a usable route cost, but the first two are not shortest. An infinite <tentative distance> means no route has yet been discovered; only a completed search establishes unreachability. The isolated <vertex> $z$ in that example remains at $\infty$.
In a <directed graph>, the discovered route is formally a <directed walk>, which may repeat <vertices>; in the pictured acyclic <graph> it is always a <directed path>. Negative-cost <directed cycles> can keep supplying cheaper <directed walks> without a finite optimum. In the all-to-one convention, the same meaning applies to discovered routes \i[from] $i$ \i[to] $r$. Do not confuse either version with the <lower bounds> supplied by feasible potentials in the <Bellman inequalities>: one records something achievable, the other rules out anything cheaper.
Back to article page
