Shortest Paths

Overview

Kent Quanrud develops shortest-path algorithms from first principles: breadth-first search (BFS) finds minimum-hop paths in O(m+n), while Dijkstra’s algorithm handles positive edge lengths by repeatedly settling the vertex with the smallest tentative distance. He derives Dijkstra’s correctness and runtime, including the O(m+n log n) bound with a Fibonacci heap, then shows how to reduce an even-edge-count shortest-walk problem to ordinary shortest paths using a two-layer graph with only 2n vertices and 2m edges.

Key takeaways

BFS computes minimum-hop distances in O(m+n) by expanding vertices in layers; induction on layer number proves that each layer matches the true distance.
Subdividing an integer-weight edge into unit edges preserves shortest-path answers but can be pseudo-polynomial because runtime depends on the weight’s numeric value, not just its O(log W)-bit encoding.
Dijkstra’s correctness for positive edge lengths follows by induction on the order vertices are settled: the predecessor on a shortest path is settled earlier, so the next minimum tentative label is final.
A binary heap gives Dijkstra an O((m+n) log n) bound, while Fibonacci-heap amortized O(1) decrease-key improves it to O(m+n log n).
To enforce an even number of edges, duplicate each vertex into even and odd states and flip parity on every edge; the resulting graph grows only from n,m to 2n,2m.
Expanded-state graphs generalize naturally: a path-length constraint modulo 5 uses five copies of each vertex, with transitions advancing between layers.

Chapters

0:00 Shortest Paths Begin with Minimum-Hop Routes

The initial problem is to travel from S to T using as few edges as possible.
A hand-picked route on the example graph has seven edges, but visual inspection does not certify that no shorter route exists.
The challenge is to find a systematic method that also makes its answer verifiable.

4:28 Weighted Distance, Infinite Values, and the Triangle Inequality

For a directed graph with edge lengths, a walk’s length is the sum of its edge weights, and distance is the infimum over S-to-T walks.
Distance is positive infinity when no walk connects the vertices and can be negative infinity when walk lengths are unbounded below.
Distances satisfy the triangle inequality: d(S,T) ≤ d(S,X) + d(X,T), since the two walks can be concatenated.

5:08 BFS Finds Minimum-Hop Distances in Layers

BFS starts with S at distance 0, labels its outgoing neighbors 1, then expands the vertices at distance 1 to find distance 2.
Each new layer is generated from the previous layer, and already-labeled vertices are not assigned a longer distance.
With adjacency lists, each vertex and edge is processed only a constant number of times, giving O(m+n) time.

11:05 Proving BFS Correct with Induction on Distance

Define Aₖ as the vertices whose true graph distance from S is k and Bₖ as the vertices BFS labels k.
The base case is k=0: both sets contain only S.
For k>0, a vertex is at distance k exactly when it is not closer and has an incoming edge from a vertex at distance k−1; BFS uses the same recurrence.
Induction establishes Aₖ=Bₖ for every layer, certifying all BFS distance labels.

18:33 Positive Edge Lengths Replace Hop Counts

The weighted version assigns positive lengths to edges, such as travel times or distances, and seeks the route with the smallest total.
The example route’s edge lengths add to 15, illustrating why counting edges no longer suffices.
A possible strategy is to adapt BFS’s expansion order from hop count to accumulated path length.

20:55 Why Subdividing Weighted Edges Can Be Too Slow

For positive integer weights, an edge of length 5 can be replaced with a chain of five unit edges, making BFS return the weighted distance.
This subdivision can take time proportional to the numeric edge weights, which may be exponentially larger than their O(log W)-bit input representation.
The key improvement is to skip empty distance layers and identify the next closest original vertex directly.

25:40 Dijkstra’s Algorithm Selects the Next Closest Vertex

Dijkstra’s algorithm begins with distance 0 at S and repeatedly selects the not-yet-settled vertex with the smallest candidate distance.
Candidates come from a settled vertex u via an outgoing edge (u,v), with value d(u)+length(u,v).
The method simulates BFS’s next-layer progression without iterating through every possible distance value, so it also works for non-integer positive lengths.

28:35 Dijkstra Correctness Uses the Algorithm’s Vertex Order

Order vertices by when Dijkstra labels them, then prove by induction that each selected vertex is the next closest one and receives its true distance.
The first vertex is S, correctly labeled 0.
For the induction step, the predecessor on a shortest path to the next closest vertex was settled earlier; positive edge lengths ensure that predecessor is closer.
Separating the algorithm’s tentative choice from the graph’s true closest vertex makes the correctness argument explicit.

36:20 Tentative Distances Avoid Recomputing Old Candidates

A naive implementation scans all m edges to find the next vertex for each of up to n iterations, costing O(mn).
For each unsettled vertex v, maintain its tentative distance: the best candidate found so far through a settled vertex.
When a new vertex is settled, only its outgoing edges can introduce new candidates, avoiding repeated work on previously processed edges.

40:20 Binary Heaps Improve Dijkstra’s Runtime

A min-priority queue stores unsettled vertices keyed by tentative distance and supports insert, decrease-key, and extract-min.
With a binary heap, each queue operation takes O(log n); processing outgoing edges across the whole run accounts for O(m) edge updates.
The resulting bound is O((m+n) log n), rather than the naive O(mn).

45:10 Fibonacci Heaps Reduce Decrease-Key Costs

A Fibonacci heap supports insert and decrease-key in O(1) amortized time and extract-min in O(log n) amortized time.
Amortized analysis bounds the total cost of an operation sequence, even if occasional individual operations take longer.
Dijkstra performs O(m) decrease-key operations and O(n) extract-min operations, yielding O(m+n log n) total time.

54:45 Shortest Walks with an Even Number of Edges

The new task is to find the minimum total length of an S-to-T walk using an even number of edges.
A standard shortest-path run does not track whether a route reaches an intermediate vertex after an odd or even number of edges.
Rather than complicating Dijkstra’s logic with backtracking, encode the constraint in a transformed graph and reuse a known shortest-path algorithm.

1:00:15 Two-Edge Shortcuts Work but Can Create a Dense Graph

Create an auxiliary edge for each pair of consecutive original edges, with weight equal to their combined length.
Paths in the auxiliary graph map to even-edge walks in the original graph, and even-edge walks map back by grouping edges in pairs.
A high-degree intermediate vertex can produce Θ(n²) shortcut edges, increasing Dijkstra’s cost to roughly O(n²+n log n).

1:04:50 Why a Sparse Reduction Needs to Track Route State

Removing some vertices or pruning shortcut edges does not generally eliminate the Θ(n²) blowup in the worst case.
The useful idea is to remember extra information about a route’s state—whether its edge count is currently odd or even.
Representing that state explicitly avoids adding every possible two-edge shortcut.

1:09:55 Parity Layers Generalize to Modulo-5 Path Constraints

Make two copies of every vertex, labeled even and odd; each original edge from a to b becomes transitions from a-even to b-odd and from a-odd to b-even.
Run Dijkstra from S-even to T-even; reaching T-even corresponds exactly to an even-edge walk, and the transformed graph has 2n vertices and 2m edges.
For a walk whose edge count must be divisible by 5, use five copies of each vertex and advance one layer per edge, wrapping around modulo 5.
This expanded-state construction is a reduction: prove the transformed paths correspond to valid original walks, then apply the already-proved shortest-path algorithm.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.