Code

最短路径

分析图论中各类最短路径问题的算法设计，给出 Bellman-Ford，Dijkstra，SPFA 和 Floyd-Warshall 算法描述与代码。

问题分类

  • 最短路径问题中，给出的是一个带权有向图G=（V，E），无向图可以认为是双向的有向图。加权函数w：E->R为从边到实型权值的映射，路径p=的权指其组成边的所有权值之和。定义从u到v的最短路径为所有从u到v的路径中权值最小的路径，若不存在从u到v的路径则权值为正无穷。
  • 单源最短路径及其变体
    • 单源最短路径：已知图G=（V，E），求从V中某个给定源点s到V中的其他所有顶点的最短路径。
    • 单终点最短路径：将E反向，转化为单源最短路径。
    • 单对顶点最短路径问题：对于某对给定顶点（u，v），找出u到v的最短路径。通常解决办法为找到u的单源最短路径。
    • 每对顶点间最短路径问题：对每个顶点求单源最短路径，或采用Floyd-Warshall。

算法设计

可能情况分析

  • 最短路径的算法很明显依赖于最优子结构性质：假设当前求出了（u，v）的最短路径p，并且p上有两个中间节点（u’，v’），则u’到v’的最短路径一定是路径p上从u’到v’的路径。即：最短路径的子路径是最短路径。证明采用反证法。
  • 假设你有两个传送门u和v，穿过一个传送门就可以到达另一个传送门的位置，并且从u到v会倒退时间t1,从v到u会前进时间t2，t1>t2。此时你就可以无止境的穿越到过去的任意一个时间点，也就是说从u到v和从v到u均有路径，并且路径权值（从u到v和从v到u穿过传送门所需的时间之和t1+t2）是负数。此时形成了负权环，称其为负权回路（回路上的权值之和为负数，而不一定每条权值均为负数），负权回路上的最短路径是没有意义的，只要不停在u和v两点间穿梭，就可以让权值变为负无穷。但是，假如t2>t1，此时只能任意穿越到未来，也就是说当负权路径存在但不存在负权回路时，不影响最短路径算法的求解。
  • 回路问题：图G=（V，E）的任意一条无环路径至多包含|V|个不同的顶点，以及|V|-1条边。最短路径一定不能包含负权回路，同样也不能包含正权回路：假设最短路径上存在正权回路，则将该回路从路径中移除后，路径权值减小，但仍满足u->v。

    数据的记录和操作的实现

  • 通常情况下最短路径的目的不仅在于其路径权值大小，还在于路径自身如何行走。最短路径的记录方法可以联想到链式结构，采用前趋数组p[v]记录到达v的前一个顶点。打印路径时，从v开始逆向打印，直到遇到源点s。
  • 松弛技术：对每个顶点v，均设置一个属性d[v]，在求解过程中描述从源点s到v的最短路径上权值的上界，求解结束后就是最短路径的权值，称为最短路径估计。初始化d[v]全部为正无穷，p[v]全部为nil（空）。d[s]=0（源点到自身的距离为0）。在求最短路径过程中，总是不停使用一种替换策略来寻求更小权值：当迄今为止找到的d[v]（s到v的权值）小于d[u]+w(u,v)时，就应当松弛边（u，v）。因此松弛操作要测试是否可以通过u来更新迄今为止所找到的v的最短路径。每次松弛操作可以减小最短路径估计，并更新前缀p[v]。下面的伪代码给出了对边（u，v）的松弛操作。
1
2
3
4
RELAX(u, v, w)
	if d[v] > d[u] + w(u,v)
	   then d[v] <- d[u] + w(u,v)
	   		p[v] = u
  • 正确性
    • 三角不等式：当最短路径求出后，对任意边(u,v)属于E，有d[v] <= d[u] + w(u,v)。
    • 上界性质：在求解最短路径过程中，对任意顶点v属于V，都有d[v] >= MinPath(s,v)，这里用MinPath(s,v)代表从s到v实际的最短路径。一旦d[v]到达MinPath(s,v)，就不再改变。
    • 无路径性质：若从s到v不存在路径，则d[v] = MinPath(s,v) = 正无穷。
    • 收敛性质：若s ~> u -> v是图G中从s到u和v的最短路径，并且在松弛边（u，v）之前有d[u] = MinPath(s,u)，松弛操作后都有d[v] = MinPath(s,v)。
    • 前趋子图性质：对于所有的v，一旦d[v] = MinPath(s,v)，则前趋子图就是一个以s为根的最短路径树。

单源最短路径

Bellman-Ford

  • 经过算法分析可知，松弛操作是求解最短路径的核心。需要解决的是如何通过多次松弛操作得到最短路径。
  • 在算法分析的第一步，得到最短路径问题满足最优子结构，因此整个求解的过程是不断完善的，也就是在已经求解出的d[u]基础上更新更多的结点。因此思路可以按层次或按步骤展开。
  • Bellman-Ford算法：初始化在算法分析中，伪代码如下
1
2
3
4
5
6
7
8
9
BELLMAN_FORD(G, w, s)
    INITIALIZE_SINGLE_SOURCE(G,s)
    for i from 1 to |V(G)|-1:
        for each edge(u,v) in E(G):
            RELAX(u, v, w)
    for each edge(u,v) in E(G):
        if d[v] > d[u] + w(u,v):
            return FALSE
    return TRUE

执行过程：第一行初始化d和p数组，第2~4行，对每条边都进行松弛操作，并重复该过程|V(G)|-1次，结束后即可得最短路径。5~7行，判断得到的最短路径是否满足要求，即判断图中是否存在负权回路，存在则返回false，否则返回true。

  • 在第2~4行的操作中，共对所有边重复松弛了|V|-1次。理解如下：在第一次对所有边 的松弛中，得到了源点到所有最短路径长度为1的点的最短路径，也就是说，如果s~>v的实际最短路径长度仅为一条边，则经过第一次循环的松弛操作，该最短路径就已经确定。第二次循环，在第一次循环已经确定的最短路基础上，可以得到源点到所有最短路径长度为两条边的点的最短路径。算法分析中已经得到，图G=（V，E）的任意无环路径最多只能有|V|-1条边，因此经过|V|-1次循环后，可以得到源点到所有顶点的最短路径。
  • 在第5~7行的操作中，如果发现某条边还可以继续松弛，意味着2~4行求出的最短路径还可以更短，这就违背了算法分析中的收敛性质。因此存在负权环，返回FALSE。
  • BELLMAN-FORD算法可以求解图中存在负权的情况，对负权环的存在可以报错。

Dijkstra算法

  • Bellman-Ford算法的时间复杂度为O(VE)，Dijkstra算法可以将时间复杂度提升到O(V^2)，利用二叉最小堆实现优先队列进行维护则可以提升到O((V+E)lgV)，利用斐波那契堆可以将运行时间提升到O(VlgV+E)。
  • 回顾求解最小生成树的Prim算法，在初始化阶段设置了一个集合S’只含任意一个结点，用来标记已在最小生成树中的结点，每次从顶点集合V-S’中取出一个顶点，该顶点满足：在所有V-S’的顶点中，该顶点到S’中的顶点距离最小。重复这个过程|V|-1次就可以得到最小生成树。参照这种思想设计Dijkstra算法。
  • Bellman-Ford算法可以理解为按层次展开。由Prim算法，推测Dijkstra则是按集合划分的“最短路径子图”（自己乱起的名字），初始状态该子图G’只包含源点s，每个计算周期后，向该集合增加一个结点u，并且源点到这个集合的所有结点的最短路径均已求出。这样重复n-1次后即可求出所有结点的最短路径。
  • 如何实现上述推测：
    上述操作的可行性，可以通过数学归纳法证明：（1）初始化状态下，s到s的最短路径为nil。（2）假设在第k次操作后，G’中含有k+1个结点，除s外还有k个结点，且s到这k个结点的最短路径已经求出。在第k+1次操作中，如何求出应该加入到G’的下一个结点？考虑到Bellman-Ford算法对所有边的|V|-1次松弛操作，当对所有边进行第一次松弛操作后，就已经求出了到源点s最短路径仅含1条边的点集。因此在Dijkstra算法的第k次操作中，利用加入的第k个结点对剩下的结点中与其直接相连的结点进行松弛操作，就可以得到基于已求出最短路径的前k个结点的最短路径估计。也就是，此时V-G’中的顶点的最短路径估计，都已经完全利用了前k个结点的最短路径（在第i次操作中利用了加入的第i个结点）。因此V-G’中顶点最短路径估计最小的顶点，就是k+1次操作需要加入的结点。
  • 伪代码：
1
2
3
4
5
6
7
8
9
DIJKSTRA(G, w, s)
	INITIALIZE_SINGLE_SOURCE(G,s)
	S <- Nil
	Q <- V[G]
	while Q != Nil:		# Q为剩余未加入G’的顶点，Q=V-G’
		  u <- EXTRACT-MIN(Q)	# 选出Q中最短路径估计最小的顶点，用优先队列维护
		  S <- S | {u}
		  for each vertex v in Adj[u]:	# 与u有直接边相连的顶点
		  	  RELAX(u, v, w)
  • 要注意的是，Dijkstra算法的正确性是依赖于：更长的最短路径是从短的最短路径发展而来的，例如s~>v的路径是从s~>u维护出来的，存在的问题在于短的最短路径一旦确定就不能修改。而Dijkstra总是选择当前能连到的V-G’中最近的顶点插入集合G’中，即使用了贪心策略。想象一个图：一共三个顶点1、2、3，1到2距离为3，1到3距离为4，而3到2距离为-2。在Dijkstra算法运算后，1到2、3的距离分别为3和4，而实际上1到2的距离应该为2。尽管在G’中有了1、2后，插入3会重新松弛与3相连的边，但Dijkstra不允许对已经在G’中的结点松弛（如果松弛成功，此前已经确定的最短路径都会发生改变，则算法是错误的）。因此Dijkstra不能处理存在负权边的图。

SPFA

由Bellman-Ford和Dijkstra衍生的Priority Queue-Based Bellman-Ford，国内ACM称为SPFA，与Dijkstra区别在于一个结点能否多次入队。可以处理负权边，适合临接表存储，是Bellman-Ford的优化。又可以看做是BFS的多次入队算法。

  • Bellman-Ford无论是否已求出最短路径，一定要重复松弛所有边|V|-1次，SPFA将松弛的次数减少。Dijkstra中，一个结点一旦进入了“最短路径子图”就无法再修改其路径和权值，而在SPFA中，并不设置这样一个“写保护”的集合，仅有一个表示最短路径估计的d数组。
  • 算法流程：初始化相同，d[s]=0，设置一个队列，将源点s入队。每次从队中取出一个结点u，并用该结点松弛和其直接相连的所有边，如果发现有一条边（u，v）在松弛操作后更新，则很有可能其它顶点因为d[v]的更新而产生新的最短路径，所以要将v入队。以此循环往复，直到队列为空，整个图没有可以继续松弛的边，则SPFA结束。算法执行时需要设置一个inq数组,inq[v]表示v当前是否在队列中，以防止一个结点在队列中同时出现多次。对于图中存在负权环的情况，可以依据结点入队的次数进行判断。Bellman-Ford对所有边松弛|V|-1次后就能求得最短路径，因此如果某个顶点入队了|V|次，就意味着出现了负权环。
  • 伪代码
1
2
3
4
5
6
7
8
9
10
11
SPFA(G, w, s)
	INITIALIZE_SINGLE_SOURCE(G,s)
	Queue <- s
	while Queue is not nil:
		u <- Queue
		if InQueueCount(u) > V(G):
		   return FALSE
		for each vertex v in Adj[u]:
			if RELAX(u, v, w) and not inq[v]:
			   Queue <- v
	return TRUE

优化

Dijkstra算法优化

  • 二叉堆实现的优先队列优化
    Dijkstra算法每次要从V-G’中选取最短路径估计最短的结点加入G’，因此可以利用优先队列对顶点集V维护，类似Prim的二叉堆维护。可以直接copy最小生成树中Prim的二叉堆部分代码。
  • 斐波那契堆实现的Dijkstra优化

    TODO

SPFA算法优化

  • SLF：Small Label First，假设要加入的结点是j，队首元素为i，若d[j]<d[i]则将j插入队首，否则插入队尾。速度可提升15～20%。
  • LLL：Large Label Last，假设队首元素为i，队列中的所有结点的d平均值为x，若d[i]>x，则将i插入队尾，查找下一元素，直到找到某一个i使得d[i]<=x，则将i出队进行松弛。SLF+LLL可将效率提升约50%。
  • SPFA效率不稳定，若无负权边，通常采用Dijkstra。

多对顶点间最短路径

动态规划求解算法

  • 数据的记录：在单源最短路径中我们采用前缀数组pre[i]记录以i为终点的最短路径上的前一个结点，在多对顶点间最短路径问题中，将此数组延伸为二维数组，用pre[i][j]记录从i到j的最短路径上，j的前趋结点。这时打印路径的方法可以用以下伪代码描述。
1
2
3
4
5
6
7
PRINT_ALL_PAIRS_SHORTEST_PATH( pre, i, j)
    if i = j :
	   then print i
	else if pre[i][j] = Nil:
		 then print "No path from" i "to" j
		 else PRINT_ALL_PAIRS_SHORTEST_PATH( pre, i, pre[i][j] )
		 	  print j
  • 简要描述设计动态规划算法的步骤
    • 描述一个最优解的结构
    • 递归定义一个最优解的值
    • 按自底向上的方式计算一个最优解的值
    • 从计算出的信息中构造出一个最优解
  • 具体分析最短路径问题
    • 最短路径的结构：在单源最短路径中我们已经得到最短路径满足最优子结构，即最短路径的所有子路径也是最短路径。
    • 最短路径问题的状态转移方程：考虑状态转移方程，首先考虑如何通过变量表示整个递推过程，再用类似数学归纳法给出递推过程，通常用“恰好”和“至多”定义某个可递推的变量。对于i、j之间的最短路径，这条最短路径至多包含m条边，用L(i,j,m)表示从i到j，至多包含m条边的任何路径的权值最小值。当m=0时，i = j。因此当i=j时，L(i,j,0) = 0，否则L(i,j,0)=正无穷。对于m非0情况，我们可以发现，至多包含m条边时的最短路径，要么是最多包含m-1条边的最短路径，要么是在m-1条边的最短路径的基础上计算出在m条边下的最短路径（这里用例子说明，假如L(i,j,m)不是L(i,j,m-1)，则一定是走了一条i~>k -> j的路径，根据最优子结构，i~>k的路径一定是最短路径，这在推导m-1时已经得到了，因此i~>k的权值L(i,k,m-1)+w(k,j)就是L(i,j,m)。用递归式表达即L(i,j,m) = min{ L(i,k,m-1) + w(k,j) }, k from 1 to n。这个式子包含了L(i,j,m)=L(i,j,m-1)的情况，因为w(j,j)=0。因为图G=(V,E)的任一最短路径至多只能包含|V|-1条边，因此L(i,j,|V|-1)就是任意i到j的最短路径的权值。
    • 自底向上计算最短路径权值：对于一个给定的临界矩阵W，和一个已经求好的L(k-1)，可以用以下伪代码求出L(k)。
1
2
3
4
5
6
7
8
9
EXTEND_SHORTEST_PATHS(L,W)
	n <- rows(L)	# 顶点数目
	let L' be an n×n matrix
	for i from 1 to n:
		for j from 1 to n:
			L'[i][j] = INF
				for k from 1 to n:
					L'[i][j] = min( L[i][k] + w(k,j) )
	return L'

因此，可以加上一重循环，求出L(m)。时间复杂度O(V^4)。

1
2
3
4
5
6
SLOW-ALL-PAIRS-SHORTEST-PATHS(W)
	n <- rows(W)
	Let L(1) = W
	for m from 2 to n-1:
		L(m) <- EXTEND-SHORTEST-PATHS( L(m-1), W )
	return L(m-1)
  • 与矩阵乘法相结合：
    考虑两个矩阵A和B相乘C = A·B，对与i，j=1,2,…,n，计算c(ij) = Sum( a(ik)·b(kj) , k from 1 to n )，记此式为‘。上面给出的递推公式，作如下替换：l(m-1) -> a，w -> b， l(m) -> c， + -> · ， min -> + ，则得到了式‘。因此，EXTEND_SHORTEST_PATHS(A,B)实际返回的是A·B，因此L(1) = L(0)·W， L(2) = L(1)·W = W^2，…，L(n-1) = L(n-2)·W = W^(n-1)。
  • 改进运行时间：对矩阵的乘方作快速幂运算。改进后的时间复杂度为O(V^3·lgV)。

Floyd-Warshall

  • 同样是动态规划算法，利用了最短路径结构的另一个特点，不同于基于矩阵乘法算法中的特征。Floyd考虑最短路径上的中间结点，对于一条从u到v的简单路径（不含环）p，中间结点是p上除了u和v之外的其他结点。此算法应用广泛，在群论中用于计算传递闭包，图论中还可用于计算最大流。
  • Floyd-Warshall算法基于以下最优子结构：将G的V个顶点编号为1,2,3,…,V，任意一对顶点(i,j)，考虑从i到j并且所有中间结点都属于集合{1,2,3,…,k}的路径，并设p是这些路径中的最短路径，则可推导出“从i到j并且所有中间结点都属于集合{1,2,3,…,k,k+1}的最短路径p’”。推导过程如下：假设顶点k+1不是路径p’的中间结点，则p’的所有中间结点都在集合{1,2,3,…,k}中，因此p’=p。假设顶点k+1是路径p’的中间结点，则可将p’分解为i~>k+1, k+1~>j，分别记为p1和p2，根据最短路径最优子结构，p1和p2分别是从i到k+1和从k+1到j的最短路径，p1和p2的中间结点均属于{1,2,3,…,k}。
  • 递归解：记D(i,j,k)为上述的p的权值，则k=0时有D(i,j,k) = w(i,j)，k非0时有D(i,j,k) = min{ D(i,j,k-1), d(i,k,k-1) + d(k,j,k-1) }。根据该方程，我们知道D(i,j,k)的值从D(i,j,k-1)推出，因此D(i,j,k-1)必须在D(i,j,k)之前计算。因此将k放在伪代码的最外层循环。伪代码如下。
1
2
3
4
5
6
7
8
FLOYD-WARSHALL(W)
	n <- rows(W)
	D(0) <- W
	for k from 1 to n:
		for i from 1 to n:
			for j from 1 to n:
				D(i,j,k) = min ( D(i,j,k-1) , D(i,k,k-1)+D(k,j,k-1) )
	return D(n)

代码实现

Dijkstra+堆优化

SPFA+SLF+LLL

Floyd-Warshall

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(https://forec.github.io/2015/12/23/Graph-Algorithms5/) 、作者信息（Forec）和本声明。

分享到