常见的最短路径算法有哪些？BFS、Dijkstra、Bellman-Ford、Floyd 怎么选？
简化版
按「无权/带权、有无负权、单源/多源」选：BFS 求无权图单源最短路，O(V+E)；Dijkstra 求非负权单源最短路，O((V+E)log V)；Bellman-Ford 能处理负权、还能检测负环，O(VE)；Floyd-Warshall 求所有点对（多源）最短路，O(V³)、能负权。核心口诀：无权用 BFS、非负权用 Dijkstra、有负权用 Bellman-Ford、多源用 Floyd。
详细版
| 算法 | 适用 | 负权 | 复杂度 | 类型 |
|---|---|---|---|---|
| BFS | 无权图 | — | O(V+E) | 单源 |
| Dijkstra | 带权、非负 | ❌ | O((V+E) log V) | 单源 |
| Bellman-Ford | 带权、可负 | ✅ 且能检测负环 | O(V·E) | 单源 |
| Floyd-Warshall | 带权、可负（无负环） | ✅ | O(V³) | 多源（所有点对） |
完整版教学
一、先分类：三个维度决定用哪个
选最短路算法，先问三个问题：
- 边有没有权重？ 无权 → BFS（每条边算 1 步，按层扩展第一次到达即最短）。
- 有没有负权边？ 有负权 → Dijkstra 失效，用 Bellman-Ford。
- 求单源还是所有点对？ 所有点对（多源）→ Floyd。
把这三个维度想清楚，选择就明确了。
二、BFS：无权图的最短路
无权图里「最短」= 边数最少。BFS 按层扩展，第一次到达某点时经过的边数一定最少，所以无权图最短路直接用 BFS，O(V+E)。别在无权图上用 Dijkstra——BFS 更简单更快。网格图、迷宫最少步数都是它。
三、Dijkstra：非负权单源
带权且边权非负时用 Dijkstra，贪心 + 优先队列，O((V+E) log V)。它的前提是「已确定点的距离不再变小」，只在非负权成立（详见 Dijkstra 专题）。这是最常用的带权最短路算法。
四、Bellman-Ford：能处理负权、能检测负环
当图有负权边时 Dijkstra 会算错，改用 Bellman-Ford：
- 做法：对所有边松弛 V-1 轮。为什么是 V-1 轮？因为任意两点间的最短路径最多经过 V-1 条边，每轮至少能「确定」一条边的贡献，V-1 轮后所有最短路都收敛。
- 检测负环：V-1 轮后再松弛一轮，如果还有距离能被更新，说明存在负权环（绕环一圈总距离变小，最短路无意义）。
- 复杂度 O(V·E)，比 Dijkstra 慢，但能处理负权。
- SPFA 是 Bellman-Ford 的队列优化版，平均更快但最坏仍 O(VE)。
五、Floyd-Warshall：所有点对（多源）
要求任意两点之间的最短距离（不只是从一个起点），用 Floyd：
- 动态规划：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])，三重循环，枚举「中转点 k」。 - k 必须在最外层循环——它表示「允许经过前 k 个点作为中转」，逐步放开。
- 复杂度 O(V³)、空间 O(V²)，能处理负权（但不能有负环）。
- 适合点数不多（几百）但要所有点对的场景，代码极简（五行三重循环）。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| BFS | 无权图单源最短路 |
| Dijkstra | 非负权单源最短路 |
| Bellman-Ford | 可处理负权并检测负环 |
| Floyd | 所有点对最短路 |
choose:
unweighted -> BFS
non-negative single source -> Dijkstra
negative edges -> Bellman-Ford
all pairs small V -> Floyd最短路选算法先问三件事：有没有权重、有没有负权、要单源还是多源。
- 误区：所有最短路都用 Dijkstra。 负权边会破坏 Dijkstra，所有点对问题用 Dijkstra 跑多次也不一定最合适。
- 误区：BFS 不能算最短路。 在无权图里，BFS 第一次到达节点就是最少边数路径。
- 误区：Bellman-Ford 只是更慢的 Dijkstra。 它能处理负权边，还能检测从源点可达的负环。
- 追问：Floyd 适合什么规模？ O(V³) 时间、O(V²) 空间，适合点数较小且需要任意两点最短路。
- 追问：负环意味着什么？ 若可达负环存在，最短路可被无限降低，某些点的最短距离没有定义。
- 追问：边权全为 1 该用什么？ 用 BFS 即可，没必要上 Dijkstra。
七、加强记忆
最短路选择看三维度：无权 → BFS（O(V+E)，按层第一次到达即最短）；非负权单源 → Dijkstra（O((V+E)log V)，贪心+堆）；有负权单源 → Bellman-Ford（松弛 V-1 轮、再松弛一轮可检测负环，O(VE)；SPFA 是其队列优化）；所有点对（多源）→ Floyd（DP，中转点 k 在最外层，O(V³)，可负权无负环）。口诀:无权 BFS、非负 Dijkstra、负权 Bellman-Ford、多源 Floyd。