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

-------------------siwuxie095

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

在《算法导论》中，关于 Dijkstra 算法和 Bellman-Ford 算法，

通常都会将 distTo[i] 初始化为正无穷，使得松弛操作的代码有

了一定的简化，将 if 条件中复杂的两个判断改为对 distTo[i] 的

一个判断

但在真正的实现中并没有这么做，关键在于：在程序中是无法

写正无穷的

所以，通常是使用一个非常大的数来代替正无穷，即 如果可以

找到一个非常大的数，且它比图中任意一个路径的长度都要大，

那么在图中就可以把这个数当做正无穷来进行处理

可是，如果找不到一个非常大的数，依然可以使用原来复杂的

判断。虽然多了一个判断，但效率损耗并没有那么明显，整个

逻辑也是非常清晰的

在实现 Bellman-Ford 算法时，进行了 (V-1)*E 次的松弛操作，

但对于一张很小的图来说，其实并不需要那么多松弛操作，而

对于一张很大的图来说，优化余地更高

所以，Bellman-Ford 算法有一个非常标准的优化形式，即 利

用队列作为辅助数据结构进行优化，这个优化算法通常被称为

queue-based Bellman-Ford 算法，也被称为 SPFA 算法

对于该优化，虽然在最差的情况下，时间复杂度依然是 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】

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

原文：http://www.cnblogs.com/siwuxie095/p/7135603.html