我們知道，狄克斯特拉算法可以用于尋找權(quán)值為正的有向無(wú)環(huán)圖的最短路徑坏逢。如果我們遇到圖中某些邊的權(quán)值為負(fù)，我們應(yīng)該如何尋找最短路徑呢?貝爾曼福德算法就是一種思路。
如果說(shuō)狄克斯特拉算法是用一種“廣度”的方式惹谐，每次尋找源點(diǎn)所能到達(dá)的距離最短的一個(gè)點(diǎn)，更新其鄰居節(jié)點(diǎn)的距離（拓展）驼卖。那么貝爾曼福德算法就是用一種“深度”的方式氨肌，每次找到所有的路徑，進(jìn)行“松弛”操作（更新最短的路徑）最終找到最短路徑酌畜。
算法過(guò)程
松弛操作
貝爾曼福德算法是基于“松弛”操作來(lái)進(jìn)行的擅这，我們首先來(lái)看一下什么是松弛操作郭卫。其實(shí)表述起來(lái)也很簡(jiǎn)單，就是：
- 有兩個(gè)點(diǎn)A、B都可以從源點(diǎn)經(jīng)由某條路徑到達(dá)结笨，假設(shè)源點(diǎn)經(jīng)由某條路徑到A點(diǎn)的距離是M宰衙，源點(diǎn)經(jīng)某條路徑到達(dá)B點(diǎn)的距離是N旅薄；
- A點(diǎn)可直接到達(dá)B點(diǎn)搁进，并且A點(diǎn)到B點(diǎn)的距離是L。
- 如果有 M(源點(diǎn)到A的距離) + L(A到B的距離) < N(源點(diǎn)到B的距離)缎罢，那么就說(shuō)明有一條新的從源點(diǎn)到B的路線（途徑A點(diǎn)）的距離要小于之前源點(diǎn)到B點(diǎn)的距離伊群。此時(shí)我們更新源點(diǎn)到B的距離為 M + L。
這樣下來(lái)策精，源點(diǎn)到B點(diǎn)的最小距離就被縮短了舰始，也就是說(shuō)我們找到了一條更近的能夠從源點(diǎn)到達(dá)B點(diǎn)的路（經(jīng)由A點(diǎn)）。這個(gè)路線的距離被縮短了蛮寂，這個(gè)過(guò)程就是 “松弛” 的過(guò)程蔽午。
基于“深度”的松弛操作
對(duì)最短路徑的一個(gè)認(rèn)知
首先，我們要想清楚一件事酬蹋，那就是：含有N個(gè)頂點(diǎn)的圖及老，某兩個(gè)頂點(diǎn)之間最短路徑的深度不會(huì)超過(guò)N-1抽莱。
這句話的意思是，如果我們找到的是一條最短的路徑骄恶，那么這條最短的路徑包含的邊肯定小于N-1條食铐；最短路徑最多邊的情況就是經(jīng)歷了所有的節(jié)點(diǎn)，最終到達(dá)終點(diǎn)僧鲁，此時(shí)路徑的變數(shù)為N-1條虐呻。
為什么是這樣呢？因?yàn)槿绻皇沁@樣的話寞秃，那么圖中肯定存在一個(gè) 環(huán)路：
我們看圖斟叼，圖中存在一條環(huán)路，B => C春寿。如果我們從A出發(fā)最終到達(dá)D朗涩，那么我們的最短路徑是什么呢？很容就能看到绑改，最短路徑是 A => B => D谢床。如果我們經(jīng)過(guò)一次B、C之間的環(huán)路厘线，那么路徑就會(huì)變?yōu)?A => B => C => B => D识腿。此時(shí)路徑長(zhǎng)度就會(huì)增加B、C之間距離的2倍造壮，就是2渡讼。也就是說(shuō)，這種情況下费薄，每每經(jīng)過(guò)一次環(huán)路硝全，路徑的總長(zhǎng)度就會(huì)增加2栖雾。
如果我們整個(gè)路徑中沒(méi)有環(huán)路楞抡，也就是沒(méi)有兩個(gè)點(diǎn)間互相到達(dá)的這種情況，那么我們的路徑中析藕，肯定就不會(huì)存在某個(gè)頂點(diǎn)重復(fù)出現(xiàn)的情況（剛才 A=>B=>C=>B=>D中存在環(huán)路召廷，B就重復(fù)出現(xiàn)了），所以最多我們就是經(jīng)歷了所有的頂點(diǎn)：N個(gè)账胧。這N個(gè)頂點(diǎn)可以確定N-1條邊竞慢。所以：含有N個(gè)頂點(diǎn)的圖，某兩個(gè)頂點(diǎn)之間最短路徑的深度不會(huì)超過(guò)N-1治泥。
基于深度進(jìn)行松弛操作
為什么說(shuō)是基于深度進(jìn)行的松弛操作呢筹煮？我們依然使用狄克斯特拉算法時(shí)候的路徑圖來(lái)證明這一點(diǎn)。另外居夹，我們還需要兩個(gè)圖表（與狄克斯特拉算法的相同）：距離表败潦、父節(jié)點(diǎn)表本冲。
- 最初的時(shí)候，這個(gè)表中的值如下：
我們得到了一張從Start開(kāi)始劫扒，第一步只能到達(dá)A檬洞、B兩點(diǎn)的初始化的距離表，也就是說(shuō)沟饥，此時(shí)到達(dá)A添怔、B的距離是已知的，因?yàn)榭梢杂蒘tart直接到達(dá)贤旷； 得到一個(gè)只有Start點(diǎn)作為父節(jié)點(diǎn)的兩個(gè)點(diǎn)A广料、B的父地點(diǎn)表；還有一個(gè)全部路徑的路徑圖幼驶。
- 我們遍歷路徑表中的 相鄰兩點(diǎn)之間的全部路徑 一次性昭，根據(jù)距離表更新每個(gè)點(diǎn)的到達(dá)距離。也就是對(duì)圖進(jìn)行一次松弛操作：
我們可以看到县遣，初始化的時(shí)候糜颠，Start確定的是只能直接到達(dá)A、B兩點(diǎn)萧求。我們遍歷所有的 兩點(diǎn)之間 的路徑（比如A其兴、C之間的這條 A => C路徑，起點(diǎn)為：A夸政；終點(diǎn)為：C元旬；權(quán)值為：2）。我們根據(jù)距離表守问，知道了起點(diǎn)到A的距離是5匀归，到B的距離是3。由于A能到達(dá)C耗帕、D（存在路徑：A => C 穆端、A => D），所以仿便，此時(shí)通過(guò)A到達(dá)C体啰、D的距離就是（B點(diǎn)同理）：
對(duì)于經(jīng)過(guò)A直接到達(dá)的點(diǎn)：
C的距離 = 5（Start到A的距離）+ 2（A到C的距離，也就是 A => C 的權(quán)值）= 7
D的距離 = 5（Start到A的距離）+ 2（A到C的距離嗽仪，也就是 A => C 的權(quán)值）= 7
對(duì)于經(jīng)過(guò)B直接到達(dá)的點(diǎn)：
C的距離 = 3 （Start到B的距離）+ 1（B到C的距離荒勇，也就是 B=> C 的權(quán)值）= 4
E的距離 = 3 （Start到B的距離）+ 6（B到E的距離，也就是 B=> C 的權(quán)值）= 9
我們依次遍歷所有相鄰兩點(diǎn)之間的路徑闻坚，遍歷到 A => C 的時(shí)候沽翔，我們得到Start到C的距離是 5 + 2 = 7，將其寫(xiě)入距離表中窿凤；但是之后遍歷到 B => C 的時(shí)候仅偎，我們又得到了Start到C的距離是 3 + 1 = 4 < 7西潘，所以我們更改距離表，到達(dá)C的距離就更新為了4哨颂。遍歷完所有路徑后（松弛之后）喷市，我們更新了圖中的距離表，就是現(xiàn)在這個(gè)樣子威恼。同樣品姓，我們將記錄進(jìn)距離表的點(diǎn)的相應(yīng)的父節(jié)點(diǎn)也寫(xiě)進(jìn)父地點(diǎn)表。
我們可以對(duì)比第一張圖來(lái)看箫措，此時(shí)我們做的操作腹备，其實(shí)就是基于深度（淺色標(biāo)線）的一次松弛操作。
- 繼續(xù)2中的操作過(guò)程斤蔓，我們?cè)僖淮伪闅v全部的相鄰兩點(diǎn)之間的路徑植酥，我們可以得到如下三張圖：
同樣的操作，我們繼續(xù)遍歷所有相鄰兩點(diǎn)之間的路徑（包括之前已經(jīng)記錄過(guò)距離的點(diǎn)弦牡，每次都遍歷全部友驮，因?yàn)椴恢乐氨闅v過(guò)的會(huì)不會(huì)被再次更新，再次松弛）驾锰。所以這次我們松弛的邊分別是（這個(gè)圖來(lái)說(shuō)之前兩部遍歷過(guò)后卸留，有一些邊再松弛權(quán)重已經(jīng)不會(huì)改變）：
D => C、D => End椭豫，C => End耻瑟、E => End
D => C : 查表得知到D的距離是7，D到C的距離是3赏酥，7 + 3 = 10 > 4（表中C的距離）喳整，所以C的距離不更新；
D => End: 查表知到D的距離是7裸扶，D到End的距離是4框都，7 + 4 = 11，表中無(wú)End姓言，所以加入End = 11瞬项， 父地點(diǎn)為D；
C => End: 查表知到C的距離是4何荚，C到End的距離是5，4 + 5 = 9 < 11（D=>End寫(xiě)入的）猪杭，所以更新End的距離為 9餐塘， 父節(jié)點(diǎn)為C；
E => End: 查表知到E的距離是9皂吮， E到End的距離是1戒傻，9 + 1 = 10 > 9 (C => End更新過(guò)的)税手，所以不更新距離表和父節(jié)點(diǎn)表。
到此更新完畢了需纳。我們得到了最終的距離表和父地點(diǎn)表芦倒。這樣就得到了結(jié)論，從Start到到End的最小距離是9不翩，路徑是：End => C(End的父節(jié)點(diǎn)) => B(C的父節(jié)點(diǎn)) => Start(B的父節(jié)點(diǎn)) 的反轉(zhuǎn) Start => B => C => End兵扬。
這張圖比較簡(jiǎn)單，我們只是初始化了一次各個(gè)表格口蝠，3次遍歷(初始化算一次)所有的相鄰節(jié)點(diǎn)之間的路徑就得到了最終的路徑器钟。但是根據(jù)上面我們 對(duì)最短路徑的一個(gè)認(rèn)知 可以知道，并不是所有的節(jié)點(diǎn)分布都如此妙蔗，但是傲霸，最短路徑的深度最多就是 N(節(jié)點(diǎn)個(gè)數(shù)) - 1，所以我們最多需要遍歷 N - 1 次眉反。
算法可以用于含有負(fù)權(quán)值邊的圖
狄克斯特拉算法實(shí)際是依賴廣度來(lái)進(jìn)行拓展昙啄。依賴廣度來(lái)進(jìn)行拓展就會(huì)造成已經(jīng)完成任務(wù)的頂點(diǎn)就不能再改變其距離，最終是通過(guò)累加的方式寸五，算出所有頂點(diǎn)到達(dá)源點(diǎn)的最小路徑跟衅，只能逐漸增加總權(quán)值，負(fù)值的存在會(huì)減小總權(quán)值播歼，可能會(huì)造成某條路徑上的頂點(diǎn)從原來(lái)的不是當(dāng)前距離表中的最小值變成最小值伶跷。
由于貝爾曼福德算法是通過(guò)N-1次遍歷，每次都遍歷所有的兩個(gè)相鄰頂點(diǎn)之間的路徑秘狞。所以是有窮次的單純遍歷去“松弛”叭莫，相當(dāng)于在深度上去松弛，每次都會(huì)再次遍歷所有的路徑進(jìn)行松弛烁试，簡(jiǎn)單粗暴雇初，所以路徑上某個(gè)頂點(diǎn)距離的變化都是動(dòng)態(tài)的來(lái)變化，因?yàn)槊看伪闅v只在一個(gè)深度减响，并不能確定下一個(gè)深度遍歷過(guò)后靖诗，某個(gè)頂點(diǎn)的到達(dá)距離是會(huì)變大還是縮小。所以不管放大還是縮小都是可以的支示，也就是不管路徑的權(quán)值是正還是負(fù)都是可以的刊橘。
去除負(fù)權(quán)環(huán)
上面的過(guò)程實(shí)際上還沒(méi)有結(jié)束，我們還需要思考一個(gè)問(wèn)題：如果圖中存在負(fù)權(quán)環(huán)會(huì)怎么樣颂鸿？答：存在負(fù)權(quán)環(huán)的話會(huì)使最終某幾個(gè)頂點(diǎn)的到達(dá)距離值不收斂于一個(gè)小的值促绵，每次更新都不斷的減小，無(wú)限制的減小。
如圖败晴，如果圖中某一部分如圖中所示浓冒，是一個(gè)包含有負(fù)權(quán)值的一個(gè)環(huán)路，那么我們第一次遍歷所有相鄰接點(diǎn)之間的路徑進(jìn)行松弛的時(shí)候尖坤，各個(gè)頂點(diǎn)的距離會(huì)發(fā)生變化（假設(shè)遍歷順序從 C => A 這條路徑開(kāi)始）：
我們可以看到稳懒，遍歷一次之后，環(huán)中所有的頂點(diǎn)的距離值都變小了慢味！如果圖中的所有節(jié)點(diǎn)個(gè)數(shù)有N個(gè)场梆，根據(jù)上面，我們會(huì)進(jìn)行N-1次循環(huán)贮缕，那么在這N-1次循環(huán)中辙谜，這個(gè)環(huán)中的節(jié)點(diǎn)的距離每次都會(huì)減小，總的距離會(huì)無(wú)限減小感昼，以至于最終找不到最短的路徑（每次都減短装哆，無(wú)限循環(huán)的話就無(wú)限減短，這肯定是不對(duì)的）定嗓。
所以我們要檢查圖中有沒(méi)有負(fù)權(quán)環(huán)蜕琴。檢查的方法就是，在經(jīng)歷過(guò)之前N-1次循環(huán)之后宵溅，我們?cè)俅螜z查一遍所有的相鄰節(jié)點(diǎn)之間的路徑凌简。如果不存在負(fù)權(quán)環(huán)，那么N-1次之后我們肯定找到了最短路徑恃逻，那么我們此時(shí)圖中的所有的相鄰節(jié)點(diǎn)之間的路徑都會(huì)滿足（比如 C => A）：
C的距離 + C到A的距離 >= A的距離（如果C => A 是最短路徑的一部分取=雏搂，如果不是就取 >）
如果存在負(fù)權(quán)環(huán)，導(dǎo)致的是這個(gè)環(huán)中所有的頂點(diǎn)的到達(dá)距離會(huì)無(wú)限減小寇损。我們N-1次循環(huán)是有限的凸郑，但是N-1次循環(huán)之后，再次進(jìn)行檢查時(shí)（多加一次第N次循環(huán)）矛市，距離還是可以減小芙沥，也就是（比如C => A）:
C的距離 + C到A的距離 < A的距離（這個(gè)言外之意就是還能優(yōu)化，我們知道經(jīng)歷N-1次循環(huán)之后已經(jīng)找到最短路徑了浊吏，這里還能再找而昨，也就是無(wú)限減小最短路徑的距離）
所以出現(xiàn)這種情況，我們就可以判定找田，這個(gè)圖中存在負(fù)權(quán)環(huán)歌憨。如果存在負(fù)權(quán)環(huán)，那么我們經(jīng)歷N-1次循環(huán)之后我們得到的最短路徑就不一定是最短的路徑了午阵。所以只有在經(jīng)歷過(guò)N-1次遍歷松弛之后躺孝，再進(jìn)行負(fù)權(quán)環(huán)的判定享扔，如果沒(méi)有負(fù)權(quán)環(huán)的存在底桂，那么我們得到的最短路徑植袍，就是正確的。
算法實(shí)現(xiàn)
# -*- coding: utf-8 -*-
# @Time : 2019-01-02 12:27
# @Author : Jaedong
# @Version : 3.6
# @File : Bellman-Ford_algorithm.py
# @Software: PyCharm
# 定義一個(gè)表示邊的類(lèi)
class Edge:
u = '' # 邊的起點(diǎn)
v = '' # 邊的終點(diǎn)
weight = 0 # 邊的權(quán)重
def __init__(self, u, v, weight):
self.u = u
self.v = v
self.weight = weight
# 貝爾曼福德算法的主體
def bellman_ford_algorithm(vertices, edges, start, end):
distances = {}
parents = {}
# 初始化參數(shù)
for v in vertices:
if v == start:
distances[v] = 0
else:
distances[v] = float('inf')
# 遍歷并且松弛每一條邊
for i in range(0, len(vertices) ):
for edge in edges:
if distances[edge.u] + edge.weight < distances[edge.v]:
distances[edge.v] = distances[edge.u] + edge.weight
parents[edge.v] = edge.u
# 檢查是否有負(fù)權(quán)環(huán)
for edge in edges:
if distances[edge.u] + edge.weight < distances[edge.v]:
return None, None
# 更新了所有節(jié)點(diǎn)的到達(dá)最小距離籽懦，那么到達(dá)end的最小距離就是distances表中end所對(duì)應(yīng)的值
distance = distances[end]
# 通過(guò)不斷的回溯的方式于个，得到end到達(dá)start的路徑，這樣暮顺，就得到了start到達(dá)end的路徑
parent = parents[end]
paths = [parent, end]
while parent is not start:
paths.insert(0, parents[parent])
parent = parents[parent]
return distance, paths
# 所有圖中的頂點(diǎn)
vertex = ['Start', 'A', 'B', 'C', 'D', 'E', 'End']
# 所有圖中的邊
edges = [Edge('Start', 'A', 5), Edge('Start', 'B', 3),
Edge('A', 'C', 2), Edge('A', 'D', 2),
Edge('B', 'C', 1), Edge('B', 'E', 6),
Edge('C', 'End', 5),
Edge('D', 'C', 3), Edge('D', 'End', 4),
Edge('E', 'End', 1)]
distance, paths = bellman_ford_algorithm(vertex, edges, 'Start', 'End')
print('\n從 Start 到 End 的最短的距離是：{}, 路徑是： {}'.format(distance, ' ==> '.join(paths)))
結(jié)果是：
上一篇：寫(xiě)給媳婦兒的算法（十二）——狄克斯特拉算法
下一篇：寫(xiě)給媳婦兒的算法（十四）——?jiǎng)討B(tài)規(guī)劃
