最短路径算法Bellmanford算法

2次阅读

共计 2922 个字符，预计需要花费 8 分钟才能阅读完成。

最短路径问题
在图结构中，求解最短路径问题有多种算法，Bellman-Ford 是其中之一，它可以处理含有负权边的情况，同样是单源最短路径算法，而之前讲到的 Dijkstra 算法不能处理含有负权边的情况。对应的代价就是其算法时间复杂度要高一些。后面我们会分析。

这里能处理负权边是针对有向图的，因为对无向图来说，含有负权边就意味着含有负权回路，在有负权回路的这种情况下求最短路径是无解的，因为每经过一次负权回路，距离都会减少，就会无限循环下去。

在继续往下讲之前，先补充一个图最短路径的一个性质：最短路径的子路径也是最短路径，数学描述如下：有向图 G =(V,E)G=(V,E)G=(V,E)，设 p =(v0,v1,…,vk)p=(v_0,v_1,…,v_k)p=(v
0

,v
1

,…,v
k

)为从点 v0v_0v
0

到点 vkv_kv
k

的一条最短路径，且 0≤i≤j≤k0≤i≤j≤k0≤i≤j≤k，设 pij=(vi,vi+1,…,vj)p_{ij}=(v_i,v_{i+1},…,v_j)p
ij

=(v
i

,v
i+1

,…,v
j

)为路径 ppp 中从点 viv_iv
i

到点 vjv_jv
j

的子路径，那么 pijp_{ij}p
ij

也是这两点之间的一条最短路径。可用反证法来证明：

证明：如果将路径 ppp 分解为 v0−vi−vj−vkv_0-v_i-v_j-vkv
0

−v
i

−v
j

−vk，则有 w(p)=w(p0i)+w(pij)+w(pjk)w(p)=w(p_{0i})+w(p_{ij})+w(p_{jk})w(p)=w(p
0i

)+w(p
ij

)+w(p
jk

)。假设存在一条从 viv_iv
i

到 vjv_jv
j

的一条更短的路径 p′ijp_{ij}’p
ij
′

，w(p′ij<w(pij))w(p_{ij}'<w(p_ij))w(p
ij
′

<w(p
i

j))。则新路径权值为 w(p0i)+w(p′ij)+w(pjk)<w(p)w(p_{0i})+w(p_{ij}’)+w(p_{jk}) < w(p)w(p
0i

)+w(p
ij
′

)+w(p
jk

)<w(p)，这与 ppp 是最短路径相矛盾。

Bellman-Ford 算法
与 Dijkstra 算法类似，Bellman-Ford 算法也是通过不断的“松弛”操作来求得最终解。“松弛”就是如下的操作过程：w(u,v)w(u,v)w(u,v)表示 uuu 与 vvv 之间的权值，d[v]d[v]d[v]表示从源点 sss 到顶点 vvv 的距离，若存在边 e(u,v)e(u,v)e(u,v)，使得：d[v]>d[u]+w(u,v)d[v] > d[u] + w(u,v)d[v]>d[u]+w(u,v)(即发现了优于当前的路径), 则更新 d[v]=d[u]+w(u,v)d[v] = d[u] + w(u,v)d[v]=d[u]+w(u,v)，并更新路径 prev[v]=uprev[v] = uprev[v]=u。可以看到每一次“松弛”都会更逼近最优解。Dijkstra 算法通过优先队列每次选择当前未被处理过的距离最小的顶点，对该顶点未被处理过的边进行松弛。而 Bellman-Ford 算法则简单的松弛所有的边，反复执行∣V∣−1|V|-1∣V∣−1 次（∣V∣|V|∣V∣为顶点的的个数），时间复杂度 O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。可以看出，Bellman-Ford 松弛的次数远多于 Dijkstra，所以其时间复杂度相比 Dijkstra 要高。

伪代码如下：

function BellmanFord(list vertices, list edges, vertex source)

// step 1 初始化, dist[v]表示源节点到顶点 v 的距离值，prev[v]表示顶点 v 的前驱顶点
for each vertex v in vertices
    dist[v] = inf
    prev[v] = null

dist = 0

// step 2 迭代松弛 |V|- 1 次
for i from 1 to size(vertices) -1 
    for each edge(u,v) with weight(u,v)  in edges
        if dist[u] + weight(u,v) < dist[v]
            dist[v] = dist[u] + weight(u,v)
            prev[v] = u

// step 3 检查是否有负权回路
for each edge(u,v) with weight(u,v) in edges
    if dist[u] + weight(u,v) < dist[v]
        error "检测到负权回路"

return dist[], prev[]

对算法的优化：在实际应用中，Bellman-Ford 算法其实不用迭代松弛∣V∣−1|V|-1∣V∣−1 次，理论上图中存在的最大的路径长度为∣V∣−1|V|-1∣V∣−1，实际上往往要小于这个∣V∣−1|V|-1∣V∣−1，即，在∣V∣−1|V|-1∣V∣−1 次迭代松弛之前就已经收敛了，计算出最短路径了，所以可在循环中设置判定，在某次循环中不再进行松弛时，表明当前已收敛，可退出步骤 2，进行下一步检查是否有负权回路。

怎么理解这个算法呢？假设某顶点与源顶点没有连通，即没有边，那么这个点就不会被松弛，距离不会被更新，依旧为无穷大。如果顶点与源顶点是连通的，在不存在负权回路的情况下，一定存在一条最短路径，这条最短路径 p =(v0,v1,…,vk)p=(v_0,v_1,…,v_k)p=(v
0

,v
1

,…,v
k

)为源点 sss 到 vvv 之间的任意一条最短路径 (这里 v0=sv_0=sv
0

=s，vk=vv_k=vv
k

=v)。最大会有多少条边呢？假设图有∣V∣|V|∣V∣个顶点，那么有 k≤∣V∣−1k≤|V|-1k≤∣V∣−1。在进行第一轮松弛时，被松弛的边中一定会包含边(v0,v1)(v_0,v_1)(v
0

,v
1

)，结合文章开头讲到的最短路径的子路径也一定是最短路径的性质，v1v_1v
1

已经得到了其最短路径，在第二轮松弛过程中，被松弛的边中一定会包含边(v1,v2) 边(v_1,v_2)边(v
1

,v
2

)，经过此次松弛后，v2v_2v
2

也已经得到了其最短路径。以此类推，在第 kkk 轮松弛中，被松弛的边中一定包含了边(vk−1,vk)(v_{k-1},v_k)(v
k−1

,v
k

)，之后 vkv_kv
k

也得到其最短路径。也就是说，凡是与源顶点最短路径经过的边数为 kkk 的顶点，在第 kkk 轮松弛时一定会被确认（最短路径被找到）。所以，我们需要松弛多少轮呢，最多∣V∣−1|V|-1∣V∣−1 次就可以了。