最短路径算法总结

前言

因为我在跟Robert SedgewickAlgorithms,所以本文和前面几篇算法文章一样,都是基于这门课的梳理总结,并加以自己理解,这种学习方式其实效率还挺高的。

最短路径算法

最短路径问题有多种情况可以讨论

  • 给定起点的最短路径问题
  • 给定终点的最短路径问题
  • 给定起点和终点的最短路径,也就是求任意两点之间的最短路径问题

本文只讨论单源起点问题,有如下三个算法可以解决这个问题。

  • Dijkstra //适用于无负权重
  • Topological sort //适用于无环
  • Bellman-Ford //适用于无负环

Dijkstra

对于不含负权的有向图,这是目前已知的最快的单源最短路径算法

比较有意思的是,这个算法可以说就是prim算法。只不过就是比较的依据从相对于整棵树变成了源点

所以,原理依旧是贪心算法,保证每一步都是最短。这里需要用优先队列来保存边。

步骤

  1. 初始化所有顶点到源点的路径为无限大
  2. 顶点插入优先队列
  3. 出队一个点
  4. 对所有与这个点相关联的边进行放松操作
  5. 重复3

所谓的放松操作,就是一个比较的过程,若比原来的距离更短即进队。

代码

可以看到下面的代码基本上和Prim一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// @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维护的优先队列,每次都是取一条最小的边出来的,而这条负边,可以使这条路无限小。

1
2
3
4
5
6
7
8
9
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

这种方法实现简单,效率也高,但只适用于无环图,权值可以为负。

步骤

  1. 初始化所有顶点到源点的路径为无限大
  2. 对顶点进行拓扑排序
  3. 按照顶点顺序,对每条相关的边进行放松

代码

1
2
3
4
5
6
7
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 edgeweighted
DAG in time proportional to E + V

Bellman-Ford

对于无负环的图一种解决方案。最直接的实现是对所有边进行V-1次放松,但是效率太低。复杂度高达O(V*E)

1
2
3
4
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

维基百科