最短路
题单介绍
---
[**参考**此篇博文](https://www.luogu.com.cn/blog/FrozaFerrari/xue-tu-lun-ni-zhen-di-liao-xie-zui-duan-lu-ma-post)
[**Johnson** 算法](https://www.luogu.com.cn/article/eew64dlc)
### 1.最短路基础算法：BFS、DFS、Floyd、Dijkstra、Bellman-Ford、SPFA、Johnson
- [P1359 租用游艇](https://www.luogu.com.cn/problem/P1359)：Floyd、Dijkstra、Bellman-Ford、SPFA
- [P1629 邮递员送信](https://www.luogu.com.cn/problem/P1629)：Floyd、Dijkstra、Bellman-Ford、SPFA
- [P1938 \[USACO09NOV\]Job Hunt S](https://www.luogu.com.cn/problem/P1938)：Dijkstra、Bellman-Ford、SPFA
- [P1457 \[USACO2.1\]城堡 The Castle](https://www.luogu.com.cn/problem/P1457)：BFS、DFS、Dijkstra
- **[P1119 灾后重建](https://www.luogu.com.cn/problem/P1119)：Floyd**
- [P1144 最短路计数](https://www.luogu.com.cn/problem/P1144)：BFS、Dijkstra、SPFA
- **[P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371)：Dijkstra、SPFA**
- **[P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)：Dijkstra**
- [P3956 棋盘](https://www.luogu.com.cn/problem/P3956)：DFS、Dijkstra
- **[P3385 【模板】负环](https://www.luogu.com.cn/problem/P3385)：Bellman-ford、SPFA**
- [P5905 【模板】Johnson 全源最短路](https://www.luogu.com.cn/problem/P5905)
### 2.最短路引申出的问题：次短路、k短路
- [P2324 [SCOI2005]骑士精神](https://www.luogu.com.cn/problem/P2324)：A*
- [P1491 集合位置 ](https://www.luogu.com.cn/problem/P1491)：次短路
- **[P2483 【模板】k短路 / [SDOI2010]魔法猪学院](https://www.luogu.com.cn/problem/P2483)：k短路**
---
最近更新：加入了 [P1629 邮递员送信](https://www.luogu.com.cn/problem/P1629)
---