最短路总结
单源最短路
| Bellman-Ford | SPFA | Dijkstra | H-Dijkstra | |
|---|---|---|---|---|
| 思路 | 遍历全边，直到不变 | 宽搜渐进，入队再更 | 找最近点，更新邻点，找完不再用 | 取负入队，大根堆找点，其余相同 |
| 负边权 | 能 | 能 | 否 | 否 |
| 判负环 | 能 | 能 | 否 | 否 |
| 时间复杂度 | O(nm) | O(km~nm) | O(m+n^2) | O(mlogn) |
| 适用于 | 为什么不用SPFA | 稀疏图 | 还是优化吧 | 非负边权 |
| 链接 |
基本上是H-Dijkstra>Dijkstra>SPFA>Bell-Ford
多源最短路
| Floyed | H-Dijkstra | Johnson | |
|---|---|---|---|
| 思路 | 动规三重循环 | n次Dijkstra | 虚拟结点，映射非负，H-Dijkstra |
| 负边权 | 能 | 否 | 能 |
| 判负环 | 能 | 否 | 能 |
| 时间复杂度 | O(n^3) | O(nmlogn) | O(nm+nmlogn) |
| 适用于 | 稠密图 | 非负边权 | 稀疏图 |
| 链接 |