貝爾曼福德演算法

『壹』 最短路徑演算法

最短路徑的演算法主要有三種：floyd演算法、Dijkstra演算法、Bellman-Ford(貝爾曼-福特)

一、floyd演算法

基本思想如下：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點X到B。所以，我們假設Dis(AB)為節點A到節點B的最短路徑的距離，對於每一個節點X，我們檢查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設置Dis(AB) = Dis(AX) + Dis(XB)，這樣一來，當我們遍歷完所有節點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。

三、Bellman-Ford(貝爾曼-福特)

演算法的流程如下：

給定圖G(V, E)（其中V、E分別為圖G的頂點集與邊集），源點s，

1.數組Distant[i]記錄從源點s到頂點i的路徑長度，初始化數組Distant[n]為, Distant[s]為0；

2.以下操作循環執行至多n-1次，n為頂點數：
對於每一條邊e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；
若上述操作沒有對Distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；

3.為了檢測圖中是否存在負環路，即權值之和小於0的環路。對於每一條邊e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的邊，則圖中存在負環路，即是說該圖無法求出單源最短路徑。否則數組Distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

可知，Bellman-Ford演算法尋找單源最短路徑的時間復雜度為O(V*E).

『貳』 EIGRP 和RIPv2 哪方面的功能不同

1.使用演算法不同,EIGRP(DUAL演算法),RIPv2(Bellman-Ford的DV演算法);
2.度量值不同,EIGRP採用復合度量值(帶寬,時延,可靠性,負載,MTU),RIPv2僅採用跳數作度量,而且有最大跳數(16跳)的限制;
3.組播地址不同,EIGRP(224.0.0.10),RIPv2(224.0.0.9);
4.管理距離不同,EIGRP為90(當然EIGRP summary為5),RIPv2為120,也即EIGRP計算的路由條目可信度要比RIPv2高;
5.工作層次不同,EIGRP可以看作工作在網路層,而RIPv2則是使用UDP 520的應用層(由於RIP使用UDP的關系也導致了其數據包的發送可靠性的保證相對較低,而EIGRP則有重傳等可靠性機制);
6.EIGRP支持非等價負載均衡(通過修改variance值),RIPv2僅為等價負載均衡;
7.EIGRP能夠定義不同的EIGRP AS,RIPv2不能且也不支持多進程;
8.根據演算法及運行原理的不同,EIGRP與RIPv2的timer也會有所不同,EIGRP主要為hello(5s/60s),holddown(15s/180s);RIPv2為Update(25.5~30s),invalid(180s),flush(240s),holddown(180s);而且EIGRP可根據拓撲表的後備路由對路由的失效進行快速的收斂,RIPv2則沒有這類表以及這些能力...

暫時總結這些,總的來說,RIP相對於EIGRP來說,應該應用在網路規模較小,擴展性要求不太高的網路..