All Pairs Shortest Path Algorithm by Floyd Warshall

In this video, we explore the All-Pairs Shortest Path (APSP) problem and one of the most elegant algorithms in computer science: the Floyd–Warshall Algorithm. Given a weighted graph, APSP asks us to find the shortest path between every pair of vertices. While running Dijkstra’s algorithm repeatedly is one option, Floyd–Warshall provides a remarkably simple dynamic programming solution that works for directed graphs, supports negative edge weights (as long as there are no negative cycles), and runs in O(n^3) time. We begin by examining intuitive recursive formulations for APSP and discuss why some seemingly reasonable recurrences fail to lead to efficient dynamic programs. This naturally motivates the key insight behind Floyd–Warshall: introducing a third parameter that limits which intermediate vertices are allowed on a path. From this idea emerges the famous recurrence that incrementally builds shortest paths by considering larger and larger sets of allowable intermediate nodes. Along the way, we connect Floyd–Warshall to Bellman’s Principle of Optimality, shortest-path decomposition strategies, and even ideas from formal language theory such as ambiguity in recursive structures. Through examples, visualizations, and step-by-step derivations, you'll gain a deep understanding of not just how Floyd–Warshall works, but why its dynamic programming formulation is so powerful and elegant. Perfect for students of algorithms, computer science, and optimization.