最短路径算法Bellmanford算法

80次阅读

共计 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 次就可以了。

算法的数学证明可以参考《图论》或《算法导论》中的证明过程。

代码实现见 bellman_ford.cpp。最后再分析一下时间复杂度,最坏的情况 O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣),这个比较好理解,最好的情况 O(∣E∣)O(|E|)O(∣E∣),一次松弛所有边的操作就可以了,对应的就是边松弛的顺序恰好是最短路径树的生成顺序。

算法的应用
其中一个应用就是路由协议了(距离向量协议),对此实现了一个路由协议测试工程,代码见 router。实现了一个通过路由表的方式进行的路由算法。

正文完
 0