By Zhang, Cheng

更新日期:

文章目录
  1. 1. 最短路径
    1. 1.1. Dijkstra算法
      1. 1.1.1. 算法描述
      2. 1.1.2. 伪代码
      3. 1.1.3. 举例
      4. 1.1.4. 讨论
    2. 1.2. Bellman-Ford算法
      1. 1.2.1. 算法描述
      2. 1.2.2. 伪代码
      3. 1.2.3. 举例
    3. 1.3. Floyd-Warshall算法

最短路径

除了遍历以外，对图最常见的操作就是求点到点的最短路径了。在日常生活中，这个问题也十分常见，比如我从宿舍出发，要去游泳馆，那么我得计划一条去游泳馆最近的路线，宿舍和游泳池可以看作图的节点，到游泳池的路上经过个个节点的路程长度看作是边的权值。在地图中，这个应用更为广泛，一个城市到其他城市的最短距离。与此类似的还有各个城市之间的最短路径。

由此我们可以将最短路径归纳成两类问题：单源最短路径(single source shortest path problem)和多源最短路径(all pairs shortest path problem)。它们都有成熟的算法，单元最短路径有Dijkstra算法和Bellman-Ford算法，而多源最短路径有Floyd-Warshall算法。

Dijkstra算法

算法描述

Dijkstra算法的思想和Prim算法的思想很像，都是构建两个集合，一个集合用来存放已经找到从s出发的最短路径的节点集合，另一个是还没找到最短路径的节点集合。每次进行查找的时候都将还没有加到集合的节点添加进集合，并更新从源点到其他点的路径直到所有节点都被添加到集合中。

它的证明可以通过反证法来证，简单点说就是如果我添加的节点不是最短的话，总能找到更短的，这与一开始的假设是矛盾的。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
Dijkstra(source)
Input: source //源节点
	bool isFound[nodes];//用bool数组作为找到的最短路径集合
	double distance[nodes];//表示其他各点到源点的距离
	for each i in nodes //遍历每个节点
		//Step1: 在未找到最短路径的集合中找出到源点最短距离的点
		minVertex = getMin();
		isFound[minVertex] = true;
		//Step2: 更新未加入集合的点到源点的最短距离
		update distance；
	End	
End

可以看到Dijkstra的主要由两个操作来决定，一个是找到这个最短距离的点和边，另一个是更新记录最短距离的数组。我们可以通过下表来总结一下:

实现的数据结构 找最短距离的点和边(1) 更新最短距离的数组(2) V*(1)+(V+E)*(2)
邻接矩阵 O(V) O(1) O(V^2)
二叉堆 O(logV) O(logV) O((V+E)logV)
d堆 O( dlogV/logd ) O(logV/logd) O( (dV+E)logV/logd )
斐波那契堆 O(logV) O(1)(摊销) O(VlogV+E)

举例

讨论

就此我们已经讲完了Dijkstra算法，也知道了它的适用范围是每条边都为非负权值。那么这时候有人问了，如果我对每条边都加一个正数，使得边集里面没有复权边，这时候Dijkstra算法还能使用吗？这个问题要从等价问题来思考，如果给每条边都增加一个正数，看上去这是件公平的事，其实不然。对某些由多条边组成的路径来说，整个路径的权值不只增加了这个一个正数，而是几倍的正数，原来这条路径在权值上还有优势的，现在增加了几倍的正数，反而变为劣势了，所以这是件不等价的转化。那么非要进行等价转化，我觉得是每条边都乘以一个正数，这应该是等价的转化。

Bellman-Ford算法

算法描述

Bellman-Ford算法的思想在于从源点逐步访问到其他节点来缩短到达目标节点的距离。

关键在于需要构造一个记录最短路径的序列dist(k)[i]，表示从源点出发经过k个节点到达i的最短距离。每次在第k次迭代时，进行判断dist(k)[i]与dist(k-1)[j]+edge(j,i)，其中j=1…nodes。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Bellman-Ford(source)
Input: source //源点
	distance[nodes];//记录当前迭代下源点到其他节点i的最短距离
	for i in nodes.size: //经过i个节点
		for e in edge: //遍历每条边
			start = e.start;
			end = e.end;
			if(distance[end] > distance[start]+edge)//松弛计算
				distance[end] = distance[start]+edge;
		End
	End
	//检查图中是否存在负环，只需要再进行次上面的计算，如果权值变小，则存在负环
	for e in edge: //遍历每条边
		start = e.start;
		end = e.end;
		if(distance[end] > distance[start]+edge)//松弛计算
			output("存在负环！");
	End
End

需要经过V-1个节点，每次遍历E条边，所以复杂度是O(EV)。

BellmanFord对负权边也是有效的，同时也能检测出负环的存在，如果负环存在，那么该图没有最短路径，因为总可以走一次负环使得求得的最短路径的代价更小。

那么这里有个问题，BellmanFord是求单源最短路径，那么如果我在每个顶点都求次BF算法，是不是就等价于下面的Floyd-Warshall算法了呢？

答案是不能，因为BellmanFord的算法复杂度是O(VE)，则对每个节点都求次BF算法的复杂度是O(EV^2)，与Floyd-Warshall算法的复杂度O(V^3)不同。

举例

经过k个点 distk[2] distk[3] distk[4] distk[5] distk[6] distk[7]
0 6 ∞ 5 5 ∞ ∞
1 3 5 5 3 4 ∞
2 1 2 5 3 4 7
3 1 0 5 3 4 5
4 1 0 5 3 4 3
5 1 0 5 3 4 3

它与Dijkstra算法的区别就在于：

  1. Dijkstra算法在求解的过程中，源点s到其他节点最短距离求出来就不会再改变了，每次更新的最短距离都是s到未加入集合的节点的最短距离。
  2. Bellman-Ford算法在每次迭代过程中，最短距离都是会更新的，因为需要计算如果加入这个点对最短路径的影响，所以只有当迭代全部结束时才能知道源点到其他各点的最短路径。

Floyd-Warshall算法

上面的两个算法都是针对单源的问题，Floyd算法是针对多源问题。代码看上去很直观，运用的思想是动态规划。针对一个中间点，如果源点到目标点的距离大于源点到中间点的距离加上中间点到目标点的距离，那么就更新距离。

1
2
3
4
5
6
7
8
9
10
11
12
Floyd-Warshall()
	distance[nodes][nodes];//记录各点之间的最短距离
	for(int middle=0;middle<nodes;middle++)
		for(int source=0;source<nodes;source++)
			for(int end=0;end<nodes;end++)
				if(distance[source][end]>distance[source][middle]+distance[middle][end])
					distance[source][end] = distance[source][middle]+distance[middle][end];
			End
		End
	End
	output distance;
End

很直观这个方法的空间复杂度是O(V^2)，时间复杂度是O(V^3)，当然图中不能有负权边。

文章目录
  1. 1. 最短路径
    1. 1.1. Dijkstra算法
      1. 1.1.1. 算法描述
      2. 1.1.2. 伪代码
      3. 1.1.3. 举例
      4. 1.1.4. 讨论
    2. 1.2. Bellman-Ford算法
      1. 1.2.1. 算法描述
      2. 1.2.2. 伪代码
      3. 1.2.3. 举例
    3. 1.3. Floyd-Warshall算法