贝尔曼福德算法

‘壹’ 最短路径算法

最短路径的算法主要有三种：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来说,应该应用在网络规模较小,扩展性要求不太高的网络..