Getting Started with Competitive Programming
(an NPTEL course)
Week 6. Shortest Path
In this week, we look at shortest path algorithms in various scenarios - for unweighted graphs (BFS), graphs with positive edge weights (Dijkstra), graphs with positive and negative edge weights but no negative cycles (modified Dijkstra), and finally the most general case (Bellman-Ford). We also look at the all-pairs shortest path problem (APSP; Floyd-Warshall).