这里讨论下RIP和OSPF的基本算法,在CISCO课程中讨论RIP和OSPF的区别有不少,但是回溯源头,它们理论算法里面的原理差不多,比较大的区别主要有三点
1.Bellman-ford的链路距离是估算的,Dijkstra是传输链路距离给邻居的。PS:这就说明了为什么RIP要采用跳数,而OSPF用的是cost,也就是带宽作为主要参数,因为估计在具体实现中是不大可行的,故采用不同的具体度量值。
2.Bellman-ford的持续进行链路距离的计算,而Dijkstra只进行一次计算就可以了,这点可能表达的不是太准确,大致意思
3.还有点就是Bellman-ford是不停在从目标出发所有相邻的节点上计算最小的路径,然后往前推进,而Dijkstra是从最小标记的节点往前推进,这里看后面解释:
这里用图例解释下(直接抓的是jean walrand的书上的图)
首先这是Bell-man算法的一个收敛图,图中解释了一个收敛的过程。
Bell-man算法采用节点间链路长度估算的方式,公式为L( i ) = min { d( i , j )+ L( j ) },其中d( i , j ) 表示节点 i 到 j 的链路长度,L( j )是从节点 j 收到的最短长度的估算。
即每一个节点初始时候以∞作为标识,从目标点向源点收敛,目标点作为0,然后相邻的标记为链路长度,当出现到目标点更短的链路长度时候,重新进行标记,直到到达源,从而得出最短的路径,每个节点都向它的邻居节点发送到所有节点的估算值。
这是Dijkstra算法的收敛图,具体过程有点相似Bell-man。
首先还是从根(也就是目标)出发,根标记为0,其他节点标记为∞,然后按照标号最小的走,比如第一步2最小,然后从2往前走,其相邻节点原来是5,现在由于2+2=4,故更新下,然后再比较所有节点里面,标记最小的是3,然后从3走,发现11,大了,然后返回最小的4继续走,这样一路一路从最小标记的节点往相邻走,最终达到收敛。
PS:这里还有点区别在于Bell-man一直从相邻节点往前走,然后进行比较,把节点的标记逐步最小往前推进,从前往后看,每一个节点都是相对最小的。而Dijkstra是每次从标记值最小的节点往前走,每次都是走最小,所以它走的顺序和Bell-man的顺序是不一样的。
分享到:
相关推荐
Bellman-Ford算法与差分约束系统
bellman-ford算法的C++实现,邻接表
Java实现的Dijkstra算法和Bellman-ford算法代码,带UI界面,已封装的可执行jar文件,以及源代码。
NULL 博文链接:https://128kj.iteye.com/blog/1715073
Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E),Dijkstra 算法要求图 G 中边的权值均为非负,而 Bellman-Ford 算法能适应一般的情况(即存在负权边的情况)。一个实现的...
分步介绍了bellman-ford算法的详细步骤和分析方法,最后给出了例题进行了说明
NBFNet将广义Bellman-Ford算法参数化,采用3个神经单元,分别对应边界条件、乘法算子和求和算子。NBFNet是非常通用的,涵盖了许多传统的基于路径的方法,并且可以应用于同构图和多关系图(例如,知识图)在转换和归纳...
基于Bellman-Ford最短路径算法的演示程序 提供源代码
以下是Bellman-Ford算法的基本讲解: 算法步骤: 初始化:将源点到各个顶点的距离初始化为无穷大,源点到自身的距离为0。 松弛操作:对图中的每一条边进行V-1次松弛操作,其中V是图中顶点的数量。松弛操作的目的...
最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(CC++),希望对你能有所帮助!
Bellman-Ford模板 Bellman-Ford模板 Bellman-Ford模板 Bellman-Ford模板 Bellman-Ford模板
图论- 最短路- Bellman-Ford 算法与 SPFA.rar
bellman-ford算法bellman-ford算法bellman-ford算法bellman-ford算法bellman-ford算法bellman-ford算法
Bellman-ford算法.ppt
Bellman-Ford算法.docx
Bellman-Ford——解决负权边
经典算法书籍《算法导论》之图算法章节中Bellman-ford算法的C++版。
Bellman-Ford算法(单源最短路径) 矩阵是在main函数里输入的 可以处理带负权的图
%%贝尔曼-福特算法是针对边的算法,而迪杰斯特拉算法是针对点的算法 %%举个明显的列子: % 迪杰斯塔拉:假设从a到b的距离10,那么从b出发到a的距离也是10 % 贝尔曼-福特:假设从a到b的距离10,即a->b的边是10。但...
Bellman Ford算法的并行实现