mod06lec32 - SSSP and Modified Dijkstra

In this module, we introduce the shortest path problem, and specifically focus on the SSSP (i.e, single-source shortest path problem). We deal with the cases of uniform edge weights (via BFS), non-negative edge weights (via Dijkstra’s algorithm), negative edge weights with no negative cycles (via modified Dijkstra’s algorithm).

We implement Dijkstra’s algorithm in the context of a problem called Sending Email, which is available from here:

To examine the problem of printing shortest paths, you might want to practice with this Codeforces problem:

You can find pointers to resources that describe the analysis of these algorithms, and provide details about the proofs of correctness, from this page on the course website:

You can find the code described in the lecture at this repository:

If you are watching this during an active run of the course, you can join the discord community for the course using this link:

The course website can be found at:

[jayeshsharma]

everybody gangsta till nptel exam comes close