（模式识别与智能系统专业论文）路由算法及过滤器部署算法的研究与分析.pdf

原创性声明 i i i i tt li ii t li ii il u ti ii y 18 3 3 5 7 3 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 学位论文作者：孝私咨日期：拜多月多e l 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。 根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门 或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学 可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印 或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文 或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。 保密论文在解密后应遵守此规定。 学位论文作者：亏鹏盈日期：啼年g 月乒日 摘要 摘要 随着网络规模的日趋增大，网络拓扑结构也越来越复杂，路由器在网络中 作用显得尤为重要，而运行其上的路由协议更是网络正常高效运行的关键，因 此，路由协议的性能是网络性能的重要决定因素之一。 本文着重分析了开放式最短路径优先协议( o s p f ) 的实现机制和性能特点， 以及过滤器部署算法的性能特点。本文的工作重点是对o s p f 从类型，拓扑的 l s a ，路由计算，邻居状态机，报文的交换，区域的划分，虚连接，与外部系统 的通信以及可靠性等方面进行了分析。其次是对过滤器部署算法( o f p ) 的分析和 研究，该算法通过对比边界上各种风险，移除有操作风险的边界，产生一条最 短虚拟路径，更加有效地部署过滤器的位置，给内部节点之间的信任网络提供 保护，并使用基于风险的方法对虚拟边界进行离线计算。最后，能把o f p 算法 和o s p f 算法有效融合，改变o s p f 算法的效率。 根据以上的分析，使用网络仿真软件o p n e t ，模拟了一个学校的网络模型， 设置了口地址，并配置了相应的流量。对融合后的算法的节点数目、连通度、 互连点等问题进行了实验分析；其次，选取了路由协议网络延时和负载特性两 个性能参数进行仿真，并对仿真结果进行了分析。最后通过对仿真结果的分析， 得到以下结论：融合算法与o s p f 算法相比在网络延时和负载方面有一定的优越 性，更能适合于规模大、拓扑结构复杂和性能要求高的网络环境。 关键字：路由算法o s p f 过滤器部署网络仿真数据包过滤器 a b s t r a c t a b s t r a c t w i mt h ei n c r e a s i n go fn e t w o r ks i z e ，t h en e t w o r kt o p o l o g yi sm o r ea n dm o r e c o m p l e x t 1 l er o l eo fr o u t e ri nt h en e t w o r ki sp a r t i c u l a r l yi m p o r t a n t t om a k es u r e n e t w o r kt of u nn o r m a l l ya n de f f i c i e n t l y , t h er o u t i n gp r o t o c o l sw h i c hr u n o nt o u t e r s a r ek e yf a c t o r s t h e r e f o r e ，t h ep e r f o r m a n c eo fr o u t i n gp r o t o c o l si so n eo fi m p o r t a n t f a c t o r st 1 1 a td e c i d et h en e t w o r ke f f i c i e n c y 1 1 h em a i nc o n t r i b u t i o no ft h e p a p e r i st h a tt h e p r o t o c o li m p l e m e n t a t i o n m e c h a n i s m sa n dp e r f o r m a n c ec h a r a c t e r i s t i c so fo s p fa n dt h e p e r f o r m a n c e c h a r a c t e r i s t i c so fo f pa l g o r i t h m 功ei m p o r t a n tw o r ko ft h i sp a p e ri sa n a l y s i ss o m e c h a r a c t e r i s t i c so fo s p f , s u c ha sp a t t e r n ，l s ao ft o p o l o g y , r o u t i n gc o m p u t a t i o n ， n e i g h b o rs t a t em a c h i n e ，a r e ad i v i s i o n ，av i r t u a lc o n n e c t i o n ，t r a n s m i t t i n go fr o u t i n g i d a t aa n dc o m m u n i c a t i o n 谢la sa n ds oo n n es e c o n di st oa n a l y s i st h eo f p a l g o r i t h m 1 1 1 ea l g o r i t h mc a nc o m p a r ew i t hk i n d so fr i s k si nt h eb o r d e ra n dr e m o v e t h ee d g eo fo p e r a t i o nr i s k ，t h ep a c k e tf i l t e r sc a nb ep l a c e di na ne f f i c i e n tw a yb y g e n e r a t i n gas h o r t e s tb o r d e r i tp r o v i d e sp e r f e c tp r o t e c t i o nf o rt r u s t e dn e t w o r k b e t w e e nt h ei n t e r n a ln e t w o r kn o d e s t h ef i n a l ，o f pa l g o r i t h ma n do s p fa l g o r i t h m c a ne f f e c t i v e l yi n t e g r a t ea n dt h ee f f i c i e n c yo fo s p fa l g o r i t h mc a l lb ei m p r o v e d b a s eo l lt h ea b o v ea n a l y s i sa n ds i m u l a t i o ns o f t w a r eo p n e t , ac a m p u sn e t w o r k s i m u l a t i o nm o d e li sd e s i g n e d a n dw ec o n f i g u r et r a f f i ca n di pa d d r e s s n ei m p r o v e d a l g o r i t h me x p e r i m e n t a la n a l y s i ss u c hi s s u e sa st h en u m b e ro fn o d e s ，c o n n e c t i v i t y , i n t e r c o n n e c t i o np o i n t s t h e n , t h et w op a r a m e t e rn e t w o r k1 0 a da n dc h a r a c t e r i s t i cd e l a y a r et e s t e da n da n a l y z e d b a s e do nt h ec o m p a r i s o nt h eo s p fa n di n t e g r a t e da l g o r i t h m ， ac o n c l u s i o nc a r lb ed r a w ：t h ei n t e g r a t e da l g o r i t h mh a sa na d v a n t a g eo fn e t w o r kd e l a y a n dl o a dc h a r a c t e r i s t i c s t h e r e f o r e ，i n t e g r a t e da l g o r i t h mi sa d a p tt ot h el a r g e ra n d c o m p l e xn e t w o r kw e l l k e yw o r d s ：r o u t i n gp r o t o c o l ，o s p f , f i l t e rp l a c e m e n t ，n e t w o r ks i m u l a t i o n ，p a c k e t f i l t e r - 1 1 目录 目录 摘要j i a b s t r a c t i i 图表清单v i 1 绪论1 1 1 研究的背景l 1 1 1 计算机网络技术的发展1 1 1 2 路由器技术3 1 1 3 路由算法5 1 2 论文的内容和工作 6 2 最短路径算法7 2 1 d i j k s t r a 算法7 2 1 1 d i j k s t r a 算法7 2 1 2 d i j k s t r a 算法分析。7 2 2 b e l l m a n f o r d 算法一8 2 2 1 b e l l m a n - f o r d 算法简介8 2 2 2 b e l l m a n - f o r d 算法分析8 2 3 s p f a 算法9 2 3 1 s p f a 算法简介。9 2 3 2 s p f a 算法分析：9 2 4 f l o y d - w a r s h a l l 算法一1 0 2 4 1 f l o y d - w a r s h a l l 算法简介lo 2 4 2 f i o y d - w a r s h a l l 算法分析1o 2 5 j o h n s o n 算法1 l 2 5 1 j o h n s o n 算法简介11 2 5 2 j o h n s o n 算法分析11 3 o s p f 的分析1 3 i i i 目录 3 1 通过l s a 描述网络的拓扑结构。1 4 3 1 1 1 - 0 拓扑的l s a 描述1 5 3 1 2 点对点网络的l s a 描述。1 6 3 1 3 非广播式多路访问网络的l s a 描述1 6 3 1 4 多路访问网络的l s a 描述1 7 3 2 路由计算18 3 3 邻居状态机和报文交换l9 3 4 d r 和b d r 2 2 3 5 域的划分和虚连接2 3 3 5 1 域问路由计算2 4 3 5 2 虚连接2 5 3 6 外部通讯2 6 4 过滤器部署算法2 8 4 1 优劣性分析2 8 4 2 数据包过滤器2 9 4 3 数学建模3l 4 3 1 网络模型：3l 4 3 2 o f p 数学模型3 2 4 4 过滤器的部署3 3 4 4 1 部署的约束条件。3 3 4 4 2 最短虚拟边界3 4 4 5 o f p 算法。：3 6 4 5 1 相关问题3 6 4 5 2 算法的提出3 7 4 6 o f p 与o s p f 的融合。3 8 5 仿真和结果分析4 0 5 1 仿真环境4 0 5 1 1 网络仿真概述4 0 5 1 2 通信仿真机制4 2 5 1 3 建模方法4 6 - 目录 5 2 融合算法性能分析4 8 5 2 1 节点数目问题4 9 5 2 2 连通度问题5 0 5 2 3 互连点问题5 0 5 3 o s p f 与融合算法的对比分析5 2 5 3 i 延迟分析。5 2 5 3 2 负载分析。5 2 6 总结与展望5 4 6 1 总结5 4 6 2 展望5 4 参考文献：5 6 致谢5 9 个人简历、在学期间发表的学术论文与研究成果6 0 v 图表清单 图表清单 图1 1 路由器在o s i 中的位置3 图1 2 路由器典型组成。4 图1 3 路由器工作原理图5 图3 1o s p f 数据报格式1 4 图3 2 网络拓扑结构二1 5 图3 3 网络的拓扑结构1 8 图3 4 每台路由器的链路状态数据库1 9 图3 5 由链路状态数据路得到的带权有向图1 9 图3 6 每台路由器分别以自己为根节点计算出的最小生成树1 9 图3 7 报文交互过程2 l 图3 8 网络的拓扑结构2 2 图3 9 没有选举d r 时邻接关系2 3 图3 10 选举d r 后的邻接关系2 3 图3 1 1 区域间的路由计算2 4 图3 12 虚连接2 6 图3 1 3o s p f 与外部自治系统的通信2 7 图4 1 过滤器部署和路由故障图a 3 0 图4 2 过滤器部署和路由故障图b 3 1 图4 3 网络拓扑图3 5 图4 4 数据包路由图3 5 图4 5 边界去除图3 5 图4 6 过滤器放置图3 6 图5 1 仿真流程图4 2 图5 2 输入流中的排队图4 4 图5 3 包传递4 4 图5 4 仿真流程图4 6 图5 5 节点数量与连接点上过滤器均值关系图5 0 图5 6 连通度5l 图5 7 节点内部互联点均值与互联点上过滤器均值关系图5 l 图5 8 延时对比图5 2 图5 9 负载对比图5 3 v i 1 绪论 1绪论 1 1 研究的背景 本文课题来源是河南省杰出人才创新基金资助项目“智能化网络入侵防御 系统关键技术研究”( 项目编号：0 7 4 2 0 0 5 1 0 0 1 3 ) 的重要组成部分。 2 1 世纪的重要特征就是数字化、网络化和信息化，它是一个以网络为核心 的信息时代。当今世界经济正在从工业经济向知识经济、信息经济转变，而知 识经济的两个重要特点就是信息化和全球化。要实现信息化和全球化，完善的 网络是重要条件之一。因此，网络已经成为信息社会的命脉和发展经济的重要 基础。同时，网络对社会生活的很多方面和社会经济的发展已经产生了不可逆 转的影响，已经成为推动生产力发展的巨大动力。 1 1 1 计算机网络技术的发展 随着计算机技术的飞速发展和通信技术的进步，计算机网络也应运而生， 一方面，通信网络为计算机之间的数据传递和交换提供了必要的手段，另二方 面，数字计算技术的发展又渗透到通信技术中，提高了通信网络的各种性能。 早在上世纪6 0 年代【l j ，保罗巴伦( p a u lb a r a n ) 、伦纳德克兰罗克( l e o n a r d k l e i m o c k 、唐纳德- 戴维斯( d o n a l dw a t t sd a v i e s ) 就提出了i n t e r n e t 的设计理念， 该理念主要由分组交换( p a c k e ts w i t c h i n g ) 、存储转发( s t o r ea n df o r w a r d ) 、分布式 网络( d i s t r i b u t e dn e t w o r k ) 等理论组成，这些理论影响深远，至今还是i n t e r n e t 的 核心设计理念。计算机网络的发展大致分为以下几个阶段： 第一阶段是上世纪6 0 年代末到7 0 年代初，为计算机网络发展的起步阶段。 其典型代表就是美国国防部高级研究计划署( d a r p a ，d e f e n s ea d v a n c e d r e s e a r c hp r o j e c t sa g e n c y ) 为新型计算机网络实验而建立了a r p a n e t ，这就是今 天i n t e m e t 的前身。首次实现了由通信网络和资源网络融合，构成了真正的计算 机网络系统，此举有着里程碑式的意义，标志计算机网络的真正诞生。当时， 设计这一网络的最初目的是当网络中一部分因为战争等特殊原因遭到破坏时， 网络的其他部分仍能正常运行。 第二阶段是上世纪7 0 年代中后期，即局域网络( l a n ) 发展的重要阶段，其 1 绪论 主要特征为：局域网络作为一种新型的计算机体系结构开始进入产业部门。 a r p a n e t 规模的扩大以及网络多样化促使a r p a n e t 进行网络互连的研究。可用 于异构网络的t c p i p 协议也成功研制并正式投入使用，并且，由于t c p i p 网 络的灵活性、开放性、易用性，可以很轻松的延伸网络，因此，各种各样的网 络通过t c p i p 协议可以有机的结合起来，一个基于t c p i p 的i n t e r n e t 基本上形 成。这些网络的成功实现，不仅标志着l a n 的产生，还对形成以太网及环网起 到推动作用。同时，随着h l t e r n e t 的发展，基于网络的各种应用也逐渐丰富起来。 1 9 7 1 年，雷汤姆林森( r a y t o m l i s o n ) 实现了基于互联网络接发消息的电子邮件程 序。1 9 7 8 年，沃德克里斯琴森( w a r dc h r i s t i a n s e n ) 和兰迪瑟斯( r a n d ys e u s s ) 开发 了第一个计算机公告牌系统( b b s ，c o m p u t e r i z e db u l l e t i nb o a r ds y s t e m ) ，这是第 一个民众参与的试验系统。1 9 7 9 年，理查德巴 ( r i c h a r db a t t l e ) 和罗伊杜伯萧 ( r o yt r u b s h a w ) 开发了第一个多人参与的m u d ( m u l t iu s e rd i m e n s i o n ) 游戏，开创 了一个新的游戏娱乐平台。 第三阶段是上世纪8 0 年代，是计算机局域网络的发展时期。其主要特征是： 从硬件上实现了局域网络，以及i s o 的开放系统互连通信模式协议的能力。计算 机局域网及其配套产品的集成，使得局域网与各类主机互连、局域网与局域互 连，以及局域网与广域网互连的技术日臻完善，网络的互连进一步推动了互联 网的用户。据有关统计表明，从1 9 8 8 年开始，i n t e r n e t 的用户也一直以每年翻一 番的速度飞速增长，展现出i n t e r n e t 旺盛的生命力和巨大的潜力。 第四阶段是上世纪9 0 年代初至今是网络日新月异的阶段，其主要特征是： 计算机网络化，协同计算能力发展以及全球网络互连的盛行。1 9 9 0 年，提姆伯 纳斯李( t i mb e r n e r s l e e ) 提出了万维网( w w w w o r l dw i l dw e b ) 计划，目的是建立 一个“可描述的多媒体系统 ，这对互联网来说影响更是巨大。同时，超文本标 示语言( h t m l ，h y p e r t e x tm a r k u pl a n g u a g e ) 、超文本传输协议( h t t p ，h y p e r t e x t t r a n s f e rp r o t o c 0 1 ) 、统一资源定位( u r l ，u n i f o r mr e s o u r c el o e a t o r ) 等必需的基础 技术也相继被开发出来。实际上，并没有吸引人们的注意力，没有取得预期的 轰动效果，直到1 9 9 3 年，马克安德森( m a r c a n d r e e s s e n ) 发明了世界上第一个多 媒体浏览器m o s a i c 。m o s a i c 让图像的显示变为现实，让人们发现万维网的实时 性和低成本，与传统印刷业相比，具有无可比拟的优越性，因此成为信息发布 和信息交换最便捷方式。于是，万维网上的通信量以指数级的速度的上升，这 一爆炸性的增长标志这i n t e r n e t 的真正起飞。 2 1 绪论 时至今日，i n t e r n e t 上已经连了千万台计算机，把地球的各个角落连接在一 起，形成了“地球村 ，可以毫不夸张的说，i n t e m e t 已经影响到人类生产和生活 的各个方面，它已经不再是一门单纯的技术，而是成为了一种世界性的文化， 而且这种文化已经融入了人类社会的各个角落，同人类的进步息息相关。 1 1 2 路由器技术 计算机网络的蓬勃发展，跟路由器【2 h 3 】有着密切的关系，它是网络互连的桥 梁，可以被看作是一种专用的计算机。运行在路由器上的各种路由协议，也是 网络正常运转的重要条件之一。在i n t e m e t 中，p 协议己经成为古统治地位的组 网协议，实际上，i n t e m e t 是一个庞大的口网络，其性质己经不是最初的的研究 模型，而是覆盖全世界的数字通信网络。当数据从i n t e r n e t 某一地点向另一个地 点转发时，其转发的路径和时间要由路由器来决定。决定路由器如何选择传输 路径的协议，称为路由选择协议。对i n t e r n e t 组织结构发生类似中断、路由器崩 溃等的变化时，这些协议必须做出快速有效的反应。 路由器 交换机 集线器 图1 1 路由器在o s i 中的位置 路由器是一种用于网络互连的计算机设备，它工作在o s i 参考模型的第三 层即网络层，为不同的网络设备之间报文寻径并存储转发，如上图1 1 所示。一 个典型的路由器应有以下四种四部分组成：输入端口、输出端口、交换网络和 网络处理器，如下图1 2 所示。路由器必须具备两个或两个以上的接口，用于连 接不同的网络；路由协议至少实现到网络层，因为只有理解到网络层才能与网 - 3 - i 绪论 络层通信，路由器的存在才有意义；路由器还至少要支持两种以上的子网协议， 以方便异种网络互联；同时，路由器还应具有存储、转发、寻径、缓存等功能， 以实现速率匹配与路由寻径。 图1 2 路由器典型组成 早期的路由器中，路由的选择策略是通过网络工作人员通过设置来实现的 的，这种路由策略被称做静态路由。随着网络节点的迅猛增加，拓扑结构日益 复杂，静态路由已经不能满足需求，于是，能够适应网络拓扑变化的动态路由 协议应运而生。 在口网络中，以动态路由协议的作用为标准，可以将动态路由协议分为两 种：外部网关协议( e g p , e x t e r i o rg a t e w a yp r o t o c 0 1 ) 和内部网关协议( i g p , i n t e r i o r g a t e w a y p r o t o c 0 1 ) 。把用于自治系统内部的各个路由器之间的路由协议的集合， 称为内部网关协议，例如r i p 和o s p f 等。把用于自治系统之间的各个路由器之 间的路由协议的集合，称为外部网关协议。目前，边界网关协议( b g p , b o r d e r g a t e w a yp r o t o c 0 1 ) 己经取代外部网关协议族。 把动态路由协议所使用的算法为根据，动态路由协议又可以分为三种：第 一种路由协议是基于距离矢量路由算法，例如r i p 协议等；第二种路由协议是 基于链路状态的，例如i s i s ( i n t e r m e d i a t es y s t e mt oi n t e r m e d i a t es y s t e m r o u t i n gp r o t o c 0 1 ) 协议、o s p f 协议等；第三种路由协议是基于路径矢量路由算 法的，例如b g p 协议。 路由器中时刻维持着路由表，所有报文的发送和转发都通过查找路由表从 相应端口发送。这张路由表可以是静态的，即由人工手动配置的：也可以是动 态路由协议产生的。其工作原理如下：物理层从路由器的一个端口收到一个报 4 i 绪论 文，上送到数据链路层。数据链路层去掉链路层封装，根据报文的协议域上送 到网络层。网络层首先看报文是否是送给本机的，若是，则去掉网络层封装， 送给上层。若不是，则根据报文的目的地址查找路由表，若找到路由，将报文 送给相应端口的数据链路层，数据链路层封装后，发送报文。若找不到路由， 报文丢弃。具体过程如下图所示： 图1 3 路由器工作原理图 1 1 3 路由算法 路由算法是指路由问题的求解方法和与步骤，在路由器中起着至关重要的 作用。路由算法通常以优化、简单、健壮、稳定、快速收敛、灵活性等作为设 计的目标。 优化指路由算法选择最佳路径的能力，根据m e t r i c 的值和权值来计算。例 如一种路由算法可能使用跳数和延迟，但可能跳数的权值要小些。当然，路由 协议必须严格定义计算m e t r i c 的算法。 路由算法也应该设计得尽可能的简单，换句话说，路由协议必须高效地实 现其作用，其各方面开销应减少到最低限。实现路由算法的软件必须运行在物 理资源有限的计算机上时，简单高效更是显得重要。 路由算法的健壮是指当出现不正常或不可预见事件的情况下，像网络故障、 过负荷等情况是，算法仍然能正常处理。主要是因为路由器位于网络的连接点， 是网络的传输枢纽，它们不正常工作会带来严重的后果。 此外，路由算法必须能快速收敛，收敛是所有路由器对最佳路径达成一致 5 1 绪论 的过程。当网络出现故障而导致路径不可用时，路由器通过网络分发路由更新 信息，以便最优路径的再计算，并使所有路由器最终达成共识。收敛速度慢的 路由算法可能会产生路由环或网路中断等问题。 路由算法还应该是灵活的，即它们能快速、准确地适应不同的网络环境。 例如某网段出现故障不能正常工作后，路由算法就对通常使用该网段的路径将 快速选择次佳的路径。 另外，路由算法也是相互区分的。各路由算法的区别点包括：静态与动态、 单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状 态与距离向量等阡1 7 。 1 2 论文的内容和工作 本文首先介绍了网络的发展历程，以及其发展现状。对网络的重要中继设 备路由器的发展过程、路由器的基本结构和作用都做了仔细的介绍，并着重分 析了路由器的工作原理。接着最开放式最短路径优先协议即o s p f 进行了深入的 分析，包括算法如何用l s a 描述周围的网络拓扑结构，s p f 路由计算的过程， 邻居状态机和报文交互过程，d r 和b d r 的选举，网络区域的划分，以及与外 部网络的通讯原理等。接着分析了o f p 算法的原理，介绍的算法的设计思想， 算法的数学建模过程，算法的实现等。并给予o p n e t 软件对算法的主要参数进 行了反复的试验，对试验结果作了仔细的分析和对比。最后，对本论文做了总 结和展望。 作者主要做了以下工作： ( 1 ) 对网络和路由器知识的总结； ( 2 ) 对o s p f 算法进行了分析研究； ( 3 ) 对o f p 算法进行了分析研究； ( 4 ) 用网络仿真软件o p n e t 设计了相应的网络仿真环境； ( 5 ) 对算法的主要参数进行试验，并对实验结果进行了对比分析。 - 6 2 最短路径算法 2 最短路径算法 最短路径问题是路由研究中的重要问题，也是图论研究中的一个经典算法 问题，旨在寻找图( 由结点和路径组成的) 中两结点之间的最短路径。本章节 主要介绍单源路径算法和节点对间的最短路径算法【8 】1 9 。所谓单源路径算法就是 给定一个加权有向图g = 代e ) ，其中每条边的权是一个非负实数。另外，还给定 v 中的一个顶点，称为源。现在计算从源到所有其他各项点的最短路径长度。这 里的长度是指路上各边的权之和。最常用的路径算法有：d i j k s t r a 算法、s p f a 算法、b e l l m a n f o r d 算法。所谓节点对间的最短路径算法就是给定一个有向图 g = e ) ，其中有的边的权为负，不能使用d i j k s t r a 算法，而使用b e l l m a n - f o r d 算法时，但其算法复杂度又太大，因此，针对这种情况提出的算法，比较经典 的算法有f l o y d 【- w a r s h a l l 算法、j o h n s o n 算法等。算法解决的主要问题包括：1 确定起点的最短路径问题，即起始结点已知，求其最短路径的问题。2 确定终点 的最短路径问题，即终结结点已知，求最短路径的问题。但是，值得注意的是 在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所 有路径方向反转的确定起点的问题。3 确定起点和终点的最短路径问题，即起点 和终点均已知，求两结点之间的最短路径。4 全局最短路径问题，即求图中所有 的最短路径。下面就这些算法做简单的介绍。 2 1 d i j k s t r a 算法 2 1 1 d i j k s t r a 算法 迪杰斯特拉( d i j k s 昀) 算法【1 0 1 - 1 “1 是最典型的单源最短路径算法之一，用于计 算一个节点到其他所有节点的最短路径。动态路由协议o s p f 中就用到了d i j k s t r a 算法来为路由计算最短路径。主要特点是以起始点为中心向外层层扩展，直到 扩展到终点为止。d 啦s 仃a 算法为正向搜索算法，即起点已知，通过正向搜索来 计算最短路径，其时间复杂度是o ( n 2 ) 。 2 1 2 d i j k s t r a 算法分析 其主要过程是：将顶点集v 分成s 集合和v - s 集合。s 集合包含的点都是 7 2 最短路径算法 已经计算出最短路径的点，开始时只包含源节点；v - s 集合包含那些未确定最短 路径的点。然后从v - s 集合中选取项点w ，w 满足经过s 集合中任意顶点v 到w 的路径最短，如此反复，直到v - s 变空集为止。设g 为加权有向图，v 是所有 结点的集合，e 是所有路径的集合，s 表示源点，n 表示v 中所有结点的数目， w 【l l ，v 】表示从结点u 到结点v 的路径的权值。d 【v 】表示从源点s 出发到结点v 的 最短路径的距离，或者说是从s 到v 所有的路径中权值的最小值。 算法描述如下： s t e p l ：初始化； s t e p 2 ：s4 - - v 0 ； s t e p 3 ：d v o 4 - - 0 ； s t e p 4 ：对于每一个1 ，y ，则研y 】4 - - ( v o ，d ； s t e p 5 ：当s v 时，则开始； s t e p 6 ：在y s 中选择一个顶点w ，保证在点w 的d 【叫最小； s t e p 7 ：增加w 到s ； s t e p s ：对于y s 中的每一个v ，则d 【1 ，】卜m i n ( d v ，d 【w 】+ ，( w ，1 ，) ) ； s t e p 9 ：结束。 2 2b e l l m a n f o r d 算法 2 2 1 b e l l m a n f o r d 算法简介 b e l l m a n f o r d 算法【n 】与d i j k s t r a 算法的用途是相同的，都是用于求解单源点 得最短路径问题。但是，该算法与d i j k s t r a 算法又有两点不同：1 b e l l m a n f 0 r d 算法不仅可求解边权均非负的问题外，还可以解决边权为负的问题，因此 b e l l m a n f o r d 算法的应用面要更加广泛一些。但是，b e l l m a n f 0 r d 算法时间复杂 度为o ( v e ) ，其中v 为图的结点数，e 为图的边数，其算法的时间复杂度比d i j k s t r a 算法的高。2 b e l l m a n f o r d 算法为反向搜索算法，即终点已知，需要反向计算来 找到最短路径。 2 2 2b e l l m a n f o r d 算法分析 算法过程首先进行初始化，估计除源点外的所有顶点的最短距离；其次迭 代求解，反复对边集e 中的每条边进行松弛操作，使得顶点集v 中的每个顶点 8 2 最短路径算法 v 的最短距离估计值逐步逼近其最短距离，最后检验负权回路，判断边集e 中的 每一条边的两个端点是否收敛。设g 为加权有向图，v 是所有结点的集合，e 是所有路径的集合，s 表示源点，n 表示v 中所有结点的数目，w 【u ，v 】表示从结 点u 到结点v 的路径的权值。d 【v 】表示从源点s 出发到结点v 的最短路径的距离， 或者说是从s 到v 所有的路径中权值的最小值，p 【v 】表示节点v 的父结点。 算法描述如下： s t e p l ：对于每一个1 ，v ； s t e p 2 ：o v 】竽o o ，p l y 】= n u l l ； s t e p 3 ：d s 】：- 0 ，尸 s 】：= n u l l ； s t e p 4 ：循环( 1 ) - ( 3 ) 步骤n 1 次； s t e p 5 ：对于每一条路径 ，) e ； s t e p 6 ：如果d u 】+ w ”，1 ，】 d 【 ，】； s t e p l o ：则终止，返回“找到负环路； s t e p l l ：返回。 2 3s p f a 算法 2 3 1s p f a 算法简介 最短路径快速算法( s p f a ，s h o r t e s tp a t hf a s t e ra l g o r i t h m ) 算法【1 2 】也是一种单 源最短路径算法，是西南交通大学段凡丁于1 9 9 4 年发表的。该算法实际上是 b e l l m a n f o r d 算法的一种队列实现，利用了每个点不会更新次数太多的特点发明 的，减少了大量的不必要的冗余计算，降低了算法的复杂度，提高了算法的效 率。 2 3 2s p f a 算法分析 s p f a 算法流程如下：用一个先进先出的队列来存放被成功松弛的顶点，初 始时，源点s 入队。当队列不为空时，取出队首顶点，对它的邻接点进行松弛。 一9 2 最短路径算法 如果某个邻接点松弛成功，且该邻接点不在队列中，则将其入队。经过有限次 的松弛操作后，队列将为空，算法结束。为了方便查找某个顶点的邻接点，图 采用临界表存储。设g 为加权有向图，v 是所有结点的集合，e 是所有路径的 集合，s 表示源点，1 1 表示v 中所有结点的数目，d 【v 】表示从源点s 出发到结点 v 的最短路径的距离，或者说是从s 到v 所有的路径中权值的最小值，除此之外， s p f a 算法的实现，还需引入一个先进先出的队列q u e u e ，和一个标记数组m a r k 用来表示顶点是否在队列q u e u e 中。 算法描述如下： s t e p l ：初始化单源节点( gs ) s t e p 2 ：初始化队列q ； s t e p 3 ：将源点s 加入队列q ； s t e p 4 ：当q 为非空时； s t e p 5 ：把u 0 的路由器都认为自己是d r 。选举的原则是比较各 路由器的研o f i t y ，如果研o r i 锣的值相等，则选择r o u t e rl d 大的作为d r 。d r 一旦选举产生，除非该d r 出现故障或者损坏，否则是不会更换的。d r 选举产 生后，b d r ( b