最短路径算法总结

前言

因为我在跟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 edgeweighted
DAG 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

维基百科

原文地址：http://threezj.com/2016/05/02/最短路径算法总结/