Algorithm Science (Summer 2025) - 36 - Minimum Cost Paths III

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

0:00 Introduction
2:45 All-Pairs Minimum Cost Paths
16:58 Overlapping Subproblems
28:19 Restricted Reachability
45:09 Just Passing Through
59:48 The Floyd-Warshall-Roy Algorithm
1:19:07 Recovering Paths
1:22:35 Another Example
1:28:30 Negative Cycles
1:36:53 Summary of Minimum Cost Path Algorithms

There is a typo on Slide 83 (first seen at 1:01:17): The recursive expansion of m(i,j,k) should be
m(i,j,k+1) = min( m(i,j,k), m(i,k+1,k) + m(k+1,j,k) )
(This typo seems to be local to Slide 83 and does not affect the following slides)

B. Roy’s 1959 article on the transitive closure problem was written in French. The following English article includes a summary of Roy’s transitive closure algorithm and its relationship to later work by Warshall and Floyd.
P. Hansen and Dominique de Werra. Connectivity, transitivity and chromaticity: the pioneering work of Bernard Roy in graph theory, In: Aiding Decisions with Multiple Criteria. International Series in Operations Research and Management Science, vol. 44 (2002)

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).