Mathematics for Data Science 1 - W11_L5: Single source shortest paths | dijkstra’s algorithm

Welcome to Week 11 Lecture 5 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 introduces the single-source shortest path problem in weighted graphs. We study how to compute the shortest path from a given source vertex to all other vertices when edge weights represent distances or costs. The lecture presents Dijkstra’s Algorithm, a fundamental algorithm that efficiently solves this problem in graphs with non-negative edge weights. Using the fire propagation analogy, we build intuition for how the algorithm expands outward, step by step. We also explain the algorithm’s implementation, its limitations in the presence of negative edge weights, and why alternative methods are needed in such cases. This forms the foundation for solving practical pathfinding and network optimization problems. 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 #WeightedGraphs #ShortestPath #SingleSourceShortestPath #DijkstraAlgorithm #GraphTheory #Algorithms #ComputerScience #Pathfinding #Optimization #NetworkAnalysis #NonNegativeWeights #GraphAlgorithms #ShortestPathProblem #DataStructures #AlgorithmAnalysis