几种最短路算法对比
众所周知，关于 SPFA，它死了。
几种最短路算法对比：
| 名称 | 时间复杂度 | 优点 | 缺点 | 使用情况 |
|---|---|---|---|---|
| Floyd-Warshall | 仅有的多源最短路径算法（即跑一遍 Floyd 能求出每个点到其它点的距离）、其核心代码就 5 行 | 时间复杂度过高 | 多源最短路、对时间复杂度没要求 | |
| Dijkstra（朴素） | 编码复杂度非常高、不能处理负权，即边的权值是负数的情况（跟它用的是贪心有关） | |||
| Dijkstra（优先队列优化） | 最快了 | 同朴素版 | 对时间复杂度有要求 | |
| Bellman-Ford | 跟 Dijkstra 时间复杂度互有胜负，有时还是 Dijkstra 赢了 | 稀疏图 | ||
| SPFA | 最坏也是 |
优化版 Bellman-Ford | 众所周知，它死了 | 稀疏图 |
| Jonson | 仅有的全源最短路算法，结合了 Dijksra 和 SPFA 的优势 | 不怎么常用…… | ||
| BFS | 思路简单 | 只能处理等权图或无权图 | 等权图 / 无权图 |
注：
- 标题: 几种最短路算法对比
- 作者: Leo2011
- 创建于 : 2024-01-29 22:41:55
- 更新于 : 2024-08-31 11:34:24
- 链接: https://leo2011.eu.org/2024/01/29/ji-chong-zui-duan-lu-suan-fa-dui-bi/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
评论