W5_L3: Single source shortest paths with negative weights | bellman-ford algorithm)

Welcome to Week 5 Lecture 3 of the course "Programming, Data Structures and Algorithms using Python" by Prof. Madhavan Mukund. Full Course: https://study.iitm.ac.in/ds/course_pages/BSCS2002.html Video Overview This lecture extends the discussion on the single-source shortest path problem in weighted graphs by examining how negative edge weights affect algorithm performance. We revisit Dijkstra’s algorithm to understand why it fails when negative weights are present, and then introduce the Bellman-Ford Algorithm, which correctly computes shortest paths even with negative weights — provided there are no negative cycles. The lecture explains the core logic, step-by-step implementation, and time complexity of Bellman-Ford, and demonstrates how the algorithm can also be used to detect negative cycles within a graph. 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 #ShortestPath #GraphAlgorithms #Dijkstra #BellmanFord #NegativeWeights #NegativeCycles #Algorithms #ComputerScience #GraphTheory #SingleSource #WeightedGraphs #Pathfinding #AlgorithmDesign #PythonProgramming #DataStructuresAndAlgorithms #IITMadras