[科普中國]-距離矢量路由協(xié)議

距離向量路由協(xié)議（英語：distance-vector routing protocol），為路由協(xié)議中的兩大分類之一，這類協(xié)議采用距離向量（distance-vector，縮寫為DV）算法來決定報文交換的路徑。包括貝爾曼-福特算法，F(xiàn)ord–Fulkerson algorithm與DUAL FSM等算法，都被歸類于距離向量算法中。

簡介距離向量路由協(xié)議（英語：distance-vector routing protocol），為路由協(xié)議中的兩大分類之一，這類協(xié)議采用距離向量（distance-vector，縮寫為DV）算法來決定報文交換的路徑。包括貝爾曼-福特算法，F(xiàn)ord–Fulkerson algorithm與DUAL FSM等算法，都被歸類于距離向量算法中。

這類協(xié)議包括路由信息協(xié)議（RIP）及內(nèi)部網(wǎng)關(guān)協(xié)議（IGP）等。在這類協(xié)議中，路由器需要周期性與相鄰的路由器交換更新通告（routing updates），動態(tài)建立路由表，以決定最短路徑。1

貝爾曼-福特算法貝爾曼-福特算法（英語：Bellman–Ford algorithm），求解單源最短路徑問題的一種算法，由理查德·貝爾曼（Richard Bellman） 和萊斯特·福特創(chuàng)立的。有時候這種算法也被稱為 Moore-Bellman-Ford 算法，因為Edward F. Moore也為這個算法的發(fā)展做出了貢獻。它的原理是對圖進行次松弛操作，得到所有可能的最短路徑。其優(yōu)于迪科斯徹算法的方面是邊的權(quán)值可以為負數(shù)、實現(xiàn)簡單，缺點是時間復(fù)雜度過高，高達。但算法可以進行若干種優(yōu)化，提高了效率。

算法貝爾曼-福特算法與迪科斯徹算法類似，都以松弛操作為基礎(chǔ)，即估計的最短路徑值漸漸地被更加準(zhǔn)確的值替代，直至得到最優(yōu)解。在兩個算法中，計算時每個邊之間的估計距離值都比真實值大，并且被新找到路徑的最小長度替代。 然而，迪科斯徹算法以貪心法選取未被處理的具有最小權(quán)值的節(jié)點，然后對其的出邊進行松弛操作；而貝爾曼-福特算法簡單地對所有邊進行松弛操作，共次，其中是圖的點的數(shù)量。在重復(fù)地計算中，已計算得到正確的距離的邊的數(shù)量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特算法比迪科斯徹算法適用于更多種類的輸入。

貝爾曼-福特算法的最多運行（大O符號）次，和分別是節(jié)點和邊的數(shù)量）。

偽代碼表示procedure BellmanFord(list vertices, list edges, vertex source) // 該實現(xiàn)讀入邊和節(jié)點的列表，并向兩個數(shù)組（distance和predecessor）中寫入最短路徑信息 // 步驟1：初始化圖 for each vertex v in vertices: if v is source then distance[v] := 0 else distance[v] := infinity predecessor[v] := null // 步驟2：重復(fù)對每一條邊進行松弛操作 for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance[u] + w