最短路径算法总结
前言
因为我在跟 Robert Sedgewick 的 Algorithms ，所以本文和前面几篇算法文章一样，都是基于这门课的梳理总结，并加以自己理解，这种学习方式其实效率还挺高的。
最短路径算法
最短路径问题有多种情况可以讨论
- 给定起点的最短路径问题
- 给定终点的最短路径问题
- 给定起点和终点的最短路径，也就是求任意两点之间的最短路径问题
本文只讨论 单源起点问题 ，有如下三个算法可以解决这个问题。
-
Dijkstra//适用于无负权重 -
Topological sort//适用于无环 -
Bellman-Ford//适用于无负环
Dijkstra
对于不含负权的有向图，这是目前已知的最快的单源最短路径算法
比较有意思的是，这个算法可以说就是 prim 算法。只不过就是比较的依据从 相对于整棵树 变成了 源点
所以，原理依旧是贪心算法，保证每一步都是最短。这里需要用优先队列来保存边。
步骤
- 初始化所有顶点到源点的路径为无限大
- 顶点插入优先队列
- 出队一个点
- 对所有与这个点相关联的边进行
放松操作 - 重复3
所谓的 放松 操作，就是一个比较的过程，若比原来的距离更短即进队。
代码
可以看到下面的代码基本上和 Prim 一致。
// @author Robert Sedgewick @author Kevin Wayne
public DijkstraSP(EdgeWeightedDigraph G, int s) {
for (DirectedEdge e : G.edges()) {
if (e.weight() < 0)
throw new IllegalArgumentException("edge " + e + " has negative weight");
}
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
// relax vertices in order of distance from s
pq = new IndexMinPQ<Double>(G.V());
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
for (DirectedEdge e : G.adj(v))
relax(e);
}
}
// relax edge e and update pq if changed
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
关于 Dijkstra 为什么不能含有负权值
可以想象一下，如果有一条负边在图中。 Dijkstra 维护的优先队列，每次都是取一条最小的边出来的，而这条负边，可以使这条路无限小。
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) { //若是负边的话每次都会减小，就会不断进入优先队列！！！
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
效率
Dijkstra 效率取决于优先队列的效率。二叉堆的话效率为 O(ElogV)
Topological sort
这种方法实现简单，效率也高，但只适用于无环图，权值可以为负。
步骤
- 初始化所有顶点到源点的路径为无限大
- 对顶点进行
拓扑排序 - 按照顶点顺序，对每条相关的边进行
放松
代码
Topological topological = new Topological(G);
if (!topological.hasOrder())
throw new IllegalArgumentException("Digraph is not acyclic.");
for (int v : topological.order()) {
for (DirectedEdge e : G.adj(v))
relax(e);
}
效率
Topological sort algorithm computes SPT in any edgeweightedDAG in time proportional to E + V
Bellman-Ford
对于无负环的图一种解决方案。最直接的实现是对所有边进行 V-1 次放松,但是效率太低。复杂度高达 O(V*E)
for (int i = 0; i < G.V(); i++)
for (int v = 0; v < G.V(); v++)
for (DirectedEdge e : G.adj(v))
relax(e);
优化
原始的版本总共进行 V-1 次放松，但其实，后面的很多次都是无效的放松，实际中不到 V-1 次就已经放松完全了。判断依据就是 distTo[v] 有无变化。
这种方法时间复杂度最坏情况依旧是 O(V*E) ，平均情况已经快很多了 O(E+V)
Reference
算法4th
维基百科
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
