本文主要是介绍单源最短路径算法小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这里就不写具体算法了，只将他们的时间复杂度、适用范围、代码复杂程度简单做个比较
待搜索的图都指有向图(无向图类似)。储存方式均为邻接表
一、广度优先搜索(BFS)
时间复杂度：O(V+E)，效率很高
适用范围：(很窄)仅适于无权边的图。即每条边长度都为1的情况
代码复杂程度：一般，需队列
二、Bellman-Ford
时间复杂度：O(VE)，效率一般
适用范围：(很广)允许存在负权边，能够判断图中是否存在从源点可到达的负权环路
代码复杂程度：较易
三、有向无环图算法
时间复杂度：O(V+E)，效率很高
适用范围：(很窄)仅适于有向无环图
代码复杂程度：一般，需拓扑排序
四、Dijkstra
适用范围：(一般)不允许存在负权边
这个算法复杂度取决于"取最小"(Extract-min)操作使用的算法
顺序检测所有点决定最小值 O(V^2) 一般
使用Binary-Heap(优先队列) O((V+E)lgV) 较复杂
五、SPFA (Shortest Path Faster Algorithm)
时间复杂度：O(kE)，k为一较小常量。效率很高
适用范围：(较广)，允许存在负权边，但不允许负权环路
代码复杂程度：较易，需队列
这个算法可算是 Bellman-Ford 的优化版本，去除冗余的Relax操作，效率有很大提升
有些奇怪的是这个算法在《算法导论》和 Wikipedia上竟然都没有介绍，而只在国内的OI相关网站论坛才发现的解释，大多还不是很全面。从适用范围和代码复杂程度来看绝对是一个值得推荐的算法(比熟知的Dijkstra 都要好)，效率上也不比使用 Heap 优化的 Dijkstra低，一般来说甚至还要高(还有待更多题目实践验证)。即使寻找所有顶点对之间的最短路径这个算法也是值得考虑的(对每个顶点运行一次SPFA)。
转载自： 蓬莱山辉夜的博客
转载自： 蓬莱山辉夜的博客
这篇关于单源最短路径算法小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
