Mathematics for Data Science 1 - W11_L7: All-pairs shortest paths | floyd-warshall algorithm

Welcome to Week 11 Lecture 7 of the course "Mathematics for Data Science I" by Profs. Neelesh Upadhye, Madhavan Mukund. Full Course: https://study.iitm.ac.in/ds/course_pages/BSMA1001.html Video Overview This lecture extends the study of shortest paths in weighted graphs to the all-pairs shortest path problem. Building on earlier discussions of single-source shortest paths (Dijkstra’s and Bellman-Ford), we introduce the Floyd-Warshall Algorithm, a powerful method that efficiently computes the shortest path between every pair of vertices. We explain its foundation in Warshall’s Algorithm, which is described as an iterative matrix-based approach for computing transitive closure. The lecture demonstrates how Floyd-Warshall can handle graphs with negative edge weights, provided no negative cycles exist, and illustrates its iterative updates to the distance matrix with examples. About IIT Madras' online Bachelor of Science programme IIT Madras offers four-year BS programmes that aim to provide quality education to all, irrespective of age, educational background, or location. The BS programme has multiple levels, which provide flexibility to students to exit at any of these levels. Depending on the courses completed and credits earned, the learner can receive a Foundation Certificate from IITM CODE (Centre for Outreach and Digital Education), Diploma(s) from IIT Madras, or BSc/BS Degrees from IIT Madras. For more details, visit: https://www.iitm.ac.in/academics/study-at-iitm/non-campus-bs-programmes #ShortestPaths #WeightedGraphs #FloydWarshall #Algorithm #GraphTheory #Dijkstra #BellmanFord #AllPairsShortestPath #SingleSourceShortestPath #TransitiveClosure #WarshallAlgorithm #NegativeWeights #NegativeCycles #ComputerScience #DataStructures #Algorithms #ShortestRoute #Optimization #GraphAlgorithms