基本介紹
- 中文名：距離矢量路由協定
- 外文名：distance-vector routing protocol
簡介,貝爾曼-福特算法,算法,偽代碼表示,路由協定,路由信息協定,
簡介
距離向量路由協定（英語：distance-vector routing protocol），為路由協定中的兩大分類之一，這類協定採用距離向量（distance-vector，縮寫為DV）算法來決定報文交換的路徑。包括貝爾曼-福特算法，Ford–Fulkerson algorithm與DUAL FSM等算法，都被歸類於距離向量算法中。
貝爾曼-福特算法
貝爾曼-福特算法（英語：Bellman–Ford algorithm），求解單源最短路徑問題的一種算法，由理察·貝爾曼（Richard Bellman） 和萊斯特·福特創立的。有時候這種算法也被稱為 Moore-Bellman-Ford 算法，因為Edward F. Moore也為這個算法的發展做出了貢獻。它的原理是對圖進行
次鬆弛操作，得到所有可能的最短路徑。其優於迪科斯徹算法的方面是邊的權值可以為負數、實現簡單，缺點是時間複雜度過高，高達
。但算法可以進行若干種最佳化，提高了效率。
算法
貝爾曼-福特算法與迪科斯徹算法類似，都以鬆弛操作為基礎，即估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。在兩個算法中，計算時每個邊之間的估計距離值都比真實值大，並且被新找到路徑的最小長度替代。 然而，迪科斯徹算法以貪心法選取未被處理的具有最小權值的節點，然後對其的出邊進行鬆弛操作；而貝爾曼-福特算法簡單地對所有邊進行鬆弛操作，共次，其中
是圖的點的數量。在重複地計算中，已計算得到正確的距離的邊的數量不斷增加，直到所有邊都計算得到了正確的路徑。這樣的策略使得貝爾曼-福特算法比迪科斯徹算法適用於更多種類的輸入。
偽代碼表示
procedure BellmanFord(list vertices, list edges, vertex source)
// 該實現讀入邊和節點的列表，並向兩個數組（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：重複對每一條邊進行鬆弛操作
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// 步驟3：檢查負權環
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "圖包含了負權環"
路由協定
路由協定（英語：Routing protocol）是一種指定數據包轉送方式的網上協定。Internet網路的主要節點設備是路由器，路由器通過路由表來轉發接收到的數據。轉發策略可以是人工指定的（通過靜態路由、策略路由等方法）。在具有較小規模的網路中，人工指定轉發策略沒有任何問題。但是在具有較大規模的網路中（如跨國企業網路、ISP網路），如果通過人工指定轉發策略，將會給網路管理員帶來巨大的工作量，並且在管理、維護路由表上也變得十分困難。為了解決這個問題，動態路由協定應運而生。動態路由協定可以讓路由器自動學習到其他路由器的網路，並且網路拓撲發生改變後自動更新路由表。網路管理員只需要配置動態路由協定即可，相比人工指定轉發策略，工作量大大減少。
