最短路径算法dijkstra算法在路由选择中的应用

《最短路径算法dijkstra算法在路由选择中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据计算机与网络最短路径算法Dijkstra算法在路由选择巾的应用江苏联合职业技术学院徐州机电工程分院王恒青江苏联合职业技术学院徐州生物工程分院宋如敏[摘要】本文介绍了路由算法的设计目标以及种类，从最短路径算法的基本原理出发，举实例推演了Dijkma算法的运算过程，且对最短路径树的找出过程进行了解释。[关键词】路由选择最短路径Dijks吼算法最小时延0．路由算法的设计目标路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终的寻径结果，因此选择路由算法一定要仔细。通常需要综合考虑5个设计目标：(1)最优化：指路由算法选择最佳路径的能力。(2)简洁性：

2、算法设计简洁，利用最少的软件和开销，提供最有效的功能。(3)坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。最好的路由器算法通常能在各种网络环境下都是可靠的。(4)快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。收敛慢的路由算法会造成路径循环或网络中断。(5)灵活性：路由算法可以快速、准确地适应各种网络环境。1．路由算法种类路由算法按照种类可分为：静态和动态、单路和多路、平等和分级、源路由和透明路由、域内和域问、链路状态和距离向量。链路状态算法(也称最短路径算法)发送路由信息到互联网上所有的结点，然而对于每个

3、路由器，仅发送它的路由表中描述了其自身链路状态的那一部分。本质上说，链路状态算法只是将少量更新信息发送至网络各处。由于链路状态算法收敛快，通常不易产生路由循环。另一方面，链路状态算法要求有更强的CPU能力和更多的内存空间，相对其他算法在实现时费用会高些。不论在哪一种路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman—Ford算法和Dijks缸a算法。这两种算法的思路不同，但得出的结果是相同的。本文仅介绍Dijkstra算法。2．Dijkstra算法Dijl妇算法的已知条件是整个网络拓扑和各链路的长度。应当注意到，若将已知的各链路长度

4、改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。下面以图1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便举例起见，设源结点为结点1。然后一步一步地寻找，每次找—个结点到源结点的最短路径，直到把所有的点都找到为止。5图I求最短路径算法的网络令R(x)为源结点(记为结点1)到某个结点x的距离，它就是从结点I沿某一路径到结点x的所有链路的长度之和。再地j)为结点i至结点j之间的距离。整个算法只有以下两个部分：(1)初始化令N表示网络结点的集合。先令N={1}。对所有不在N中

5、的结点x，写出⋯fZ(1，x)若结点x与结点1不直接相连‘q”一I∞若结点x与结点1不直接相连在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替。对于上述例子，可以使R(x)=99。(2)寻找—个不在N中的结点y，其R∽值为最小。把Y加入到N中。然后对所有不在N中的结点x，用[R(x)，R劬+地，x)]中的较小的值去更新原有的R(x)值，即：R(x)+．Min[R(x)，R劬+地，x)】(Cs-1)(3)重复步骤2，直到所有的网络结点都在N中为止。表1是对图1的网络进行求解的详细步骤。可以看出，上述的步骤(2谤乓执行了5次。表中带圆圈的数字是在每一次执行

6、步骤(2)时所寻找的具有最小值的R劬值。当第5次执行步骤(2)并得出了结果后。所有网络结点都已包含在N之中，整个算法即告结束。表1计算图1的网络的最短路径步骤NR(2)R0)尉4)R(5)R(6)初始化{1)25l09,∞I{1,4l24①2∞2{1,4,5l231②4311,2’4'5l②3l24{1,2，3,4，512③1245{1,2,3，4,5，6)23l2④3．最短路径树现在我们对以上的最短路径树的找出过程进行一些解释。因为选择了结点1为源结点，因此一开始在集合N中只有结点Z。结点1只和结点2，3和4直接相连，所以在初始化时，在R(2)，R(3)和R(4)

7、下面填入结点1到这些结点相应的距离，而在R(5)和R(6)下面填入∞。下面执行步骤1。在结点1以外的结点中，找出—个距结点l最近的结点y，这应当是y----4，因为在R(2)，R(3)和R(4)中，R(4)=1，它之值最小。于是将结点4加入到结点集合N中。这时，我们在步骤1这一行和R(4)这一列下面写入①，数字1表示结点4到结点l的距离，数字1的圆圈表示结点4在这个步骤加入到结点集合N中了。接着就要对所有不在集合N中的结点(即结点2，3，5和6)逐个执行(Gs-1)式。对于结点2，原来的R(2)--2。现在R劬+ZO，x)=R(4)+l(4’2)=1+2--3>