Negative-length shortest paths and all-pairs shortest paths

Overview

Kent Quanrud develops a dynamic-programming approach to shortest paths with negative edge lengths, first bounding walks by their number of edges and then using the resulting Bellman–Ford-style relaxation to identify negative-infinity distances. For all-pairs shortest paths, he compares a doubling-based recurrence running in O(n³ log n) with Floyd–Warshall’s O(n³) recurrence, and previews Johnson’s algorithm as a way to handle negative edges more efficiently.

Key takeaways

Dijkstra’s greedy ordering fails with negative edges because a vertex that appears close can later receive a shorter route through an edge with negative length.
If a source-to-destination distance is finite, a shortest walk is attained by a path; a cycle in a shortest walk either can be removed without increasing length or can be repeated to force negative infinity.
The bounded-edge recurrence computes shortest walks in O(k(m+n)) time, and n−1 edge rounds suffice for finite distances because a shortest path has at most n−1 edges.
Vertices improved on round n have negative-infinity distance; a graph search from that improvement set identifies every destination with negative-infinity distance.
Doubling the permitted edge count yields an all-pairs algorithm in O(n³ log n), while Floyd–Warshall’s intermediate-vertex recurrence improves this to O(n³).
Adding a zero-length super-source edge to every vertex lets the single-source relaxation detect negative cycles across the graph.

Chapters

0:00 Why Dijkstra’s Distance Ordering Fails with Negative Edges

The opening grid example allows repeated walks and illustrates how negative edge lengths can produce a best total below zero.
Dijkstra’s algorithm can finalize a vertex too early: a later route through a negative edge may lower its distance.
The failure does not require a negative cycle; the greedy closest-to-furthest ordering itself is no longer reliable.

4:20 Negative Cycles Make Walk Distances Unbounded

A reachable negative cycle can be traversed repeatedly, making the infimum walk length from a source to a destination negative infinity.
With negative edges, shortest walks and shortest paths need to be distinguished because a walk may repeat vertices.
Algorithms must account for both finite shortest distances and destinations whose distances are negative infinity.

7:17 Finite Shortest-Walk Distances Are Attained by Paths

Quanrud proves that, when s can reach t, a finite distance from s to t is attained by a path.
Among shortest walks, choose one with the fewest edges; if it contains a nonnegative cycle, removing that cycle does not increase its length and reduces its edge count.
If the walk contains a negative cycle, repeating the cycle produces a walk shorter than the supposed finite minimum, a contradiction.

15:20 Why Repeatedly Revisiting Improved Vertices Can Be Slow

One tempting fix is to let a Dijkstra-like process revisit vertices whenever a better distance appears.
A chain of triangles with edge lengths near 1 and -1 can reveal improvements one at a time, forcing repeated scans of the graph.
This motivates an algorithm with a clear progress measure rather than relying on eventual self-correction.

23:24 Bounded-Edge Walks Provide a Progress Measure

Define a subproblem as finding the shortest walk from a fixed source using at most k edges.
For k = 0, the distance is 0 when the destination is the source and positive infinity otherwise.
Increasing k by one gives a systematic recurrence even when edge lengths are negative.

28:48 The Bellman–Ford-Style Relaxation Recurrence

For each destination v, either retain its best distance using at most i−1 edges or enter v from an in-neighbor w.
The recurrence takes the minimum of the previous value and the best distance to w using at most i−1 edges plus the length of edge (w,v).
Considering all incoming edges handles the final step of every candidate walk without assuming distances are processed in order.

34:41 Running Time and the n−1-Edge Bound

With dynamic programming, each round processes all vertices and incoming edges, giving O(k(m+n)) time, conventionally written O(km) when m ≥ n.
If there are no negative-infinity distances, a shortest walk can be represented by a path.
A path on n vertices uses at most n−1 edges, so n−1 rounds suffice to obtain every finite shortest distance.

38:56 Detecting Negative-Infinity Distances on Round n

Let A_k contain the vertices whose best distance improves when the edge limit increases from k−1 to k.
An improvement at round n cannot be the final finite answer: a finite shortest path would already have been found within n−1 edges.
Therefore, every vertex improved in round n has distance negative infinity.

43:02 Improvements Propagate Along Outgoing Edges

If a vertex improves in round k+1, at least one of its in-neighbors must have improved in round k.
Otherwise, the recurrence would use unchanged in-neighbor values and could not produce a new improvement.
Consequently, later-improving vertices are reachable from the round-n improvement set.

49:30 Reachability Marks Every Negative-Infinity Destination

Every vertex reachable from a vertex in A_n also has distance negative infinity: the improving source can be made arbitrarily cheap before taking the finite route onward.
Combined with the improvement-propagation argument, this shows that the negative-infinity destinations are exactly the vertices reachable from A_n.
Run DFS or BFS from all vertices in A_n to classify the full set.

53:12 Extending Single-Source Relaxation to All Pairs

Assume the graph has no negative cycles, so all-pairs shortest-path distances are finite whenever the corresponding vertices are reachable.
A negative cycle can be detected by adding a super-source with zero-length edges to every vertex and applying the preceding relaxation method.
Running the single-source O(mn) method from each of n sources gives an O(mn²) all-pairs baseline.

55:08 All-Pairs Dynamic Programming with Bounded Edge Counts

Make both source s and destination t parameters in the shortest-walk subproblem, alongside the edge limit i.
Use the same recurrence: retain the best value for at most i−1 edges or add one incoming edge to t.
Summing across n sources and n rounds gives O(mn²) time, with the edge scans accounting for m.

58:14 Doubling the Edge Limit to Reduce Recurrence Rounds

Compute shortest walks with limits 1, 2, 4, 8, and so on, rather than processing every edge count up to n.
For a 2^i-edge limit, test every midpoint u and combine the best s-to-u and u-to-t walks using at most 2^(i−1) edges.
There are O(log n) limits, n² source-destination pairs, and n midpoint choices, for O(n³ log n) time.

1:03:03 Floyd–Warshall: Restricting Intermediate Vertices

Number the vertices 1 through n and define a subproblem by the endpoints i,j and the largest allowed intermediate-vertex index k.
At k = 0, the answer is 0 for i = j, the edge length for a direct edge from i to j, and positive infinity when neither option exists.
This formulation builds toward allowing every vertex as an intermediate point, without bounding the number of edges in a walk.

1:08:00 Floyd–Warshall’s O(n³) Recurrence and Johnson Preview

For each k, either exclude vertex k as an intermediate or route through it: D(i,j,k) = min(D(i,j,k−1), D(i,k,k−1) + D(k,j,k−1)).
The recurrence takes constant time per subproblem and has n choices each for i, j, and k, yielding O(n³) time.
Quanrud closes by previewing Johnson’s algorithm: reweight negative edges so Dijkstra can be run from each source, a technique explored in the homework.

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.