Find a minimum-cost route under explicit assumptions
Relax tentative distances and see why nonnegative weights justify Dijkstra's settled set.
By the end: separate shortest paths, fewest-edge routes, and negative-cycle failures.
Tentative distances are upper bounds
Set the source distance to zero and all others to infinity, meaning no route is known yet. For an edge from u to v, compare the current distance of v with the distance of u plus the edge weight. If the candidate is smaller, replace the distance and record that edge as the predecessor. This update is called relaxation.
Every finite tentative distance describes a known route, so it is an upper bound on the true minimum cost. It is not necessarily final. In the example, A-C initially costs 4, but A-B-C costs 1 plus 1, so C improves to 2. Keeping predecessor edges allows reconstruction of the route rather than just its cost.
A tentative label needs a route that supports it
Consider a separate directed delivery map with vertices A, B, C, D, E. Its complete edge list is A to B costing 6, A to C costing 2, C to B costing 1, B to D costing 2, C to D costing 7, D to E costing 1, and C to E costing 8. Costs are fixed additive units, not distances inferred from the drawing. The question is the cheapest permitted route from A. Reaching B directly costs 6, but reaching C first and then B costs only 3. The first route found need not be best.
A label of 6 at B therefore means something narrower than 'the answer is 6'. It means we can exhibit a route costing 6. This gives an upper bound on the minimum, because the cheapest route cannot cost more than an available route. Improving the label to 3 tightens that bound. By contrast, a claim that every route costs at least 3 is a lower bound. A correct optimality argument eventually needs both directions. Showing a cheap route alone leaves open the possibility of another, cheaper route that has not yet been inspected.
A route costing 6 is an upper bound for E
Thick edges give A-C-B-D-E, with total 2 + 1 + 2 + 1 = 6. Thin edges remain available alternatives. Arrows give permissions; positions and line lengths are schematic, not a cost scale.
Start with A labeled 0 and every other vertex labeled infinity. After examining A's outgoing edges, B has 6 and C has 2. D and E still have infinity. Examining C next offers B the candidate 2 plus 1, so B changes to 3. It also gives D the candidate 9 and E the candidate 10. Each update has a concrete supporting route beginning at A. Infinity at this stage records a lack of discovered evidence, not proof that the destination is impossible to reach. Later finite labels can replace it.
Now examine B using its improved label 3. The B-to-D edge costs 2, making a candidate of 5. This replaces D's 9 and changes its predecessor from C to B. Examining D then lowers E from 10 to 6. The complete route to E is A, C, B, D, E, with successive cumulative costs 0, 2, 3, 5, 6. Reading predecessors backward gives E, D, B, C, A; reversing that list recovers the travel order. A predecessor identifies the last edge of a supporting route, not the entire route by itself.
Why can the cheapest route to E use the cheapest route to D as its beginning? Suppose its beginning reached D at cost 7 even though a permitted beginning of cost 5 existed. Replacing that beginning would reduce the full cost by 2, because the remaining D-to-E cost stays 1. That contradicts the original route being cheapest. This replacement argument assumes that the continuation depends only on the current vertex. If arriving at D on a particular vehicle changes which departures are allowed, the vertex must record that information too before this reasoning applies.
Every smaller label has a supporting route
After examining
Labels A, B, C, D, E
New or improved routes
Initial
0, ∞, ∞, ∞, ∞
Only A is known
A
0, 6, 2, ∞, ∞
A-B; A-C
C
0, 3, 2, 9, 10
A-C-B; A-C-D; A-C-E
B
0, 3, 2, 5, 10
A-C-B-D replaces A-C-D
D
0, 3, 2, 5, 6
A-C-B-D-E replaces A-C-E
E
0, 3, 2, 5, 6
No outgoing edges
Each row follows examination of the named vertex. B's improvement changes the later opportunity at D, which then changes E. Infinity here means no route has yet been discovered, not a final impossibility claim.
The same issue appears when weights represent prices. An edge price can be added independently only if it does not depend on which earlier edges were used. A discount for buying a return ticket breaks that simple description. Likewise, a journey with a limited fuel supply needs more information than location alone if future travel depends on fuel remaining. None of these complications makes addition wrong. They make the chosen vertices incomplete for the question. In this lesson, fixed edge costs and location-based permissions are explicit assumptions, so the labels and predecessor chains have a definite meaning.
Why Dijkstra may settle the smallest label
Dijkstra's algorithm repeatedly settles the unsettled vertex with the smallest finite tentative distance, then relaxes its outgoing edges. When all edge weights are nonnegative, a route through a more expensive unsettled frontier cannot later become cheaper on its way to that vertex. This is why settling that label is safe.
Ties may produce different predecessor trees with the same optimal distances. A zero-weight edge is valid; it is not the same as no edge. An unreachable vertex retains infinity. The model uses exact small integer weights, so there is no rounding decision hidden in equality or tie-breaking.
The first unsettled vertex explains why the minimum is safe
Settling a vertex means accepting its current label as final. The important comparison is between whole routes, not merely between the outgoing edges of the current vertex. Return to the five-vertex map above. After settling A and examining its edges, C has label 2 and B has label 6. C is the least expensive unsettled vertex with a finite label. Any alternative route to C must leave the settled region somewhere. At the first vertex outside that region, the algorithm has already considered the crossing edge from its settled predecessor. This first crossing constrains every competing route.
Suppose, for contradiction, that a route to C cost less than 2. Take the first unsettled vertex along that route and call it X. The beginning through X cannot cost more than the full route, because every later edge has nonnegative cost. The edge entering X came from a settled vertex. When that predecessor was examined, relaxation supplied X with a label no larger than this beginning's cost. X would therefore have a finite label below 2. But C was chosen as the smallest finite unsettled label. These two statements cannot both hold.
Every route leaving settled A crosses to an unsettled vertex
Only A is settled, shown filled. The dashed partition separates {A} from {B,C,D,E}; its crossing records offer B cost 6 and C cost 2. Any hypothetical cheaper route to C must have a first unsettled vertex with a smaller label, contradicting the selection of C. The boundary is schematic.
The reasoning repeats after each choice. Initially A's cost 0 is correct because nonnegative edges cannot give a cheaper return walk. Assuming earlier settled labels are correct, the first-crossing argument proves the next minimum correct. This is an induction: establish a starting case, then show that a correct completed part permits one more correct step. In the example, the settled costs become A at 0, C at 2, B at 3, D at 5, and E at 6. The sorted costs are a consequence of nonnegative weights, not a requirement that vertex names follow route order.
Zero-cost edges preserve the proof because a remaining route may cost the same as its beginning without costing less. Consider vertices A, B, C, D with exactly A to B costing 0, A to C costing 0, B to C costing 0, C to B costing 0, and C to D costing 2. After A, B and C both have label 0. Alphabetical tie-breaking settles B first. Its candidate for C is also 0, so no update occurs. The equal-cost zero cycle does not force the chosen predecessor chain to include repeated vertices.
Strict improvement matters here. Replacing a predecessor whenever an equal candidate appears could needlessly redirect B through C and C through B. The displayed model changes a predecessor only when the candidate is smaller. In this zero-cost example it keeps A as predecessor of both B and C, then gives D predecessor C. Several optimal routes remain possible, but one consistent selection is enough to report distances. Alphabetical choices make the output reproducible. They do not assign a mathematical preference to B over C, and they do not establish that the optimal route is unique.
A zero-cost cycle need not enter the predecessor tree
After examining
Labels A, B, C, D
Predecessors of B, C, D
A
0, 0, 0, ∞
A, A, none
B
0, 0, 0, ∞
A, A, none; equal candidate to C
C
0, 0, 0, 2
A, A, C; equal candidate to B
D
0, 0, 0, 2
A, A, C
The complete directed records are A→B 0, A→C 0, B→C 0, C→B 0, C→D 2. Alphabetical settling chooses B before C. Equality never replaces a predecessor, so B and C retain A rather than pointing to one another.
The stopping condition also follows from the first-crossing argument. If no unsettled vertex has a finite label, no route can leave the settled region and reach another vertex. Otherwise the first outside vertex on that route would have acquired a finite candidate. Remaining infinities now certify unreachability, unlike intermediate infinities. For a single target, a nonnegative Dijkstra calculation may stop when that target is settled, but not merely when it first receives a label. The existing comparison calculates all reachable destinations; its rows let you distinguish the moment a route appears from the moment its minimum becomes justified.
Inspect the graph and its result
Fewest edges versus least total cost
BFS discovery tree
Edge counts A–D: 0, 1, 1, 2.
Dijkstra predecessor tree
Costs A–D: 0, 1, 2, 3.
Relax an edge
Here d is the array of tentative distances; the u subscript selects vertex u. The edge weight w uses the same cost units. Replace v's tentative value only if the candidate is smaller. Settling requires the nonnegative-weight argument.
Settled so far
Tentative costs A–D
A
0, 1, 4, ∞
A, B
0, 1, 2, 8
A, B, C
0, 1, 2, 3
A, B, C, D
0, 1, 2, 3
Each row follows relaxation from the newly settled vertex.
Edge
Weight
A → B
1
A → C
4
B → C
1
B → D
7
C → D
1
Exact endpoint records. Crossing lines do not add a vertex.
Presets replace the whole graph. All supported weights are nonnegative integer cost units. Blue edges identify one predecessor tree, not every optimal route. Infinity means unreachable in the final result.
Route A to D
Edges
Cost units
A-B-D
2
8
A-C-D
2
5
A-B-C-D
3
3
The fewest-edge route is not the cheapest route. Thick blue edges are the named selection; all original connections remain visible.
Read the three route comparisons as different claims
In the displayed 'Detour is cheaper' preset, the vertices are A through D and the directed records are A to B with weight 1, A to C with weight 4, B to C with weight 1, B to D with weight 7, and C to D with weight 1. Before reading the final trees, calculate the labels after examining A. They must be 0, 1, 4, infinity in alphabetical vertex order. This prediction uses only A's outgoing edges. It does not use the visual length of either line, which carries no cost scale.
Next B settles at 1. Its edge to C replaces 4 by 2, while its edge to D supplies 8. C then settles at 2 and replaces D's label by 3. D is the final settled vertex. Compare these intermediate rows with the completed predecessor tree. The selected A-to-D route has three edges, A to B to C to D. BFS instead discovers C directly from A and discovers D while processing B, giving the two-edge route A to B to D. That BFS route costs 8, even though its edge count is smaller.
The displayed detour preset lowers D twice
Newly settled
Labels A, B, C, D
Changed predecessor
A
0, 1, 4, ∞
B from A; C from A
B
0, 1, 2, 8
C from B; D from B
C
0, 1, 2, 3
D from C
D
0, 1, 2, 3
None
These are the model's post-relaxation rows for A→B 1, A→C 4, B→C 1, B→D 7, C→D 1. C's label improves before it is settled. D's first finite label is 8, while its final minimum is 3.
The BFS result is not an unsuccessful version of Dijkstra. It answers a different question correctly. Both A-B-D and A-C-D use two edges, but their costs are 8 and 5. Alphabetical neighbor processing gives B the first opportunity to discover D, so the chosen BFS route is the costlier of those two. Dijkstra finds cost 3 using three edges. This separates two kinds of tie: equal edge counts do not imply equal weighted costs, while equal weighted costs do not imply equal predecessor choices. The pair of trees should be read with its reported quantities.
Select 'Equal-cost ties'. The only records are A to B, A to C, B to D, and C to D, all costing 1. After A, B and C each have label 1. B settles first and offers D cost 2. C then offers the same cost, so strict improvement leaves B as D's predecessor. The displayed tree chooses A-B-D, but A-C-D is equally cheap. Counting both possibilities explains why a selected-edge picture is not a picture of every optimal route. The distance 2 is determined even when the chosen final edge is not uniquely necessary.
Finally select 'Zero cost and unreachable D'. There are exactly four vertices and two edges, A to B costing 0 and B to C costing 2. D remains present as an isolated vertex. The complete labels are 0, 0, 2, infinity, and the settling rows end after C. There is no fourth row settling D. B's zero label is supported by a real edge, unlike D's missing connection. Removing A-to-B would change reachability; replacing its weight by zero does not. This is why a weighted edge record needs existence information separate from its numerical weight.
The tied preset selects one of two cost-2 routes
All four directed records cost 1. Thick edges form the selected predecessor tree A→B, A→C, B→D. C→D is equally good for reaching D, but its equal candidate does not replace B. No geometry encodes weight.
A small calculation can check the final distances without copying the algorithm. In the first preset the arrows only advance through the order A, B, C, D. List every A-to-D path: A-B-D costs 8, A-C-D costs 5, and A-B-C-D costs 3. There are no other choices because D has no outgoing edges and the listed records are complete. In the tied preset both paths cost 2. In the final preset no edge enters D. Such enumeration is practical for these tiny graphs, but the visualizer does not imply that listing every route is a scalable shortest-path method.
Recognize where the proof fails
A negative edge can make a later detour cheaper than an already settled label. This visualizer refuses negative weights for Dijkstra. Bellman-Ford is one alternative for graphs with negative weights, with explicit negative-cycle handling. A DAG also permits relaxation in topological order even with negative edges.
If a negative cycle is reachable from the source and can reach the destination, unrestricted walk costs have no finite minimum: loop again to lower the cost. If the cycle cannot lead to the destination, that specific route query need not be unbounded. Real time-dependent travel, congestion, or nonadditive preferences require a different model, not a renamed weight.
Check the destination before blaming a negative cycle
A useful independent check uses final labels as proposed lower bounds. In the five-vertex delivery map, propose A through E costs 0, 3, 2, 5, 6. For every directed edge, check that the destination label is no greater than the source label plus the edge cost. For example, C to D gives 5 no greater than 2 plus 7, while B to D gives equality, 5 equals 3 plus 2. Summing these inequalities along any A-to-E route shows that route costs at least 6. The exhibited route costing 6 then proves optimality.
Negative weights do not prevent that kind of final certificate, but they break Dijkstra's early-settling argument. There is another route procedure available on a DAG, whose prerequisite order you met in the dependency lesson. Process vertices in a topological order and relax their outgoing edges. Every predecessor of a vertex has already been processed, so its incoming opportunities have all arrived before its turn. No later vertex can lead back to it without violating the order. This works with negative edges because finality comes from direction and acyclicity rather than from labels increasing along a route.
Check every edge against the proposed final labels
Directed edge and cost
Destination label
Source label + cost
Check
A→B: 6
3
0 + 6 = 6
3 ≤ 6
A→C: 2
2
0 + 2 = 2
2 = 2
C→B: 1
3
2 + 1 = 3
3 = 3
B→D: 2
5
3 + 2 = 5
5 = 5
C→D: 7
5
2 + 7 = 9
5 ≤ 9
D→E: 1
6
5 + 1 = 6
6 = 6
C→E: 8
6
2 + 8 = 10
6 ≤ 10
Labels A=0, B=3, C=2, D=5, E=6 satisfy every edge inequality. Adding inequalities along a route gives a cost at least the destination label because intermediate labels cancel. The selected route attains 6, proving both bounds for E.
Now consider a separate directed graph with vertices A, B, C, D, E, F. Its only edges are A to B costing 2, B to C costing negative 3, C to B costing 1, A to D costing 5, and D to E costing 1. F is isolated. The B-C-B cycle costs negative 2 per repetition, and A can reach it. Nevertheless the cheapest A-to-D route still costs 5. Neither B nor C can reach D. Entering that cycle prevents reaching the requested destination, so its decreasing walk costs do not compete with the route to D.
Add just C to E with cost 2 in that paper graph. The query to E now changes: A-B-C-E costs 1, and inserting one B-C-B repetition reduces that to negative 1. Each further repetition subtracts 2. No finite cheapest unrestricted walk to E exists. The query to D still has answer 5 because E has no edge back to D. This gives two necessary reachability checks for a troublesome cycle. The source must reach it, and it must reach the particular destination. Negative examples here are reasoning cases, not selectable inputs for the nonnegative visualizer.
Our definition of a path forbids repeated vertices. Under that restriction, a finite graph has only finitely many candidate paths, so a reachable destination still has a minimum path cost even in the last example. Unboundedness concerns walks allowed to repeat the negative cycle. This distinction explains why a negative-cycle warning must name the route convention. It also explains why a zero-cost cycle is different. Repeating it gives more equally costly walks, not smaller costs without limit. Dijkstra can select a cycle-free representative when all weights are nonnegative, using strict improvements as in the model.
Adding an exit from the negative cycle affects E but not D
Solid arrows are the original records A→B 2, B→C −3, C→B 1, A→D 5, D→E 1. The dashed C→E 2 edge is the single addition. The B-C-B cycle costs −2. After the addition it can reach E but still cannot reach D. F is isolated. This is a paper counterexample, not a supported Dijkstra preset.
Even with nonnegative weights, changing their meaning can change the answer. Adding a fixed handling charge of 3 to every edge of the displayed detour graph makes A-B-D cost 14 and A-B-C-D cost 12, while A-C-D costs 11 and becomes cheapest. The extra charge penalizes more edges more often. Multiplying all costs by the same positive number instead preserves route comparisons. Before treating a calculated route as advice, ask whether the weights include the relevant charges and whether they stay fixed during travel. Exact arithmetic certifies the stated map, not observed delivery times or changing prices.
Exercises
Improve a tentative label
Known costs are distance to B = 3 and distance to C = 8. An edge B to C costs 2. What does relaxation change, and what does it not prove by itself?
Hint
Compare 8 with 3 plus 2.
Worked answer
Calculation
Cost
Existing route to C
8
Candidate via B
3 + 2 = 5
New tentative label
5
A successful update is not automatically a finality proof.
It replaces C's tentative distance with 5 and records B-to-C as its predecessor edge. It proves a route of cost 5 exists. Without the algorithm's settling conditions, another route may still improve C later.
A negative detour
Edges are A to B with cost 1, A to C with cost 2, and C to B with cost −3. Why is settling B at 1 unsafe?
Hint
Compute the route through C.
Worked answer
Route
Cost
A-B
1
A-C-B
−1
The drawing shows a counterexample, not a supported Dijkstra input. Thick blue edges are the named selection; all original connections remain visible.
A-C-B costs 2 minus 3, or −1. It is cheaper than 1, even though C initially has a larger tentative label. The nonnegative-edge assumption is violated. There is no cycle in this example; a negative edge alone can invalidate the Dijkstra proof.
Sources and further reading
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.