= Bellman inequalities
{c}
{title2=$d_i\le c_{ij}+d_j$}
The Bellman inequalities turn local <directed edge> checks into a global certificate for the <shortest path problem>. Here the convention is \i[all-to-one]: every journey ends at a fixed <vertex> $r$, and $c_{ij}$ is the cost of the original <directed edge> $i\to j$. Work in a finite <directed graph> with finite real costs. Write $L_i$ for candidate labels, normalized by $L_r=0$, on the <vertices> that can reach $r$. A feasible potential means precisely that these finite labels satisfy
$$
L_i\le c_{ij}+L_j
$$
for every <directed edge> within that set. These labels give <lower bounds> on costs \i[to] $r$. A discovered <directed path> of cost $U_i$ instead gives an <upper bound>. The following constructed <graph> shows both bounds and the exact distances between them; its weights are illustrative costs, not measured travel data.
\Image[/edge-relaxation-certificate.png]
{title=<Bellman inequalities> and explicit <directed paths> certify distances to $r$ from opposite sides}
The arrows in the picture point toward the destination, whereas <edge relaxation> propagates an improved label in the opposite direction: an improved $d_j$ can lower $d_i$. In the pictured <graph>, the <directed paths> from $a$ to $r$ cost $7$, $2+3=5$, and $2-2+4=4$. Thus $\delta(a,r)=4$. The candidate $L=(3,1,3,0)$ in <vertex> order $(a,b,c,r)$ is feasible, but underestimates the exact distances $(4,2,4,0)$. Merely satisfying the <Bellman inequalities> does not make a candidate exact.
Why do they give <lower bounds>? Along any <directed path> $i=v_0\to v_1\to\cdots\to v_k=r$, successive substitution gives
$$
L_i\le\sum_{\ell=0}^{k-1}c_{v_\ell v_{\ell+1}}+L_r=\sum_{\ell=0}^{k-1}c_{v_\ell v_{\ell+1}}.
$$
The same calculation works for a <directed walk>, with repeated <vertices> allowed. Taking the <infimum> of route costs gives $L_i\le\delta(i,r)$. A discovered route gives $\delta(i,r)\le U_i$. If the bounds meet, $L_i=U_i$, they certify an optimum without enumerating routes. Equivalently, check the <Bellman inequalities> for the proposed distances and exhibit <directed paths> realizing them. The authored <Bellman-Ford algorithm> implementation checks the corresponding single-source inequalities and equality on recorded route <edges>; reversing every <directed edge> gives this all-to-one convention.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BellmanFordSP.java[Sedgewick and Wayne, BellmanFordSP.java, optimality checks]{ref}
For the exact labels in the picture, the slack $c_{ij}+d_j-d_i$ is respectively $0,3,1,0,0$ on $a\to b$, $a\to r$, $b\to r$, $b\to c$, $c\to r$. Zero slack means equality; the zero-slack <directed path> $a\to b\to c\to r$ realizes the cost $4$. This is the useful beauty of the certificate: a few local <inequalities> rule out every cheaper journey, while one explicit journey attains the bound.
Keep unreachable <vertices> separate: $\delta(i,r)=\infty$ when no <directed path> to $r$ exists, and a finite <lower bound> alone cannot certify that fact. Extended labels can use $\infty+c=\infty$ for finite $c$, but never compute a slack as $\infty-\infty$. If $i$ can reach a negative-cost <directed cycle> and then reach $r$, repeatedly traversing the <directed cycle> makes route costs unbounded below: their <infimum> is $-\infty$, with no finite shortest <directed walk>. A finite feasible potential on such a <directed cycle> is impossible, since summing its <Bellman inequalities> would give $0\le\sum c_{ij}<0$. A negative-cost <directed cycle> that cannot reach $r$ does not affect distances to $r$. These are statements about unrestricted <directed walks>; requiring a <directed path> with no repeated <vertices> is a different optimization problem when negative-cost <directed cycles> exist.https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/5edb13fb34cbe7f4cdccc13d131772e7_MIT6_006F11_lec17.pdf[MIT 6.006, Lecture 17, pp. 1 and 5: relevant negative cycles and simple paths]{ref}
For the single-source convention, the same original <directed edge> $u\to v$ instead gives $L(v)\le L(u)+w_{uv}$ with $L(s)=0$, a <lower bound> on distance \i[from] $s$. The endpoint carrying the label on the left therefore changes with the direction of the problem.
Back to article page
