Shortest path problem (${\min }_{p:s⇝t}{\sum }_{e\in p}{w}_e$)

The shortest path problem asks for a graph path from a source vertex $s$ to a destination vertex $t$ minimizing its total edge weight. Here $w_e$ is the cost of traversing edge $e$, and costs add along the graph path. If no route exists, its shortest-path distance is $\infty$. With nonnegative edge weights, deleting cycles in a graph from a walk never increases its cost, so repetitions cannot improve the optimum.

Consider the undirected graph with vertex set $V=\{A,B,C,D\}$ and the six edge weightsEach edge can be traversed in either direction at the same cost. The direct graph path $A,D$ costs $10$; $A,B,D$ costs $4+1=5$; $A,C,D$ costs $1+5=6$. The cheapest graph path is $A,C,B,D$, costing $1+2+1=4$. The remaining graph path $A,B,C,D$ costs $11$, exhausting the possibilities without repeated vertices.

Thus fewest edges and least total cost are different objectives. Breadth-first search minimizes the number of edges, which suffices when every edge has the same positive cost. Unequal nonnegative costs call for the Dijkstra algorithm. On a map, weights might be minutes rather than kilometres: a longer-looking route can arrive sooner. This is why a weighted graph separates the network's connections from what a particular journey costs.

The Floyd-Warshall algorithm computes all-pairs shortest graph path lengths in a finite weighted directed graph with no negative-length cycles in a graph. Initialize $d_{ii}=0$, use the arc cost for each existing directed edge, and use $+\infty$ when no arc exists. For $k=1,\dots ,n$, update every ordered pair $(i,j)$ by the displayed rule. The storage is $n^2$ lengths and the running time is $O(n^3)$.

For correctness, let $d_{ij}^{(k)}$ be the shortest simple graph path length whose intermediate vertices lie among the first $k$. A shortest allowed graph path either avoids $k$ or splits at its unique occurrence of $k$, giving the recurrence. Conversely, concatenate shortest paths through $k$ and remove any repeated-vertex sections; each such closed walk has nonnegative length, so removal cannot increase the length. This proves equality. The update can be performed in place because $d_{kk}=0$ and the $k$th row and column remain unchanged during stage $k$.

If negative-length cycles in a graph are present, a shortest walk may not exist and the recurrence need not compute shortest simple graph paths. Two optimal subpaths can concatenate into a repeated-vertex walk with a negative cycle; deleting that cycle increases its length. A negative diagonal entry in the algorithm's final array detects this obstruction to finite shortest-walk distances.

Adding the same constant $C$ to every edge weight adds $C$ times the number of edges to each path's cost. Routes with different edge counts need not retain their order. For example, edges $s\to t$, $s\to u$, $u\to t$ of weights $1,-2,2$ make the two-edge path optimal with cost zero. Adding three changes the direct cost to four and the two-edge cost to six. The graph is a Directed acyclic graph and all shifted weights are positive, yet the minimizing path changes.

Compute shortest-path distances from one fixed source to every vertex, together with predecessor information when shortest paths exist. Dijkstra's algorithm handles nonnegative weights; the Bellman-Ford algorithm admits negative weights and detects reachable negative cycles. A Directed acyclic graph instead permits one pass in topological order.

Initialize source distance to zero and other distances to infinity, then process vertices in topological order, relaxing their outgoing edges once. Every predecessor on a path to a vertex appears earlier, so induction through that ordering proves that its distance is final when processed. Negative weights are allowed because there are no directed cycles. With adjacency lists, topological sorting and all edge relaxations take $O(|V|+|E|)$ time; predecessor pointers reconstruct paths.

The infimum of total edge weights over allowed walks from a source to a target. The value is $+\infty$ when no route exists. A negative cycle reachable from the source and able to reach the target makes it $-\infty$. In a finite graph without such a cycle, a finite distance is attained by a graph path, after removing non-improving repetitions.

If every nontrivial closed subwalk has strictly positive weight, removing any repeated-vertex segment strictly decreases a walk's weight. Hence a minimum-weight walk must be a graph path, and it is a shortest path. Strictly positive edge weights are sufficient in an undirected graph. For a trail, positivity of every simple cycle is already sufficient: its first repeated-vertex segment is a cycle because no edge is repeated.

Under the usual unrestricted walk convention, positivity of simple cycles alone is insufficient. A graph consisting of one zero-weight edge $xy$ has no cycles, but the walk $x,y,x,y$ is a minimum-weight walk and is not a path. A zero-weight backtrack cannot be removed with a strict improvement. For nonnegative edge weights, one may erase such backtracks without increasing weight and obtain a shortest path, but cannot conclude that every minimum walk was already a path.

In a positive-weight directed graph, run the Dijkstra algorithm from each source $s$ and minimize $d_s(u)+w(u,s)$ over closing edges. In an undirected graph, minimize $d_s(u)+w(u,v)+d_s(v)$ only over edges absent from the current shortest-path tree. A tree edge would otherwise give a spurious traversal out and back. A non-tree candidate contains a genuine cycle no longer than its score, even when the two tree routes share a prefix.

For the undirected optimum, choose a shortest cycle and a source on it. If an incident cycle edge is absent from the tree, its candidate is bounded by the cycle length. Otherwise its two neighbours lie in distinct tree branches, and some edge on the remaining cycle segment crosses branches. That edge is non-tree; shortest distances to its endpoints are bounded by the two complementary cycle segments, again giving a candidate no greater than the optimum. Thus the minimum candidate equals the shortest-cycle length. Repeated Dijkstra algorithm runs take $O((|V{|}^2+|V||E|)\log (|V|+1))$ running time with a binary heap.

Let $D_r(v)$ be the minimum weight of a route from a fixed source to $v$ using at most $r$ edges; repeated vertices are permitted. Initialise $D_0$ to zero at the source and infinity elsewhere. Every feasible route either already uses at most $r-1$ edges or appends one edge to such a route, proving the displayed dynamic programming recurrence. Reading exclusively from the previous row enforces the edge budget. Negative cycles cause no unbounded objective because the budget is finite. Each round scans all edges, costing $O(m)$ when only edge-incident vertices and the specified endpoints are processed. With nonnegative weights, cycle removal gives an equally good or better simple path within the budget.

In a finite graph with positive integral edge weights, replacing $w(e)$ by $|V|w(e)+1$ makes every transformed shortest path minimise original weight first and edge count second. Positive weights imply that an optimal route is simple, with at most $|V|-1$ edges. Original integral path weights that differ have a gap of at least one; multiplication by $|V|$ outweighs every possible difference in simple-path edge counts. Among equal-weight paths, only the added edge count differs. Thus a single ordinary shortest path computation solves lexicographic weight-and-hop minimisation.

For a graph on $n$ vertices with all edge weights in $[1,1+1/n]$, every minimum-weight shortest path has the smallest possible number of edges. Indeed, positivity permits a simple optimum, and a simple $r$-edge path weighs at most $r+r/n<r+1$ for $r\le n-1$, while any path with more edges weighs at least $r+1$. A breadth-first search followed by weighted dynamic programming along increasing-hop edges therefore solves the single-source problem in $O(|V|+|E|)$ time. Choosing an arbitrary breadth-first tree alone is insufficient: equal-hop routes may still have different weights.

Suppose two pieces occupy a common connected component of a graph in an unweighted undirected graph. For integers $a>b\ge 0$, in each round an evader moves at most $b$ edges, then a pursuer moves up to $a$ edges along a shortest path to the new evader position, stopping upon capture. Let $d_t$ be their finite graph distance at a surviving round boundary.

The triangle inequality bounds the separation after the evader moves by $d_t+b$. If that separation is at most $a$, the pursuer captures it. Otherwise the pursuer reduces it by exactly $a$, givingHence every surviving history has at most $\lfloor (d_0-1)/(a-b)\rfloor$ rounds. With a finite branching factor, the surviving search tree is finite and depth-first tree search becomes a complete search algorithm. This does not make its first goal optimal for arbitrary rewards. Initial reachability is essential: an infinite graph distance supplies no decreasing finite bound.

Unlike the sum in the usual shortest path problem, the bottleneck cost of a nonempty graph path is its largest edge weight. The optimum is the smallest threshold at which the endpoints become connected by edges of weight at most that threshold. Sorting edges and increasing the threshold, with a disjoint-set data structure maintaining components, finds this value. The minimax path property of a minimum spanning tree provides a single tree representing such optimal routes for every pair of vertices.

A shortest-path tree rooted at a source vertex is a spanning tree whose unique tree route from the source to every vertex solves the shortest path problem in the original weighted graph. Dijkstra's algorithm constructs one for a finite connected graph with nonnegative edge lengths, recording a predecessor whenever a distance improves. It need not be a minimum spanning tree: one minimizes each source-route length, the other the total weight of the tree's edges.

In a finite connected graph with strictly positive edge weights, choose any shortest path from a root $v$ to every other vertex $u$, and let $p(u)$ be its penultimate vertex. Every prefix is shortest: a better prefix followed by the final edge would give a cheaper walk, whose positive-weight cycles can be erased to give a cheaper path. Thus the displayed distance identity holds.

Following predecessors strictly decreases the shortest-path distance, so no predecessor cycle is possible. Since every nonroot vertex has a predecessor, every chain reaches the root. Opposite predecessor choices cannot select the same undirected edge, again by strict distance decrease. The selected graph is connected and has exactly one edge per nonroot vertex, so is a spanning tree. Along its root paths the distance differences telescope, proving that it is a shortest-path tree even if the original shortest paths were chosen independently.

In a triangle with root $v$, assign $w(va)=w(vb)=2$ and $w(ab)=-1$. Among graph paths, the unique shortest path from $v$ to $a$ is $v,b,a$, and that from $v$ to $b$ is $v,a,b$, both of weight one. A shortest-path tree would have to contain all three edges, impossible for a tree. The example uses shortest simple paths; arbitrary walks can have unboundedly negative weight by repeatedly traversing the negative edge.

A graph path of minimum total edge weight between its endpoints, among the permitted paths. In an unweighted graph, its weight is the number of edges. A shortest path need not be unique.

An algorithm that makes each vertex's distance permanent once it is selected. With nonnegative directed edge lengths, the Dijkstra algorithm selects the unfinalized vertex with least tentative distance; a shorter route through another unfinalized vertex is impossible because its remaining route has at least that next tentative distance. For an all-to-one problem, incoming directed edges to the selected vertex are relaxed. Negative lengths can invalidate this finalization argument.

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.

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.

The Bellman-Ford algorithm solves the single-source shortest path problem in a finite directed graph with finite real edge weights, allowing negative weights. It repeatedly applies edge relaxation, so an improved tentative distance can improve its neighbours on a later visit. This makes it a label-correcting shortest-path algorithm.^[ref] If no negative-cost directed cycle is reachable from the source, at most $|V|-1$ complete passes suffice for all distances; a further check detects a reachable negative-cost directed cycle.^[ref]

There are two orientations to keep distinct. The usual single-source problem asks for distances from $s$, extending routes along outgoing directed edges. The Bellman inequalities above instead concern distances to a sink $r$, prepending incoming directed edges to known routes. The All-to-one Bellman-Ford recurrence below preserves that convention. Reversing every directed edge, with its weight unchanged, converts one problem into the other.

Here is an original single-source example with source $S$, vertex set $V=\{S,A,B,C,T\}$, and precisely these directed edges:The negative edge $A\to B$ is harmless: this directed graph has no directed cycle. Its best route to $T$ is $S\to A\to B\to C\to T$, of cost $4-2+3+2=7$. The other routes to $T$ cost $12$ through $S,A,T$ and $10$ through $S,B,C,T$.

Initialize $d(S)=0$ and the other tentative distances to $\infty$. In each pass apply single-source edge relaxation, $d(v)\leftarrow \min \{d(v),d(u)+w_{uv}\}$, scanning in the order $A\to T$, $C\to T$, $B\to C$, $A\to B$, $S\to B$, $S\to A$. Skip a candidate with $d(u)=\infty$. The figure records labels after each complete pass and uses current labels immediately: it is an in-place trace. In pass 2, $B\to C$ still uses $d(B)=5$, giving $8$; only later does $A\to B$ lower $B$ to $2$. Pass 3 carries that improvement to $C$, and pass 4 carries it to $T$. The final labels in order $(S,A,B,C,T)$ are $(0,4,2,5,7)$; the final shortest-path predecessors are $S,A,B,C$ for $A,B,C,T$ respectively.

The scan order explains the delay. Scanning instead as $S\to A$, $S\to B$, $A\to B$, $B\to C$, $C\to T$, $A\to T$ gives those same final labels in just one in-place pass. The Synchronous Bellman-Ford recurrence has a precise bound on the number of edges used by a recorded route; an in-place pass can propagate along several edges and need not have that interpretation. Both implementations have the $|V|-1$ pass guarantee under the stated no-reachable-negative-cycle hypothesis.

With a stored list of edges, complete-pass Bellman-Ford algorithm has time complexity $O(|V||E|+|V|)$ and uses $O(|V|)$ extra space for labels and shortest-path predecessors, using Big O notation and constant-cost arithmetic. The extra $|V|$ accounts for initialization even when $E$ is empty. A pass with no strict decrease permits early termination. A queue variant instead revisits outgoing edges of vertices whose labels improved; the authored implementation provides this alternative and has $O(|V||E|)$ worst-case running time on its usual nontrivial instances.^[ref] For nonnegative weights, the Dijkstra algorithm and its existing distance-frontier figure explain how permanent labels can avoid these repeated passes; the existing edge relaxation figure illustrates one update at a time.

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 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.

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.

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]

Among paths of minimum total weight, choose the fewest edges. Store a lexicographic order pair $(d,h)$ and extend it across weight $w$ as $(d+w,h+1)$. For positive edge weights, every extension strictly increases its first component, so Dijkstra's algorithm settles these pairs correctly when its priority queue and relaxation both compare the full pair. Equal total weight then selects the smaller hop count; arbitrary vertex-name tie-breaking does not express this objective.

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.

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.

A shortest-path predecessor $\pi (v)$ records the previous vertex on a chosen route from source $s$ to $v$. When edge relaxation strictly improves $d(v)$ through $u\to v$, set $\pi (v)=u$. For a multigraph, store the actual directed edge, since two edges with the same endpoints can have different weights. Initialize all vertices, including the source, without a shortest-path predecessor. The authored implementation reconstructs a route by following these incoming edges backwards, then reversing their order.^[ref]

At the end of the edge relaxation trace, $\pi (t)=a$, $\pi (a)=b$, and $\pi (b)=s$. Following them gives $t,a,b,s$, so the forward directed path is $s\to b\to a\to t$, of cost $2-1+2=3$. This makes the distance useful: a number tells us the best cost, whereas the shortest-path predecessors tell us which connections to take. In the Dijkstra algorithm, reconstruct a destination's shortest route after its label becomes permanent. In a label-correcting shortest-path algorithm, wait for convergence and the appropriate negative-cost directed cycle check. During correction, a predecessor's label may have changed since its child's last update: immediately after $b\to a$ in the trace, the current chain to $t$ costs $3$ although $d(t)$ still records the earlier discovered route of cost $8$.

Strict improvement is a useful guard against directed cycles in the recorded pointers. Consider $s\to a$ and $s\to b$ of cost zero, followed by $a\to b$ and $b\to a$, also of cost zero. After the first two edge relaxations, both labels are zero and both shortest-path predecessors are $s$. If equality also allows pointer replacement, the last two operations can set $\pi (b)=a$ and $\pi (a)=b$: following pointers loops forever despite correct distance labels. Keeping the old pointer on ties prevents this example; choosing among equal-cost routes requires a separate rule that preserves a route to the source. Strict improvement alone does not protect against reachable negative-cost directed cycles, which can force endless decreases. Equality on recorded edges plus the Bellman inequalities certifies route costs only when the pointer chains actually terminate at the source.

For all-to-one distances to $r$, record a next vertex $j$ whenever relaxing $i\to j$ improves $d_i$. Follow these successors forward in the original directed graph to reach $r$. They are shortest-path predecessors when viewed in the reversed directed graph; keeping the direction convention explicit prevents returning a route whose arrows point the wrong way.