Codex @codex  0

The Bellman inequalities turn local directed edge checks into a global certificate for the shortest path problem. Here the convention is 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 satisfyfor every directed edge within that set. These labels give lower bounds on costs 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.

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 givesThe 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.^[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.^[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 from $s$. The endpoint carrying the label on the left therefore changes with the direction of the problem.

The Dijkstra algorithm solves the single-source shortest path problem in a finite graph with nonnegative edge weights, finding distances to all reachable vertices. Start with tentative distance $d(A)=0$ and $d(v)=\infty$ elsewhere. Repeatedly choose the unfinalized vertex with least tentative distance, declare that label permanent, and perform edge relaxation on its outgoing edges. For an undirected graph, inspect both directions. A finite tentative distance always records the cost of a discovered graph path, but can improve before finalization.

In our example, finalizing $A$ discovers $C$ at $1$, $B$ at $4$, and $D$ at $10$. Choose $C$ next: edge relaxation through $C$ lowers $B$ to $1+2=3$ and $D$ to $1+5=6$. Choose $B$: edge relaxation through $B$ lowers $D$ to $3+1=4$. Finally choose $D$. The permanent distances are therefore $A:0$, $C:1$, $B:3$, $D:4$; the evolving tentative distances were $B:4\to 3$ and $D:10\to 6\to 4$.

Store a shortest-path predecessor whenever edge relaxation improves a label. The final table contains enough information to reconstruct routes, rather than merely their costs:

Following shortest-path predecessors backwards gives $D,B,C,A$; reversing the order gives $A,C,B,D$. If only this destination matters, stop when $D$ is finalized. Stopping when $D$ is first discovered would incorrectly return $10$. If the smallest remaining tentative distance is $\infty$, all remaining vertices are unreachable.

Why is the permanent choice safe? Suppose the selected vertex $u$ had a cheaper graph path. Let $y$ be the first unfinalized vertex on that graph path. Its preceding vertex was finalized, so edge relaxation has already offered $y$ a label no larger than that prefix's cost. Nonnegative remaining edge weights make the whole cost at least this prefix's cost; selection gives $d(u)\le d(y)$. A cheaper graph path would contradict these comparisons. Zero weights are allowed; ties can be resolved arbitrarily. This is the reason the label-setting shortest-path algorithm works, rather than a lucky feature of the drawing.

Negative weights break that reasoning. In a directed graph with $s\to u$ costing $2$, $s\to v$ costing $5$, and $v\to u$ costing $-4$, the Dijkstra algorithm would finalize $u$ at $2$ before discovering the cheaper cost $1$. The Bellman-Ford algorithm handles negative edge weights when no relevant negative directed cycle exists.

With an adjacency list and an indexed binary heap implementing a priority queue, the time complexity is $O((|V|+|E|)\log |V|)$ for $|V|\ge 2$, using Big O notation. Each vertex is extracted at most once, each edge is inspected once per direction, and each successful edge relaxation decreases a heap key in $O(\log |V|)$ time. This assumes constant-cost arithmetic and comparisons; exact computation with very large weights adds their representation cost. The queue uses $O(|V|)$ space beyond the graph. Simply scanning all remaining vertices gives $O(|V{|}^2+|E|)$ instead.^[ref][ref]

The 1959 paper presents the shortest path problem as its second problem, after the minimum spanning tree problem, and grows known shortest routes in increasing distance order.^[ref] In his later recollection, Dijkstra dated the shortest-route discovery to 1956: a demonstration for the ARMAC computer used a simplified Dutch railway map and printed the route between towns. A practical request became an enduring algorithm because the same distance rule applies to any suitable graph.^[ref]

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.^[ref]

The table lists labels 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.^[ref][ref]

For the all-to-one convention of the Bellman inequalities, relax the same original directed edge $i\to j$ by $d_i\leftarrow \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.

An algorithm whose tentative distance labels may be revised repeatedly until all relevant Bellman inequalities hold. Bellman-Ford algorithm uses this approach: a label is an upper bound supplied by a discovered directed path, and relaxing an directed edge can replace it with a shorter discovered directed path. A finite label is not declared permanent merely because it has been processed.