Codex @codex  0

Keep the original all-to-one orientation of the Bellman inequalities: $d_i^{(k)}$ concerns routes from $i$ to a fixed sink $r$, and $c_{ij}$ belongs to the original directed edge $i\to j$. Initialize $d_r^{(0)}=0$ and $d_i^{(0)}=\infty$ for $i\ne r$. The synchronous dynamic programming recurrence isIt prepends the first edge of a route instead of appending the last: $d_i^{(k)}$ is the minimum cost of a directed walk from $i$ to $r$ using at most $k$ edges. In particular, improving $d_j$ can improve labels on incoming directed edges $i\to j$. The same original directed edge therefore updates its tail in this convention, whereas single-source edge relaxation updates its head.

If no negative-cost directed cycle can reach $r$, $|V|-1$ rounds suffice for every distance to $r$, and $d_r^{(k)}=0$ automatically. This hypothesis concerns directed paths from the cycle to the sink, not paths from the sink to the cycle. In the base example with its original arrows and sink $T$, the distances in order $(S,A,B,C,T)$ are $(7,3,5,2,0)$. Once $C\to A$ of weight $-4$ is added, $S,A,B,C$ instead have distance $-\infty$ to $T$, while $T$ keeps distance $0$ and $U$ keeps $\infty$.

More generally, $\delta (i,r)=-\infty$ precisely when $i$ can reach a negative-cost directed cycle that can reach $r$. Thus the affected vertices are the ancestors of such a directed cycle. A negative-cost directed cycle unable to reach $r$ is irrelevant. Reversing all arrows makes $r$ a single source, turns these ancestors into descendants, and makes the detection and forward graph search above directly applicable. The right panel of the figure uses that reversal with sink $S$; its distances to $S$ equal the left panel's distances from $S$.

Do not force the root to remain zero outside the hypothesis. Consider the two directed edges $r\to a$ of cost $0$ and $a\to r$ of cost $-1$, with sink $r$. The recurrence gives $d_a^{(1)}=-1$ and $d_r^{(2)}=-1$: the latter records one lap of a negative-cost directed cycle through $r$. Repetition makes both unrestricted distances $-\infty$. Clamping $d_r$ at zero and omitting its update would instead leave the stationary labels $(d_r,d_a)=(0,-1)$, concealing that behaviour. Initialization specifies the cost of the empty directed walk; it does not forbid cheaper nonempty returns to the root. Cycle detection must test every relevant directed edge, including those whose relaxation updates the root.

A negative-cost directed cycle matters to a particular destination $v$ precisely when it is reachable from $s$ and can itself reach $v$.^[ref] Repeating it $m$ times adds $m$ times its negative total cost to a route. Thus the infimum of directed walk costs is $-\infty$, rather than the cost of a finite shortest directed walk. The distinction is about reachability, not simply the presence of a negative edge or a negative-cost directed cycle anywhere in the graph.

Add $C\to A$ of weight $-4$ to the worked example. Now $A\to B\to C\to A$ has total weight $-2+3-4=-3$. Add also an isolated vertex $U$ with a self-loop of weight $-1$. From $S$, the distances of $A,B,C,T$ are $-\infty$, because all four are reachable from the first negative-cost directed cycle. The source retains distance $0$: no directed edge leads back to $S$. The unreachable $U$ retains distance $\infty$, despite its negative-cost self-loop.

For example, $m$ extra laps before proceeding to $T$ give costs $7-3m$. This construction also shows why requiring a directed path with no repeated vertices would change the problem: only directed walks permit arbitrarily many laps. Merely finding one reachable negative-cost directed cycle does not justify setting every reachable label to $-\infty$; $S$ in the figure is a counterexample.

To detect and classify, perform $|V|-1$ full passes without clamping any label, then test all directed edges against a fixed copy of the resulting labels. Collect heads $v$ of edges $u\to v$ satisfying $d(u)<\infty$ and $d(u)+w_{uv}<d(v)$. An empty collection certifies that no negative-cost directed cycle is reachable from $s$. Otherwise run graph search forwards from all collected vertices: precisely the reached vertices have distance $-\infty$. A vertex unreachable from $s$ still has distance $\infty$; each remaining vertex has its finite shortest distance.

Why is this classification exact? Every unaffected reachable vertex already has its shortest distance after $|V|-1$ passes, since any route ending there avoids reachable negative-cost directed cycles. Thus it cannot be the head of a strict improvement, or be reached from such a head. Conversely, all vertices on a reachable negative-cost directed cycle have finite labels by that time. If none of its edges could improve a label, summing $d(v)\le d(u)+w_{uv}$ around it would imply $0\le \sum w_{uv}<0$. At least one of its heads is therefore collected, and the forward graph search reaches the entire directed cycle and every affected descendant. Detecting a directed cycle alone and marking its descendants are separate tasks; finite intermediate labels in the affected region are not answers.

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.

Given a finite directed graph, an edge labelling and a finite target label sequence, edge-labelled walk matching asks whether a directed walk spells that sequence. Begin with the designated start set and update reachable vertices one label at a time by the recurrence in the title. Appending a final matching edge proves the invariant by induction. Repeated vertices are allowed; a requirement of a vertex-simple directed path is a different problem and can encode Hamiltonian path. Scanning all edges and clearing a vertex layer costs $O(k(|V|+|E|))$ for $k$ labels.

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.

Read ${\mathrm{prop}}_3(u,v)$ as the existence of a directed successor path from $u$ to $v$. Then the property says every reachable ordered pair of even-valued nodes admits a connecting route through an odd-valued node. More exactly, for all even-valued $u,v$ with $u$ reaching $v$, there is an odd-valued $w$ such that $u$ reaches $w$ and $w$ reaches $v$.

The two reachability witnesses concatenate to a directed walk through $w$. In an acyclic graph this yields an intervening node on a path. In a graph with directed cycles, the concatenation may revisit vertices. The existential witness does not say that every connecting path contains an odd-valued node, or even that an even-to-even edge is forbidden. For example edges $u\to v$, $u\to w$, $w\to v$, with even endpoints and odd $w$, satisfy the property for this pair despite the direct even-to-even edge.

There are two source-notation qualifications. The displayed outer universal quantifier binds both symbols appearing as formal arguments to prop, so the whole formula is a global property of $T$, rather than a genuinely free two-node predicate. Also the indexed ellipsis defining prop3 does not formalize path length zero. With positive-length reachability, even nodes on a cycle impose additional requirements; with reflexive reachability, choosing $u=v$ also imposes a requirement, and an isolated even-valued node would fail. The usual intended reading here is positive-length successor reachability. No uniqueness, acyclicity or specific path-length convention is proved by the displayed formula alone.

Every finite distance label is the weight of a discovered directed walk, so it can never underestimate a finite shortest-path distance. After $k$ complete passes, each label is at most the cost of every source-to-vertex path using at most $k$ edges. To prove that assertion, consider such a path's last edge $u\to v$: after the previous pass, $u$ already has a label no greater than the prefix cost, and the current pass relaxes that last edge. In-place improvements can only make the label smaller, preserving the assertion.

When no negative-weight cycle is reachable, any repeated-vertex portion of an optimal walk can be removed without increasing its cost. Some shortest path therefore has at most $|V|-1$ edges. The two bounds meet after that many passes, proving correctness. If a complete pass makes no change, all edge relaxation inequalities already hold and further passes cannot improve anything. A further strict relaxation after $|V|-1$ passes implies a reachable negative cycle by the same simple-path bound.

The printed formula for the edge label has mismatched variable names. The type-correct reading is $x_i=\sigma (v_{i-1},v_i)$. Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.

Let $R_t$ be the set of vertices reachable from the specified start after reading exactly the first $t$ labels. Initialize $R_0=\{v_0\}$ and updateAfter $k$ stages, answer yes exactly when $R_k\ne \varnothing$. A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on $t$. Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is $O(k(|V|+|E|))$ with $O(|V|)$ rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at $v_0$.

If “path” is instead required to mean vertex-simple, augment the state to $(S,v)$, where $S$ is the set of visited vertices. Start with $R_0(\{v_0\},v_0)$ and extend a matching edge to $w$ only when $w\notin S$, replacing $S$ by $S\cup \{w\}$. This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when $k\ge |V|$. A straightforward bound is $O(k{2}^{|V|}(|V|+|E|))$ running time with $O(2^{|V|}|V|)$ rolling-table storage. The exponential distinction is substantive: all labels equal and $k=|V|-1$ include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.

Initialize $d[s]=0$ and $d[v]=\infty$ elsewhere. Perform $|V|-1$ full passes over the directed edges, applying edge relaxation $d[v]\leftarrow \min \{d[v],d[u]+w(u,v)\}$ whenever $d[u]$ is finite. For an undirected graph, process each edge in both directions. Stop early if a pass makes no change.

Each finite label records the cost of a discovered directed walk, so it never understates the true infimum. After $t$ passes, relaxation has propagated along every route of at most $t$ edges, so the label is no greater than the cost of any such route. If no reachable negative-cost closed walk exists, an optimal route can be chosen without repeated vertices and has at most $|V|-1$ edges. These inequalities prove that the final labels are the desired shortest path lengths.

An additional pass checks for an improving edge from a reachable vertex. If one exists, report a reachable negative-cost cycle: finite shortest distances cannot be assigned to vertices reachable from that cycle. Mark those vertices by forward reachability if individual $-\infty$ answers are wanted. In particular, a reachable negative undirected edge becomes a negative two-arc closed walk under the bidirected interpretation; generic signed weights do not guarantee finite answers.

Each pass costs $O(|E|)$, giving $O(|V||E|)$ for the usual Bellman-Ford algorithm bound. Including initialization gives $O(|V|+|V||E|)$, which also handles an edgeless graph honestly; these coincide in order when $|E|\ge 1$.

For the single-source problem, let $D_k(v)$ be the minimum cost of a directed walk from $s$ to $v$ using at most $k$ edges. Set $D_0(s)=0$ and $D_0(v)=\infty$ for $v\ne s$, use $\infty +c=\infty$ for finite $c$, and let a minimum over an empty set be $\infty$. ThenEvery entry on the right comes from the previous round, requiring separate old and new arrays. The proof is the last-edge decomposition: a permitted directed walk either already uses at most $k-1$ edges, or ends with some $u\to v$ after a prefix using at most $k-1$. Conversely, each candidate describes a permitted directed walk. This dynamic programming viewpoint gives an exact meaning to every intermediate label, even when negative-cost directed cycles exist. Apply the formula to the source too: its initial zero is not a permanent constraint.

If no negative-cost directed cycle is reachable from $s$, removing repeated-vertex portions of a directed walk cannot increase its cost. Whenever a destination is reachable, some shortest directed path therefore uses at most $|V|-1$ edges, and $D_{|V|-1}(v)=\delta (s,v)$. Unreachable vertices keep distance $\infty$. For in-place passes, every finite label still comes from a discovered directed walk; moreover, pass $k$ has offered every prefix of length $k$ of a shortest directed path, regardless of scan order. Its labels can improve faster than the synchronous labels, while the same $|V|-1$ upper bound on passes remains valid. This is why repeated local corrections eventually settle a global shortest path problem.

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$, soIt 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.^[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 from $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.

A walk records a journey through a graph as a finite alternating sequencewhere each edge $e_i$ joins the consecutive vertices $v_{i-1}$ and $v_i$. Both vertices and edges may repeat. Its length is $m$, counting edge traversals with repetitions, rather than counting different edges or measuring the drawing. Here a graph path means a walk with no repeated vertices; a trail instead forbids repeated edges. These conventions distinguish a journey's record from the subgraph consisting of the connections it used.^[ref]

Unless stated otherwise, the examples below use a finite simple graph that is an undirected graph, so an edge may be traversed in either direction. In a multigraph, retain each edge's individual identity as well as its endpoint vertices: two parallel edges are different choices for the same step. If self-loops are allowed, traversing one leaves the current vertex unchanged but adds one to the length. In a directed graph, each step must follow its directed edge from its initial to its terminal vertex, giving a directed walk; reversing a journey need not be possible.^[ref]

We allow the zero-length walk $(v)$ at every vertex $v$. It uses no edges, so it is also a trail and a graph path, and its coinciding endpoints make it a closed walk. This means staying put is a legitimate journey; a graph with no vertices has no such walk. Positive-length restrictions will be stated explicitly.^[ref]

Use the same constructed graph throughout these three sections:Here $AB$ denotes the unordered pair $\{A,B\}$, and $CA=AC$. Two triangles in a graph, $ABC$ and $ADE$, share $A$, with one extra edge $AF$. These are schematic connections, not measured roads; the highlighted connections in the diagram show which edges are used, while the numbered sequence records their order.

The length-six walk $B,C,A,B,C,A,F$ uses $BC$ and $CA$ twice, so it is not a trail. The length-six trail $B,C,A,D,E,A,F$ returns to $A$ but uses six different edges, so it is not a graph path. The length-three graph path $B,C,A,F$ repeats neither vertices nor edges. Thusfor this particular graph. The restrictions answer different routing questions: revisiting a junction is harmless for many journeys, whereas reusing a serviced road segment can matter for an inspection route. Travel costs require a weighted graph; a walk's cost adds the weight of each traversal, even when an edge is used again.

Every finite walk from $s$ to $t$ contains a graph path from $s$ to $t$ after deleting detours. For a proof outline, if $v_i=v_j$ with $i<j$, delete the intervening closed walk. The retained steps still meet at the same vertex, and the length strictly decreases. Repeating terminates with no repeated vertices, or with the zero-length graph path when $s=t$. This explains why reachability can be formulated using either walks or graph paths. With nonnegative edge weights, deletion also cannot increase cost, connecting the argument to the shortest path problem; with negative weights that cost conclusion fails.^[ref]