首页 > 代码库 > 更多和最短路径相关的问题
更多和最短路径相关的问题
-------------------siwuxie095
更多和最短路径相关的问题
在《算法导论》中,关于 Dijkstra 算法和 Bellman-Ford 算法,
通常都会将 distTo[i] 初始化为正无穷,使得松弛操作的代码有
了一定的简化,将 if 条件中复杂的两个判断改为对 distTo[i] 的
一个判断
但在真正的实现中并没有这么做,关键在于:在程序中是无法
写正无穷的
所以,通常是使用一个非常大的数来代替正无穷,即 如果可以
找到一个非常大的数,且它比图中任意一个路径的长度都要大,
那么在图中就可以把这个数当做正无穷来进行处理
可是,如果找不到一个非常大的数,依然可以使用原来复杂的
判断。虽然多了一个判断,但效率损耗并没有那么明显,整个
逻辑也是非常清晰的
在实现 Bellman-Ford 算法时,进行了 (V-1)*E 次的松弛操作,
但对于一张很小的图来说,其实并不需要那么多松弛操作,而
对于一张很大的图来说,优化余地更高
所以,Bellman-Ford 算法有一个非常标准的优化形式,即 利
用队列作为辅助数据结构进行优化,这个优化算法通常被称为
queue-based Bellman-Ford 算法,也被称为 SPFA 算法
对于该优化,虽然在最差的情况下,时间复杂度依然是 O(V*E) ,
但在很多情况下,都能有非常显著的优化成果
单源最短路径算法总结
|
条件 |
类型 |
时间复杂度 |
Dijkstra |
无负权边 |
有向无向图均可 |
O(E*logV) |
Bellman-Ford |
无负权环 |
有向图 |
O(V*E) |
拓扑排序 |
有向无环图(DAG) |
有向图 |
O(V+E) |
对于有向无环图(DAG)来说,单源最短路径算法有更好的
处理方案,即 可以利用拓扑排序在 O(V+E) 的时间内解决单
源最短路径问题
单源最短路径算法是求出了一张图的最短路径树,可以非常
容易的找到某一起始顶点到其它所有顶点的最短路径,但是
在调用算法之前需要指定起始顶点
而所有点对最短路径算法,通过一系列的预处理之后,可以
直接回答任何两个点之间的最短路径
显然,执行 V 次 Dijkstra 算法和 Bellman-Ford 算法,其
实也就求出了所有点对的最短路径
不过,对于所有点对最短路径算法,有一个优化算法,称之
为 Floyd 算法,它可以处理无负权环的图,且时间复杂度为
O(V^3),它比执行 V 次 Dijkstra 算法和 Bellman-Ford 算
法效率更高
「前提:图中不能有负权环,但能有负权边」
最长路径算法,是一个看起来和最短路径算法正好相反的问
题,它的基本要求如下:
(1)最长路径问题不能有正权环
(2)无权图的最长路径问题是指数级难度的
(3)对于有权图,不能使用 Dijkstra 算法求最长路径问题
(4)可以使用 Bellman-Ford 算法求单源最长路径问题
(5)可以使用拓扑排序求有向无环图的单源最长路径问题
(6)可以使用 Floyd 算法求所有点对最长路径问题
【made by siwuxie095】
更多和最短路径相关的问题