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 370 / 392 1000
Delete edge 275 / 308 1100
3D path 137 / 149 1100
Number of shortest paths 249 / 265 1200
Double edge 135 / 196 1300
Second shortest path 151 / 177 1400
Bye bye maximum edge 170 / 189 1500
Boardgame 119 / 136 1500
Teleport 82 / 84 1500
? 65 / 90 1600
Math 93 / 122 1700
Festival 3 95 / 104 1700
Arbitrage 73 / 81 1700
Festival 4 69 / 72 1800
String construction 30 / 38 1800
Elevator 66 / 81 2000
Fortress defense 2 / 3 2200