Shortest Path

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).

Class Plan & Materials

A. Prerequisites
1. Shortest Paths: BFS and Dijkstra
2. Working with Negative Cycles
3. All-Pairs Shortest Paths
Z. Extras