首页 > 代码库 > 更多和最短路径相关的问题

更多和最短路径相关的问题

-------------------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】

更多和最短路径相关的问题