Lect 38: Shortest Path Problem with Negative Weights

In Friday’s lecture, we began with an iterative version of the dynamic program for the weighted interval scheduling problem and then looked at the shortest path problem on graphs with no negative cycles. The slides have been uploaded.

In Monday’s lecture, we will finish the dynamic program for the shortest path problem and then move on to its runtime analysis.

Here is a link to Seon McDonald‘s blog post for the lecture.