最短路径算法Dijkstra算法在路由选择中的应用.pdf

计算机与网络 江苏联合职业技术学院徐州机电工程分院 王恒青 江苏联合职业技术学院徐州生物工程分院 宋如敏 [摘要】本文介绍了路由算法的设计目标以及种类，从最短路径算法的基本原理出发，举实例推演了Dijkma算法的 运算过程，且对最短路径树的找出过程进行了解释。 [关键词】路由选择最短路径Dijks吼算法最小时延 0．路由算法的设计目标 (1)初始化 路由算法在路由协议中起着至关重要的作用，采用何种算 令N表示网络结点的集合。先令N={1}。对所有不在N中 法往往决定了最终的寻径结果，因此选择路由算法一定要仔 的结点x，写出 细。通常需要综合考虑5个设计目标： …fZ(1，x)若结点x与结点1不直接相连 (1)最优化：指路由算法选择最佳路径的能力。 ‘q”一I∞ 若结点x与结点1不直接相连 (2)简洁性：算法设计简洁，利用最少的软件和开销，提供 在用计算机进行求解时，可以用一个比任何路径长度大得 最有效的功能。 多的数值代替。对于上述例子，可以使R(x)=99。 (3)坚固性：路由算法处于非正常或不可预料的环境时，如 (2)寻找—个不在N中的结点y，其R∽值为最小。把Y加入 硬件故障、负载过高或操作失误时，都能正确运行。最好的路由 器算法通常能在各种网络环境下都是可靠的。 中的较小的值去更新原有的R(x)值，即： (Cs-1) (4)快速收敛：收敛是在最佳路径的判断上所有路由器达 R(x)+．Min[R(x)，R劬+地，x)】 到一致的过程。收敛慢的路由算法会造成路径循环或网络中 (3)重复步骤2，直到所有的网络结点都在N中为止。 断。 表1是对图1的网络进行求解的详细步骤。可以看出，上 (5)灵活性：路由算法可以快速、准确地适应各种网络环 述的步骤(2谤乓执行了5次。表中带圆圈的数字是在每一次执行 境。 步骤(2)时所寻找的具有最小值的R劬值。当第5次执行步骤(2) 1．路由算法种类 并得出了结果后。所有网络结点都已包含在N之中，整个算法 路由算法按照种类可分为：静态和动态、单路和多路、平等 即告结束。 和分级、源路由和透明路由、域内和域问、链路状态和距离向 表1计算图1的网络的最短路径 量。 步骤 N R(2)R0) 尉4) R(5) R(6) 链路状态算法(也称最短路径算法)发送路由信息到互联 初始化 {1) 2 5 l 09, ∞ 网上所有的结点，然而对于每个路由器，仅发送它的路由表中 描述了其自身链路状态的那一部分。本质上说，链路状态算法 I {1,4l 2 4 ① 2 ∞ 只是将少量更新信息发送至网络各处。由于链路状态算法收敛 2 {1,4,5l 2 3 1 ② 4 快，通常不易产生路由循环。另一方面，链路状态算法要求有更 强的CPU能力和更多的内存空间，相对其他算法在实现时费用 3 11,2’45l② 3 l 2 4 会高些。不论在哪一种路由选择算法中都要用到求最短路径算 4 2 ③ 1 2 4 {1,2，3,4，51 法。最出名的求最短