最短路径

分析图论中各类最短路径问题的算法设计,给出 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)和本声明。

分享到