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