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 424 / 453 1000
Delete edge 315 / 355 1100
3D path 160 / 171 1100
Number of shortest paths 291 / 307 1200
Double edge 145 / 214 1300
Second shortest path 181 / 214 1400
Bye bye maximum edge 198 / 220 1500
Boardgame 131 / 149 1500
Teleport 97 / 101 1500
? 70 / 98 1600
Math 102 / 133 1700
Festival 3 100 / 111 1700
Arbitrage 84 / 99 1700
Festival 4 75 / 78 1800
String construction 36 / 46 1800
Elevator 70 / 86 2000
Fortress defense 6 / 11 2200