Single-Source Shortest Paths

By the end of this lesson you will be able to explain what a shortest path even means once edges can be negative, trace initializeSingleSource, relax, bellmanFord, dagShortestPaths and dijkstra line by line on a picture of the graph (with the priority queue, topological order and pass numbers all visible), implement every one of them in idiomatic Dart, know exactly when each is safe to use (and see, concretely, where Dijkstra breaks with a negative edge), watch each of six shortest-path properties (triangle inequality, upper bound, no path, convergence, path relaxation, predecessor subgraph) happen on real data, find the critical path of a project (a PERT chart) with dagShortestPaths, and turn a system of difference constraints into a shortest-paths problem.

Weighted graphs, paths, and what δ(u,v) means

A graph is dots joined by arrows. The dots are vertices, the arrows are edges, and in a directed graph every arrow points one way (you may drive from u to v but not back unless a second arrow says so). If each arrow also carries a number, the graph is weighted and the number is the edge's weight w(u,v). This lesson asks one question: starting from one fixed vertex, the source s, what is the cheapest way to reach every other vertex? (If you have not met graphs yet, the graph basics lesson (BFS, DFS, topological sort, SCC) introduces the picture and the adjacency list we reuse here.)

Picture a road map: cities are vertices, roads are directed edges, and each road has a toll (its weight w(u,v), which can even be negative — think of it as a road that PAYS you, like a rebate). A path from s to v is a sequence of roads you drive in order; its weight is the sum of the tolls along the way. The shortest-path weight δ(s,v) is the cheapest total toll of any route from s to v — and if v simply can't be reached from s no matter which roads you take, we define δ(s,v) = ∞.

Small example. Three cities: s→a costs 2, a→b costs −1 (a rebate), and s→b costs 4. Route s→b costs 4. Route s→a→b costs 2 + (−1) = 1. So δ(s,b) = 1, and the cheapest route is not the one with the fewest roads. "Shortest" therefore means "smallest total weight", never "fewest edges" (that is what plain BFS from the graph-basics lesson measures).

Formally: G = (V, E) is a weighted directed graph with a weight function w: E → ℝ. For a path p = ⟨v₀, v₁, …, v_k⟩ its weight is w(p) = Σᵢ₌₁ᵏ w(v_{i-1}, v_i). The shortest-path weight from u to v is δ(u,v) = min{w(p) : p is a path from u to v} if any path exists, and ∞ otherwise. A shortest path from u to v is any path p with w(p) = δ(u,v).

Dart: paths, their weights and δ as code. bruteDelta takes the minimum over every simple path (tiny graphs only), reproduces the small example above (the cheapest route has more edges), shows δ = ∞ for “no path”, and shows bellmanFord returning false where δ would be −∞. The helpers negEdgeGraph(), dagGraph() and roadGraph() build the three example graphs used below (vertices are the ints 0, 1, 2, … in the order the page names them).

If a path from s to v passes through a cycle (a path that ends where it began) whose total weight is negative, you can go around that cycle forever, subtracting a little more toll each lap — so δ(s,v) = −∞ (undefined as a finite number). This is exactly why Bellman-Ford's job includes detecting a negative-weight cycle reachable from the source, not just computing distances and hoping for the best. A cycle of weight exactly zero, or a positive-weight cycle, never helps a shortest path (repeating it only adds cost or does nothing) — so whenever δ is finite, some shortest path is always simple (no repeated vertices).

Two structural facts drive every algorithm in this lesson:

Fact A — optimal substructure: any subpath of a shortest path is itself a shortest path. If ⟨v₀,…,v_k⟩ is a shortest path from v₀ to v_k, then for any 0 ≤ i ≤ j ≤ k, the subpath ⟨v_i,…,v_j⟩ is a shortest path from v_i to v_j. (Proof: if a cheaper v_i→v_j route existed, splicing it in would produce a cheaper v₀→v_k path — contradiction.) This is WHY shortest paths can be built up by relaxing edges one at a time instead of searching whole paths.

Fact B — the triangle inequality: for every edge (u,v) ∈ E, δ(s,v) ≤ δ(s,u) + w(u,v). The cheapest way to reach v can never be worse than "reach u the cheapest way, then take this one edge" — otherwise that would BE a cheaper way to reach v. This single inequality is the exact condition every relax call is trying to enforce.

Dart: Fact A checked on every subpath of every shortest path of the route-cost graph. The subpath ⟨v_i, …, v_j⟩ is the 0-indexed slice p.sublist(i, j + 1).

Every algorithm below maintains, for each vertex v, two labels. d[v] is the shortest-path estimate: our current best guess of the cost to reach v, always ≥ δ(s,v) and shrinking toward it. π[v] (read "pi") is the predecessor: the vertex just before v on the best path found so far, or null ("nothing yet"). Once an algorithm finishes and d[v] = δ(s,v) for every v, the edges {(π[v], v) : π[v] ≠ null} form a shortest-paths tree — following π pointers backward from any v traces out an actual shortest path from s.

Why the source is fixed. "Single-source" means we compute δ(s,·) for one s and all targets at once, which is no harder than a single target in the worst case. The all-pairs shortest paths lesson drops the fixed source. Three words used all lesson: a priority queue is a container that always hands back the item with the smallest key (see heapsort and priority queues); a greedy algorithm commits to the locally best choice and never reconsiders it; a topological order of a directed acyclic graph lists the vertices so every edge points forward (see the graph-basics lesson).

Starting point: initializeSingleSource

Every shortest-path algorithm starts from the same blank slate: an honest, pessimistic guess for each vertex. The procedure gives every vertex the estimate ∞ and the predecessor null, then fixes the one thing we know for certain — the source costs 0 to reach from itself.

Before you've driven anywhere, every city except your starting one should look "unreachable" (∞) and have no recorded "how did I get here" road (null) — and your starting city costs 0 to reach from itself, trivially. initializeSingleSource just paints that blank starting picture onto every vertex.

Small example. Vertices s, t, x with source s. After the call: d[s] = 0, d[t] = ∞, d[x] = ∞, and all three π = null. Nothing else about the graph (its edges!) is looked at.

Representation. Each vertex is a plain integer id (0, 1, 2, …); d and π are parallel Lists indexed by that id. "Nothing yet" is Dart's null, and ∞ is double.infinity.

Reading the three runs: the loop on lines 1–3 stamps the same pair of values on every vertex, and only line 4 treats the source differently. The custom player has no edges at all, which is the point: the procedure is pure per-vertex setup, Θ(V).

Do not start non-source vertices at 0 "to be safe". Every later relax only ever lowers an estimate, so a value that starts too low can never be corrected upward, and the algorithm would report a free route that does not exist. ∞ is the only starting value that is guaranteed to be ≥ the true answer.

Notice line 4 runs after the loop, and only once — it doesn't matter whether s is visited "first" or "last" by the loop in line 1, since line 4 overwrites whatever the loop set for s anyway. This procedure never looks at a single edge — it's purely per-vertex setup, which is also why the "custom input" example above only needs a vertex list, no edges at all. (One subtlety: if s lies on a negative cycle, the true δ(s,s) is −∞, and "d[s] = 0" is only an upper bound — see the upper-bound property in the last section.)

Dart implementation:

Input size → what is feasible. V ≤ 10⁶ → the Θ(V) loop is 10⁶ assignments, instant. The procedure is never the bottleneck: the algorithm that follows costs far more.

initializeSingleSource = Θ(V): every d = ∞, every π = null, except d[s] = 0. The invariant "d is an upper bound on the true distance" is true from this very first moment and is what all later proofs build on.

The one move: relax

To relax an edge (u, v) means to test whether the edge gives a shortcut to v, and to take the shortcut if it does. It is the only operation that ever changes an estimate in this lesson; every algorithm below is just a different schedule of relax calls.

relax asks one question about a single road: "if I drove to u the cheapest way I currently know, then took this one road to v, would that beat the cheapest way I currently know to reach v?" If yes, it updates v's estimate and remembers "I got to v via u this time." If no, it does nothing — v's current route is still at least as good.

Small example. Edge u→v has weight 6, d[u] = 0, d[v] = ∞. Candidate = 0 + 6 = 6, and ∞ > 6, so d[v] becomes 6 and π[v] = u. Relax the same edge again: 6 > 6 is false, nothing changes — a second relax on the same data is harmless.

The three players show the only two outcomes: the edge improves v (lines 2–4 run) or it does not (the function falls through to line 5). The third player lets you try a zero-weight edge, where a tie must NOT count as an improvement because the test is a strict ">".

relax only ever decreases d[v] (or leaves it unchanged) — it can never make an estimate worse. This is exactly why running relax extra times, or in a different order, never breaks correctness: by the upper-bound property (see the last section) d[v] never drops below δ(s,v), so the worst extra relax calls can do is nothing. What they cannot do is skip the edges that matter — that is what each algorithm's schedule guarantees.

relax is Θ(1). Right afterwards d[v] ≤ d[u] + w(u,v) always holds, so the edge is not improvable again until d[u] drops. The final Bellman-Ford check on line 6 is literally "is any edge still improvable?".

Dart implementation:

Input size → what is feasible. one relax is a comparison and an addition, O(1). Bellman-Ford on V = 1000, E = 5000 calls it about 5·10⁶ times; Dijkstra and dagShortestPaths call it exactly E times.

relax(u, v, w): if d[v] > d[u] + w then d[v] ← d[u] + w and π[v] ← u. Θ(1), only lowers estimates, and is the single building block of Bellman-Ford, dagShortestPaths and Dijkstra.

Bellman-Ford: sweep every edge, again and again

Bellman-Ford is the "no assumptions" algorithm: it accepts negative edge weights, and it tells you when a negative cycle makes the question meaningless. It returns true if the estimates are the true shortest distances and false if a negative cycle is reachable from s.

Bellman-Ford is brute-force patience: it doesn't try to be clever about which edge to relax next — it just relaxes every single edge, in some fixed order, and repeats that n − 1 times (n = |V|). Why n − 1? Some shortest path has at most n − 1 edges (a simple path can't repeat a vertex), so after that many full sweeps, every shortest path's edges have been relaxed in order at least once — guaranteeing every d[v] has settled to δ(s,v) by the path-relaxation property (last section), as long as no negative-weight cycle is reachable from s. A final sweep checks: did anything STILL want to improve? If so, a negative cycle exists (with no such cycle every d would already equal δ and satisfy the triangle inequality, so no edge could improve).

Small example. Graph s→a (4), s→b (1), b→a (2), listed in that order, n = 3 so 2 passes. Pass 1: s→a sets a = 4; s→b sets b = 1; b→a offers 1 + 2 = 3 < 4, so a = 3. Pass 2: nothing improves. The check sweep finds nothing improvable → true, a = 3 via s→b→a.

In the first player (the route-cost graph) the edge order is fixed and several vertices improve more than once (c first drops to 15, then to −1; d improves three times: 5, 4, then 2), which is why a single sweep is not enough. In the second player the cycle s→t→x→s has weight 1 + 1 − 3 = −1: every lap lowers the estimates, the n − 1 passes cannot stop that, and the check sweep catches it. The third player has an unreachable vertex c, which keeps d = ∞ and does not disturb the answer.

Two classic mistakes. (1) Returning the distances without reading the true/false result: if it is false, the d values are meaningless. (2) "Detecting a negative cycle" only concerns cycles reachable from s: a negative cycle in a part of the graph the source cannot reach never triggers false, and it is correct that it does not (it cannot affect any δ(s,·)).

Running time: initializeSingleSource costs Θ(V); the double loop costs (n−1)·|E| = O(VE) relax calls; the final check costs O(E). Total: O(VE). For a dense graph (E = Θ(V²)) that's O(V³) — much slower than Dijkstra's O(V²) or O(E lg V), but Bellman-Ford is the only one of the two that tolerates negative edges (and it's the one that can prove there ISN'T a negative cycle, which Dijkstra cannot do at all).

Analysis visual: what pass i guarantees

The correctness argument is one sentence: "after pass i, every d is at most the cost of the best path that uses at most i edges." The tables below print both quantities side by side — the real d[v] after each pass (top table) and the exact "best path with ≤ i edges" optimum (bottom table) — so you can watch the first stay at or below the second and land on δ by pass n−1. Cells turn green when they equal δ.

The second player is the adversarial case: the chain's edges are listed in reverse order, so each pass can only push the information one hop, and the last vertex needs all n−1 passes. With a friendlier edge order the d row runs ahead of the "≤ i edges" row and converges earlier — that is why stopping early after a pass with no change (see the early-stopping question in the bank) is a safe optimisation.

Dart implementation:

Dart: the exact relax count of the double loop, (V − 1)·E, measured on graphs with V = 10, 100, 1000 and E = 3V; and the correctness idea “after pass i, d[v] is at most the best weight of a path with at most i edges”, checked pass by pass on the route-cost graph.

Input size → what is feasible. V ≤ 1000, E ≤ 5000 → (V−1)·E ≈ 5·10⁶ relaxations, instant. V = 10⁴, E = 5·10⁴ → 5·10⁸, several seconds. V = 10⁵, E = 2·10⁵ → 2·10¹⁰, hopeless: then you need non-negative weights (Dijkstra) or a DAG.

Bellman-Ford: n−1 sweeps over all edges, then one check sweep; O(VE). Returns false exactly when a negative cycle is reachable from s. Handles negative edges. Pass i settles every vertex whose shortest path has ≤ i edges.

Shortest paths in a directed acyclic graph

A DAG (directed acyclic graph) has no cycles at all. That single fact removes the hard part of the problem: with no cycles there are no negative cycles, so shortest paths are always well defined, and there is an order in which a single sweep is enough.

If the graph has no cycles at all, you don't need Bellman-Ford's brute-force repetition — you can relax every vertex's out-edges exactly once, as long as you process vertices in an order where every vertex comes before all the vertices it can reach: a topological order (see the graph basics lesson). Because a DAG has no cycles, once you've processed u in that order, u's estimate can never improve again later (nothing that comes "after" u in the order can have an edge back into u) — so a single pass suffices, and it works even with negative-weight edges, since there is no cycle for them to go around forever. Think of building a house: foundation before walls, walls before roof — process the jobs in an order where prerequisites always come first.

Small example. DAG a→b (2), a→c (7), b→c (−3), source a. Topological order a, b, c. Process a: b = 2, c = 7. Process b: c would be 2 + (−3) = −1 < 7, so c = −1. Process c: no out-edges. Done in one sweep even though an edge is negative: δ = (0, 2, −1).

The second player shows unreachable vertices (dimmed): the sweep still visits them, but ∞ + w = ∞ never improves anything. The third player rejects any edge list containing a cycle with a clear message, because the topological order (and the whole one-pass argument) would not exist.

Running dagShortestPaths on a graph that is not acyclic silently gives wrong answers (a topological order does not exist, so the DFS produces some arbitrary order). Always check acyclicity first — the custom player does, and so should your code.

Running time: topological sort is Θ(V+E) (DFS-based); initializeSingleSource is Θ(V); the relax loop visits every vertex once and, over the whole run, every edge exactly once — Θ(V+E). Total: Θ(V + E), linear — the fastest of the three algorithms in this lesson, made possible entirely by the acyclic structure. Correctness: along any shortest path ⟨v₀,…,v_k⟩ the topological order relaxes the edges in exactly path order, so the path-relaxation property (last section) finishes the proof; unreachable vertices stay ∞ by the no-path property. A small saving: the last vertex in topological order has no out-edges, so the loop may skip it.

Operation counts for one run on the example DAG (weights irrelevant for counting), gathered by the same JavaScript implementation that drives the players:

Dart implementation (uses a DFS-based topological sort, the same technique as in the graph basics lesson):

Dart: dagShortestPaths visits each vertex once and relaxes each edge once. The code counts both on random acyclic graphs with V = 100, 1000, 5000 and E = 3V and checks the distances on the example DAG (negative weights, one pass).

Input size → what is feasible. V = 10⁵, E = 2·10⁵ → V + E = 3·10⁵ steps, instant (the recursive DFS here goes as deep as the longest path, so for V in the hundreds of thousands use an explicit stack or Kahn’s algorithm). The same instance would cost Bellman-Ford 2·10¹⁰.

Application: PERT charts and the critical path

A PERT chart (Program Evaluation and Review Technique) models a project as a DAG: edges are jobs and edge weights are how long each job takes; vertices are milestones ("events") that can be reached only after every job leading in has finished. A critical path is a longest path through the DAG: it is the chain of jobs that decides the earliest possible finish, because no other chain takes longer.

Cooking a dinner with several dishes in parallel: the total time is not the sum of all recipes, it is the time of the slowest chain of dependent steps (chop → simmer → plate). Speeding up any step off that chain gains nothing; slipping any step on it delays dinner. That slowest chain is the critical path.

Small example. Jobs: s→a 3, s→b 2, a→c 4, b→c 1, a→d 2, c→f 5, d→f 6. Chains to f: s-a-c-f = 12, s-a-d-f = 11, s-b-c-f = 8. Longest = 12, so the project takes at least 12 units and s→a→c→f is critical.

The trick: negate every edge weight and run dagShortestPaths — the shortest path under negated weights is the longest path under the real ones. Negative weights are harmless here, exactly because a DAG has no cycles. In the players below, the number under each event is its earliest start time (the negated d), and edge labels are job durations.

Longest path is NP-hard on general graphs (a positive cycle would let you loop forever). The negation trick works only because a PERT chart is acyclic — feed it a cycle and the "critical path" is not even defined. Also, several paths can tie for longest (second player): all of them are critical.

Variant: when the weights sit on the vertices (a job is a vertex, edges are only "must come before"), split each job into an "in" and "out" vertex joined by an edge of the job's duration, or equivalently add the vertex weight when relaxing into it; still Θ(V+E). Interview problems like "Parallel Courses III" (question bank) are exactly this. Another formulation keeps the weights positive but starts every estimate at −∞ and flips the comparison in relax to ">".

Dart implementation (reuses dagShortestPaths on negated durations):

Input size → what is feasible. V ≤ 10⁵ activities and E ≤ 2·10⁵ dependencies → Θ(V + E) ≈ 3·10⁵ steps. Checking every path instead would be exponential in the worst case.

dagShortestPaths: topologically sort, then relax each vertex's out-edges once. Θ(V+E), handles negative weights, requires acyclicity. Negate weights to get longest paths: that is the critical path of a PERT chart.

Dijkstra's algorithm: settle the nearest vertex first

Dijkstra's algorithm is the fast choice for graphs whose weights are all non-negative. It settles vertices one at a time in order of increasing distance, so each edge needs relaxing only once.

Dijkstra's algorithm is a "greedy conqueror": it maintains a set of settled vertices whose shortest-path weight is already known for sure, and repeatedly grabs the not-yet-settled vertex u with the smallest current estimate, declares u settled, and relaxes u's out-edges. The greedy claim is: "the not-yet-settled vertex with the smallest estimate right now MUST already have its true shortest distance" — which is only guaranteed to be true if every edge weight is non-negative (otherwise some vertex still in the queue could sneak in a cheaper route later through a negative edge, arriving from a direction the algorithm already stopped watching). Picture a flood of water spreading from s along pipes: the pipe lengths are the weights, and the water reaches the vertices in order of true distance.

Small example. s→a (1), s→b (4), a→b (2). Queue = {s:0, a:∞, b:∞}. Take s: a = 1, b = 4. Take a (smallest): b would be 1 + 2 = 3 < 4, so b = 3. Take b: done. Result (0, 1, 3). Each vertex was taken once and each edge relaxed once.

The first player runs on the road graph: watch the queue shrink and the settled set grow, always taking the smallest key. The second player is the counterexample: a negative edge lets a vertex that is already settled get a better distance later, and Dijkstra never looks back (red = wrong final values). The third player rejects negative weights up front.

Dijkstra never checks that weights are non-negative — it will run to completion and print out confident-looking (but WRONG) numbers on a graph with negative edges, silently. Always verify your weights before reaching for it; if any could be negative, use Bellman-Ford instead (or reweight first — see Johnson's algorithm in the all-pairs lesson, previewed in this lesson's Expert questions). Adding a big constant to every weight does not fix it: paths with more edges get penalised more, changing which path is shortest.

Running time (array-based minimum search, as implemented below): initializeSingleSource is Θ(V); the while loop runs V times, each minimum search scanning the whole array is O(V), giving O(V²) just for extractions; relaxing is O(E) total across the whole run. Total: O(V² + E) = O(V²). With a binary min-heap priority queue (see heapsort and priority queues) this drops to O((V+E) lg V); with a Fibonacci heap (see Fibonacci heaps) it drops further to O(V lg V + E) — the array version here is the simplest to reason about, so we start with it.

Analysis visual 1: the loop invariant

Dijkstra is correct because of this invariant: "whenever a vertex is taken, its d already equals δ". The players below check that sentence against the true δ (from Bellman-Ford) at every extraction: green rows keep the invariant, red rows break it. The proof idea, visible in the captions: any competing route to the extracted u must leave the settled set through some vertex y still in the queue; since u had the minimum key, d[y] ≥ d[u], and the rest of the route only adds non-negative weight — so it cannot beat d[u]. A negative edge is exactly what makes "only adds" false.

Analysis visual 2: cost table

The running time is not magic; it is two counters. The tables count how many array slots the minimum search scans (V per iteration, hence V²) and how many relax calls occur (one per edge, hence E), then price the same run with a binary heap and a Fibonacci heap.

Dart implementation (array-based priority queue, the simplest version):

Dart: Dijkstra’s cost counted (array version: V² slot scans and E relaxations; heap version: an ordered set with decrease-key = remove + add), the three bounds as functions with the sparse-versus-dense comparison, and the loop invariant as a test: d[u] = δ(s, u) at every extraction, true on the road graph and false with a negative edge.

Input size → what is feasible. V ≤ 1500 dense (E ≈ 10⁶) → array Dijkstra V² ≈ 2.25·10⁶ steps. V = 10⁵, E = 3·10⁵ → heap Dijkstra (V + E) lg V ≈ 6.6·10⁶, while the array version would need V² = 10¹⁰, hopeless. Any negative weight → switch to Bellman-Ford.

Dijkstra: greedy, non-negative weights only. O(V²) with an array, O((V+E) lg V) with a binary heap, O(V lg V + E) with a Fibonacci heap. Each vertex is extracted once, each edge relaxed once; a settled vertex is never revisited.

Difference constraints as a shortest-path problem

A system of difference constraints is a list of inequalities in which every line compares just two unknowns: x_j − x_i ≤ b. The question is whether numbers exist that satisfy all lines at once, and if so to find them. It is a special case of linear programming that needs no LP machinery at all. Variables are named x₀, x₁, … (the same numbering the Dart code uses).

A system of difference constraints is a list of rules like "x₁ − x₀ ≤ 3" (variable x₁ can be at most 3 more than x₀) — think of it as a set of scheduling deadlines: "task 1 must start at most 3 time units after task 0." Surprisingly, solving "does SOME assignment of numbers to the variables satisfy every rule at once?" is exactly a shortest-paths problem in disguise.

Small example. Constraints x₁ − x₀ ≤ 3, x₂ − x₁ ≤ −2, x₀ − x₂ ≤ 1. Rewrite each as "x_j ≤ x_i + b": x₁ ≤ x₀ + 3, x₂ ≤ x₁ − 2, x₀ ≤ x₂ + 1. That is exactly the triangle inequality d[j] ≤ d[i] + b of an edge (i → j) of weight b. The three edges form a cycle of weight 3 − 2 + 1 = 2 ≥ 0, so a solution exists (for instance x = (−1, 0, −2), which is exactly what Bellman-Ford from the extra start vertex z returns).

Build a constraint graph: one vertex per variable, plus one extra start vertex z with a zero-weight edge to every variable vertex (so every variable is reachable). For every constraint x_j − x_i ≤ b, add an edge (i, j) with weight b. Then run Bellman-Ford from z: if it detects a negative-weight cycle, the system is infeasible (a negative cycle among the constraint edges means the corresponding inequalities sum to something impossible, like 0 ≤ −1). Otherwise, setting each x_i = δ(z, i) satisfies every constraint (the triangle inequality on the constraint graph's edges IS exactly "x_j − x_i ≤ b" once x_i := d[i]).

The three players above build the constraint graph edge by edge from your constraints (the last one accepts your own system, in the exact format xj-xi<=b, for example x1-x0<=3). The next four run the algorithm and check the outcome.

Running Bellman-Ford on a constraint graph you type in

Checking the solution — or proving there is none

Direction matters: x_j − x_i ≤ b becomes the edge from i to j (tail = the variable being subtracted). Flipping it builds the graph of the negated system and gives wrong feasibility answers. A constraint with the "wrong" shape, like x₀ + x₁ ≤ 4 or x₀ ≥ 5, is not a difference constraint at all (single-variable bounds can be modelled by comparing against a reference variable that is pinned to 0).

The output is not just a solution: Bellman-Ford returns the componentwise-largest solution with all x_i ≤ 0, and it also minimises max x_i − min x_i, which is exactly what a construction scheduler wants (shortest overall time window). With n variables and m constraints the graph has n+1 vertices and n+m edges, so the plain algorithm costs O((n+1)(n+m)) = O(n² + nm). Equality constraints x_i = x_j + b are two inequalities.

Why z's edges all have weight 0: they exist purely to guarantee every variable vertex is reachable from SOME source (so Bellman-Ford's d-values are all finite unless there's genuinely a negative cycle among the real constraint edges) — they never participate in any negative cycle themselves, since z has no INCOMING edges, so no cycle can pass back through it. Feasible ⇔ no negative cycle; and no δ(z, i) can be positive, since the 0-weight edge (z, i) already gives d ≤ 0.

Dart implementation (builds the constraint graph, then reuses bellmanFord above):

And a checker for a candidate assignment (used by the tests to confirm that Bellman-Ford's output satisfies every constraint):

Dart: the facts about the constraint graph as executable checks: the Bellman-Ford distances solve the system, every δ(z, i) ≤ 0, adding a constant to every x[i] keeps every constraint true, the graph has n + 1 vertices and m + n edges so the main loop does n·(m + n) relaxations, and a negative cycle means no solution.

Input size → what is feasible. n = 1000 variables and m = 5000 constraints → n·(m + n) = 6·10⁶ relaxations, instant. n = 10⁴, m = 10⁵ → 1.1·10⁹, too slow for one second; use an early-stopping Bellman-Ford, a queue-based variant, or an LP solver.

Six properties that explain why relaxing works

This is where every "why does this work?" gets answered. Instead of one long proof per algorithm, the algorithms rest on six short properties — facts that hold no matter which order you relax edges in. Each player below runs a real relaxation sequence on a graph (default: s→a 5, s→b 2, b→a 1, a→c 3, c→t −1, plus x→s 4 where x is unreachable; the edge order is deliberately unfriendly so several passes are needed) and shows the property happening. All six accept your own source | u->v:w, … edge list (no negative cycle reachable).

Think of the estimates as price tags in a shop that only ever gets marked DOWN. The tags can never go below the real cost (upper bound), an item you cannot deliver keeps a tag of "∞" (no path), and once the supplier and the shipping leg are both at their real price, the item's tag becomes the real price too (convergence). Each property is one such promise about how tags behave.

Small example. Graph s→b (2), b→a (1), s→a (5). True distances: b = 2, a = 3 (via b). Start: a = ∞. Relax (s,a): a = 5, still ≥ 3. Relax (s,b): b = 2. Relax (b,a): a = 3 = δ. At no moment did a drop below 3, and after reaching 3 it stayed there.

1 · Triangle inequality

For every edge (u,v): δ(s,v) ≤ δ(s,u) + w(u,v). Why it is true: the route "cheapest to u, then this edge" is one candidate path to v, and δ(s,v) is the minimum over all candidates. Tight edges (equality) are the ones a shortest-paths tree may use.

Dart: the triangle inequality as a function over every edge. randomGraph is the seeded test-graph generator reused by the property panels below.

2 · Upper-bound property

d[v] ≥ δ(s,v) for all v after initializeSingleSource and after any sequence of relaxations; and once d[v] = δ(s,v) it never changes again. Why: each relax sets d[v] to d[u] + w, and d[u] + w ≥ δ(s,u) + w ≥ δ(s,v) by the triangle inequality; a value at the floor cannot go lower.

Dart: 200 random graphs, 60 arbitrary relax calls each, with the upper bound, “right after relax, d[v] ≤ d[u] + w” and “a value at its floor never changes” tested after every call.

3 · No-path property

If there is no path from s to v, then d[v] = δ(s,v) = ∞ always. Why: by the upper bound d[v] ≥ ∞, so it can never leave ∞. This is why a final d = ∞ is a trustworthy "unreachable" verdict.

Dart: after arbitrary relaxations every unreachable vertex still has d = ∞ and π = null.

4 · Convergence property

If s ⇝ u → v is a shortest path and d[u] = δ(s,u) at some moment before relax(u,v,w), then d[v] = δ(s,v) at every moment after. Why: the relaxation makes d[v] ≤ δ(s,u) + w(u,v) = δ(s,v), and the upper bound forbids going lower.

Dart: whenever the premise holds (the tail is exact and the edge lies on a shortest path), the head is exact right after relax and stays exact.

5 · Path-relaxation property

If p = ⟨v₀,…,v_k⟩ is a shortest path from s = v₀ and its edges are relaxed in the order (v₀,v₁), …, (v_{k−1},v_k) — with any other relaxations mixed in — then d[v_k] = δ(s,v_k). Why: apply the convergence property once per edge, left to right. This is the property that proves Bellman-Ford (n−1 full sweeps contain every ordered subsequence) and dagShortestPaths (topological order relaxes path edges in order).

Dart: relax the edges of a shortest path in path order, mixing in unrelated relaxations between them; the last vertex ends exact.

6 · Predecessor-subgraph property

The predecessor subgraph Gπ has an edge (π[v], v) for every vertex with a predecessor. If no negative cycle is reachable from s, Gπ is always a tree rooted at s; once every d[v] = δ(s,v), it is a shortest-paths tree. Why: each relax replaces a vertex's single parent, so it stays one parent per vertex; a cycle of parent pointers would mean a negative cycle. The second player shows the failure when such a cycle exists.

Dart: predecessorSubgraphIsTree is true after every relaxation when no negative cycle is reachable, isShortestPathTree is true at the end, and with a reachable negative cycle the parents loop (so the guarantee fails).

Input size → what is feasible. these six properties are proof tools, not algorithms: the checks above run on graphs of 6 to 7 vertices (a few thousand relaxations), which is all a property test needs. Each property holds for every graph size.

Two traps. (1) The convergence and path-relaxation properties are about shortest paths: relaxing the edges of a non-shortest path in order proves nothing about δ. (2) Dijkstra's correctness is not via path-relaxation: it does not necessarily relax a shortest path's edges in path order (with a zero-weight edge a tie can make it relax them out of order — see the question on exactly this); its proof is the separate loop invariant above.

How the six fit together: the triangle inequality gives the upper bound (each new estimate is a real path weight), the upper bound gives no-path and convergence, convergence chained along a path gives path-relaxation, and path-relaxation plus tightness gives the predecessor-subgraph tree. That chain is the whole correctness story of Bellman-Ford and dagShortestPaths, and (together with the loop invariant) of Dijkstra.

The six properties: triangle inequality δ(v) ≤ δ(u)+w; upper bound d ≥ δ forever; no path ⇒ d = ∞ forever; convergence: u at δ, then relax (u,v) ⇒ v at δ; path relaxation: relax a shortest path's edges in order ⇒ its end at δ; predecessor subgraph: a tree, and at the end a shortest-paths tree.

Quiz

Interview questions

Cheat sheet

Algorithm / idea	Time (best / avg / worst)	Space	Negative edges?	Negative cycle?	When to use
initializeSingleSource	Θ(V) always	O(V)	n/a	n/a	Setup step every single-source algorithm calls first
relax	Θ(1) always	O(1)	n/a	n/a	The one primitive every algorithm below is built from
Bellman-Ford	Θ(V+E) with early stop once d has converged; O(VE) worst; the plain version is Θ(VE) always	O(V)	Yes	Detects it (returns false)	General graphs, negative edges allowed, need cycle detection; also difference constraints, arbitrage
dagShortestPaths	Θ(V + E) always	O(V)	Yes (no cycles exist to go negative around)	Impossible in a DAG	Graph is known acyclic (task scheduling, PERT charts, longest path via negation)
PERT critical path	Θ(V + E) always	O(V)	Durations ≥ 0 (negated internally)	Needs an acyclic graph	Earliest project finish, zero-slack jobs
Dijkstra (array queue)	Θ(V²) always (E ≤ V²)	O(V)	No — gives silently wrong answers	Not detected: terminates but returns wrong values	Non-negative weights, dense graphs
Dijkstra (binary heap)	O((V+E) lg V)	O(V)	No	—	Non-negative weights, sparse graphs
Dijkstra (Fibonacci heap, see Fibonacci heaps)	O(V lg V + E) amortised	O(V)	No	—	Non-negative weights, very large sparse graphs
Difference constraints	O((n+1)(n+m)) via Bellman-Ford	O(n + m)	Yes	= infeasible system	Scheduling / deadline systems modelled as x_j − x_i ≤ b
The six shortest-path properties	— (proof tools)	—	—	Tree guarantee needs none reachable	Why relax schedules work: triangle, upper bound, no path, convergence, path relaxation, predecessor subgraph