Last Minute Lecture

All-Pairs Shortest Paths — Floyd-Warshall, Johnson’s Algorithm & Matrix Methods | Chapter 23 in Introduction to Algorithms Chapter 23 of Introduction to Algorithms (CLRS) dives into solving one of the most fundamental problems in graph theory: the all-pairs shortest paths (APSP) problem. This chapter introduces several algorithmic strategies—ranging from matrix multiplication using the tropical semiring to the efficient Floyd-Warshall and Johnson’s algorithms—that compute shortest path distances between every pair of vertices in a weighted, directed graph. These methods are widely applicable in routing, scheduling, reachability analysis, and computational optimization. 📺 Watch the full video above for a comprehensive summary, or continue reading for a detailed, searchable guide to every major algorithm and concept in Chapter 23. What Is the All-Pairs Shortest Paths Problem? The APSP problem aims to compute the shortest paths between all pairs of vertices in a graph. T...

Dynamic Programming — Rod Cutting, Matrix Chain Multiplication, LCS, and Optimal BSTs | Chapter 14 of Intro to Algorithms Dynamic programming (DP) is a powerful algorithmic technique that revolutionizes how we solve complex optimization problems by decomposing them into overlapping subproblems and storing solutions to avoid redundant computation. Chapter 14 of introduction to algorithms explores the essential principles of dynamic programming, provides classic problem examples such as rod cutting, matrix-chain multiplication, longest common subsequence (LCS), and optimal binary search trees, and explains why DP is a core concept for computer scientists and programmers. For a concise video walkthrough and visual examples, watch the chapter summary below. Don’t forget to subscribe to Last Minute Lecture for more algorithm deep-dives. What Is Dynamic Programming? Dynamic programming is used to efficiently solve problems that feature both overlapping subproblems and opti...