Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
This lecture covers the Bellman-Ford algorithm for finding the shortest path in a directed graph with edge weights, focusing on the iterative process of updating shortest path estimates using the RELAX function. The instructor explains the algorithm's correctness, optimal substructure, and termination conditions, emphasizing the importance of avoiding negative cycles. Additionally, a problem-solving scenario involving altitude differences in a ski resort is presented to illustrate the practical application of the algorithm.