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 275 / 292 1000
Delete edge 203 / 237 1100
3D path 98 / 105 1100
Number of shortest paths 187 / 197 1200
Double edge 102 / 147 1300
Second shortest path 105 / 122 1400
Bye bye maximum edge 123 / 138 1500
Boardgame 86 / 100 1500
Teleport 60 / 63 1500
? 52 / 70 1600
Math 72 / 84 1700
Festival 3 78 / 86 1700
Arbitrage 58 / 65 1700
Festival 4 59 / 62 1800
String construction 23 / 30 1800
Elevator 56 / 64 2000