因为我在跟 Robert Sedgewick
的 Algorithms
,所以本文和前面几篇算法文章一样,都是基于这门课的梳理总结,并加以自己理解,这种学习方式其实效率还挺高的。
最短路径问题有多种情况可以讨论
本文只讨论 单源起点问题
,有如下三个算法可以解决这个问题。
Dijkstra
//适用于无负权重 Topological sort
//适用于无环 Bellman-Ford
//适用于无负环 对于不含负权的有向图,这是目前已知的最快的单源最短路径算法
比较有意思的是,这个算法可以说就是 prim
算法。只不过就是比较的依据从 相对于整棵树
变成了 源点
所以,原理依旧是贪心算法,保证每一步都是最短。这里需要用优先队列来保存边。
放松
操作 所谓的 放松
操作,就是一个比较的过程,若比原来的距离更短即进队。
可以看到下面的代码基本上和 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 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
对于无负环的图一种解决方案。最直接的实现是对所有边进行 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)
算法4th
维基百科