Algorithm Science (Summer 2025) - 34 - Minimum Cost Paths I

Описание: This video was made as part of a second-year undergraduate algorithms course sequence (Algorithms and Data Structures I and II).

0:00 Wanderlust
12:53 Finding Feasible Paths
18:27 Optimization Strategy
30:28 Improving a Feasible Solution
47:35 First Algorithm Attempt
50:24 Starting From Nothing
1:03:19 Infeasibility
1:08:04 Unboundedness
1:21:27 Proof of Correctness
1:35:48 The Bellman-Ford Algorithm

In retrospect, I think the wording of Theorem A is a bit sloppy, since it isn't a good idea to talk about "minimum cost walks" in graphs which may contain negative cost cycles. A better phrasing might be "If P is a u-v walk of cost at most t with the smallest number of edges among all u-v walks of cost at most t and contains repeated vertices, then G contains a negative cost cycle". The logic of the proof (and the implications of the theorem) will be basically the same. A revised version of Theorem A appears briefly in a flashback in Lecture 40.

There is a technical simplification lurking under the treatment of negative cost cycles in this lecture (and Lectures 35 and 36) that could be dangerous in some cases that might apply in higher-level courses. We treat a minimum cost path problem on a graph with negative cost cycles as "unbounded" and unsolvable since there is no answer to questions like "what is the minimum cost to travel from vertex u to vertex v?". However, you may notice that the problem is only unbounded if we allow travel along arbitrary walks and not true paths (which cannot repeat vertices and therefore cannot actually produce the degenerate case that leads us to rule out graphs with negative cost cycles). So technically there could be a minimum weight path from u to v even if there is a way to encounter a negative cost cycle along the way (and there are algorithms that can solve the problem consistently on graphs with negative cost cycles). Since the Bellman-Ford algorithm really finds a minimum cost walk between vertices, it breaks on graphs with negative cost cycles (but in all other graphs, a minimum cost path between two vertices will also be a minimum cost path). The only place the walk/path simplification is acknowledged in the lecture itself is in the statements and proofs of Theorem A and Theorem B.

For a detailed history of the minimum cost path problem (aka the shortest path problem), see
A. Schrijver. "On the history of the shortest path problem", Documenta Mathematica, vol. 17, no. 1 (2012), 155-167 (https://dx.doi.org/10.4171/DMS/6/19).
Thanks to University of Georgia Libraries for scanning and providing the 1959 article "The Shortest Path Through a Maze" by Edward F. Moore.

All slides and diagrams are original content (developed in early 2025). The materials used in this video, and the video itself, were prepared without any assistance from generative AI.

As any viewer will quickly realize, these videos were made just like in-person lectures: in one sitting, with no breaks, editing or script. If you find any of this helpful or interesting, please let me know (I really appreciate any other feedback as well).