Module Shortest path

Shortest path

**Frequency: 8/10** In unweighted graph, we can use BFS to find shortest path. This module covers problems involve in finding shortest path on weighted graph, as well as other applications of these shortest path algorithms in some non-graph-related problems.

Resources

- [CP Algorithms: Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) - [CP Algorithms: Bellman-Ford](https://cp-algorithms.com/graph/bellman_ford.html) - [CP Algorithms: Floyd-Warshall Algorithm](https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html)

Problems

Shortest path 265 / 280 1000
Delete edge 196 / 230 1100
3D path 95 / 102 1100
Number of shortest paths 179 / 189 1200
Double edge 97 / 142 1300
Second shortest path 102 / 119 1400
Bye bye maximum edge 118 / 133 1500
Boardgame 83 / 97 1500
Teleport 56 / 60 1500
? 50 / 67 1600
Math 71 / 83 1700
Festival 3 76 / 82 1700
Arbitrage 56 / 63 1700
Festival 4 57 / 60 1800
String construction 23 / 30 1800
Elevator 55 / 63 2000