1. Shortest Paths: BFS and Dijkstra

Getting Started with Competitive Programming

(an NPTEL course)

Module 1. Shortest Paths BFS and 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 the code shown in these videos at these links:

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>