因特网的路由选择算法
摘要：路由选择协议是路由器用来完成路由表建立和路由信息更新的通信协议。路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终寻径结果。本文主要讨论设计路由算法应具有的原则以及第一个得到广泛使用的路由算法RIP和最短路径Dijkstra算法。
1 路由算法概述
1.1 路由算法的特点
路由选择协议的核心就是路由算法，即需要何种算法来获得路由表中的个项目。一个理想的路由算法应该具有如下特点。
（1）算法必须是正确的和完整的。这里，“正确”的含义是指沿着各路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。
（2）算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。。
（3）算法应能适应通信量和网络拓扑的变化，这就是说要有自适应性。当网络中的通信量发生变化时，算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时的改变路由。有时称这种自适应性为“稳健性”（robustness）。
（4）算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使得出的路由不停的变化。
（5）算法应是公平的。路由选择算法应对所有用户（除了少数优先级高的用户）都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显的不符合公平性的要求。
（6）算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法，但这并不是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
一个实际的路由选择算法，应该尽可能接近于理想的算法。在不同的应用条件下，对以上提出的六个方面也可有不同的侧重。
1.2 路由算法的分类
路由选择算法是个非常复杂的问题，因为它是网络中的所有节点共同协调工作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络中出现了某些故障。此外，当网络发生拥塞时，就特别需要有
能缓解这种拥塞的路由选择策略，但恰好在这种条件下，很难从网络中的各结点获得所需的路由选择信息。
倘若从路由算法能否随网络的通信量或拓扑自适应的进行调整变化来划分，则只有两大类，即静态路由选择策略与动态路由选择策略。静态路由也叫做非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。对于很简单的小网络，完全可以采用静态路由选择，用人工配置每一条路由。动态路由选择也叫做自适应路由选择，其特点是能较好的适应网络状态的变化，但实现起来较为复杂，开销也比较大。因此，动态路由选择适用于较复杂的大网络。
1.3 路由算法的度量标准
路由算法使用了许多种不同的度量标准去决定最佳路径。复杂的路由算法可能采用多种度量来选择路由，通过一定的加权运算，将它们合并为单个的复合度量、再填入路由表中，作为寻径的标准。
通常所使用的度量有：路径长度、可靠性、时延、带宽、负载、通信成本等。
路径长度是最常用的路由metric。一些路由协议允许网管给每个网络链接人工赋以代价值，这种情况下，路由长度是所经过各个链接的代价总和。其它路由协议定义了跳数，即分组在从源到目的的路途中必须经过的网络产品，如路由器的个数。
可靠性，在路由算法中指网络链接的可依赖性（通常以位误率描述），有些网络链接可能比其它的失效更多，网路失效后，一些网络链接可能比其它的更易或更快修复。任何可靠性因素都可以在给可靠率赋值时计算在内，通常是由网管给网络链接赋以metric值。
路由延迟指分组从源通过网络到达目的所花时间。很多因素影响到延迟，包括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间网络链接的拥塞程度以及物理距离。因为延迟是多个重要变量的混合体，它是个比较常用且有效的metric。
带宽指链接可用的流通容量。在其它所有条件都相等时，10Mbps的以太网链接比64kbps的专线更可取。虽然带宽是链接可获得的最大吞吐量，但是通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好。例如，如果一条快速链路很忙，分组到达目的所花时间可能要更长。
负载指网络资源，如路由器的繁忙程度。负载可以用很多方面计算，包括CPU使用情况和每秒处理分组数。持续地监视这些参数本身也是很耗费资源的。
通信代价是另一种重要的metric，尤其是有一些公司可能关系运作费用甚于性能。即使线路延迟可能较长，他们也宁愿通过自己的线路发送数据而不采用昂贵的公用线路。
2 典型的路由算法
2.1 内部网关协议RIP
路由信息协议RIP（Routing Information Protocol）是内部网关协议IGP中最先得到广泛应用的协议。它最初于1980年使用在XNS中，现在主要应用在Unix 中。
RIP是一种分布式的基于距离向量的路由选择协议，是因特网的标准协议，其最大优点就是简单。RIP属于一类被称为距离矢量路由的路由算法，即达到目的地的最佳路径是条数最少的路径，然而，最佳路径也可以由除跳数以外的其他度量指标决定。
RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录（因此，这是一组距离，即“距离向量”）。
RIP不能在两个网络之间同时使用多条路由。RIP选择一条具有最少路由器的路由（即最短路由），即使还存在另一条高速（低时延）但路由器较多的路由。
RIP具有一下特点：
（1）仅和相邻路由器交换信息。如果两个路由之间的通信不需要经过另一个路由器，那么这两个路由器就是相邻的。RIP协议规定，不相邻的路由器不交换信息。
（2）路由器交换的信息是当前本路由器所知道的全部信息，即自己的路由表。也就是说，交换的信息是：“我到本自治系统中所有网络的（最短）距离，以及到每个网络应经过的下一跳路由器”。
（3）按固定的时间间隔交换路由信息，例如，每隔30秒。然后路由器根据收到的路由信息更新路由表。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。
RIP的缺点：
超过15跳便无法到达。
协议以跳数，即报文经过的路由器个数为衡量标准，并以此来选择路由，这一措施欠合理性。
该路由协议应用到实际中时，很容易出现“计数到无穷大”的现象，这使得路由收敛很慢。
RIP采用的是D-V算法(距离矢量路由算法)，下面是D-V算法的优缺点。
优点：算法简单。
缺点：交换的路径信息量大
路径信息传播慢，使得路径信息可能不一致。
收敛速度慢，存在无穷计算问题。
不适合大型网络。
随着OSPF和IS-IS的出现，许多人认为RIP已经过时了。但事实上RIP 也有它自己的优点。对于小型网络，RIP就所占带宽而言开销小，易于配置、管理和实现，并且RIP还在大量使用中。但RIP也有明显的不足，即当有多个网
络时会出现环路问题。为了解决环路问题，IETF提出了分割范围方法，即路由器不可以通过它得知路由的接口去宣告路由。分割范围解决了两个路由器之间的路由环路问题，但不能防止3个或多个路由器形成路由环路。触发更新是解决环路问题的另一方法，它要求路由器在链路发生变化时立即传输它的路由表。这加速了网络的聚合，但容易产生广播泛滥。总之，环路问题的解决需要消耗一定的时间和带宽。若采用RIP协议，其网络内部所经过的链路数不能超过15，这使得RIP协议不适于大型网络。
2.2 Dijkstra算法
D ijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOS
E 表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。
3 小结
本文简单介绍了设计路由算法时算法应具有的特点，基于算法的这些特性可以保证生成路由表的开销、寻径和性能合理。介绍了路由算法的分类度量标准，对常见的两种路由算法——内部网关协议GIP和D ijkstra算法进行了简单的介绍。
参考文献
【1】谢希仁，计算机网络，2007，05
【2】Timothy S.Ramteke，网络，2004，11
【3】吴功宜，计算机网络
廖总主任晚上好！10日工作汇报:
1. 高管效益关键KPI过程监控收集与统计。
2.年后高管收心会数据部分整理(成本+销售)。
3.对石董汇报经营分析部2014年工作总结与2015年战略规划。
4.对接财务预算管理部《春节期间可节约项目的管控要求》，预算已发邮件通知相关责任人。
5.春节前董事办办公电脑交接处理及董事办门窗封条张贴。
6.胡总、杨总中午订餐。
路由算法是路由协议必须高效地提供其功能，尽量减少软件和应用的开销。 路由器使用路由算法来找到到达目的地的最佳路由。 关于路由器如何收集网络的结构信息以及对之进行分析来确定最佳路由，有两种主要的路由算法：总体式路由算法和分散式路由算法。采用分散式路由算法时，每个路由器只有与它直接相连的路由器的信息——而没有网络中的每个路由器的信息。这些算法也被称为DV（距离向量）算法。采用总体式路由算法时，每个路由器都拥有网络中所有其他路由器的全部信息以及网络的流量状态。这些算法也被称为LS（链路状态）算法。 收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。 路由算法的核心是路由选择算法，设计路由算法时要考虑的技术要素有： 1、选择最短路由还是最佳路由； 2、通信子网是采用虚电路操作方式还是采用数据报的操作方式； 3、采用分布式路由算法还是采用集中式路由算法； 4、考虑关于网络拓扑、流量和延迟等网络信息的来源； 5、确定采用静态路由还是动态路由。 各路由算法的区别点包括：静态与动态、单路径与多路径、平坦与分层、主机智能与路由器智能、域内与域间、链接状态与距离向量。 链接状态算法（也叫做短路径优先算法）把路由信息散布到网络的每个节点，不过每个路由器只发送路由表中描述其自己链接状态的部分。 距离向量算法（也叫做 Bellman-Ford算法）中每个路由器发送路由表的全部或部分，但只发给其邻居。 也就是说，链接状态算法到处发送较少的更新信息，而距离向量算法只向相邻的路由器发送较多的更新信息。 metric是路由算法用以确定到达目的地的最佳路径的计量标准，如路径长度。
5.3.4 附录E 最短路径算法——Dijkstra算法 在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman-Ford算法和Dijkstra算法。这两种算法的思路不同，但得出的结果是相同的。我们在下面只介绍Dijkstra算法，它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。 下面以图E-1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便起见，设源结点为结点1。然后一步一步地寻找，每次找一个结点到源结点的最短路径，直到把所有 点1, j)为结点i (1) 初始化 令N表示网络结点的集合。先令N = {1}。对所有不在N中的结点v，写出
不直接相连与结点若结点直接相连 与结点若结点 1 1 ),1()(v v v l v D ? ? ?∞= 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子，可以使D (v ) = 99。 (2) 寻找一个不在N 中的结点w ，其D (w )值为最小。把w 加入到N 中。然后对所有不在N 中的结点v ，用[D (v ), D (w ) + l (w , v )]中的较小的值去更新原有的D (v )值，即： D (v )←Min[D (v ), D (w ) + l (w , v )] (E-1) (3) 重复步骤(2)，直到所有的网络结点都在N 中为止。 表E-1是对图E-1的网络进行求解的详细步骤。可以看出，上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D (w ) 值。当第5次执行步骤(2)并得出了结果后，所有网络结点都已包含在N 之中，整个算法即告结束。 表E-1 计算图E-1的网络的最短路径
路由算法及分类 路由算法及分类： 1、非自适应算法，静态路由算法 不能根据网络流量和拓扑结构的变化更新路由表，使用静态路由表，也称为固定式路由选择算法。 特点：简单，开销少；灵活性差。 2、自适应算法，动态路由算法 可根据网络流量和拓扑结构的变化更新路由表。 特点：开销大；健壮性和灵活性好。 3、最优化原则（optimality principle） 如果路由器J 在路由器I 到K 的最优路由上，那么从J 到K 的最优路由会落在同一路由上。 4、汇集树（sink tree） 从所有的源结点到一个给定的目的结点的最优路由的集合形成了一个以目的结点为根的树，称为汇集树； 路由算法的目的是找出并使用汇集树。 几种典型的路由选择算法： 1、最短路径路由算法（Shortest Path Routing） 1）基本思想 构建子网的拓扑图，图中的每个结点代表一个路由器，每条弧代表一条通信线路。为了选择两个路由器间的路由，算法在图中找出最短路径。
2）测量路径长度的方法 结点数量 地理距离 传输延迟 距离、信道带宽等参数的加权函数 3）Dijkstra算法 每个结点用从源结点沿已知最佳路径到本结点的距离来标注，标注分为临时性标注和永久性标注； 初始时，所有结点都为临时性标注，标注为无穷大； 将源结点标注为0，且为永久性标注，并令其为工作结点； 检查与工作结点相邻的临时性结点，若该结点到工作结点的距离与工作结点的标注之和小于该结点的标注，则用新计算得到的和重新标注该结点； 在整个图中查找具有最小值的临时性标注结点，将其变为永久性结点，并成为下一轮检查的工作结点； 重复第四、五步，直到目的结点成为工作结点； 2、洪泛及选择洪泛算法 1）洪泛算法（Flooding） 属于静态路由算法 a)基本思想 把收到的每一个包，向除了该包到来的线路外的所有输出线路发送。
路由器原理及常用的路由协议、路由算法 近十年来，随着计算机网络规模的不断扩大，大型互联网络（如Internet）的迅猛发展，路由技术在网络技术中已逐渐成为关键部分，路由器也随之成为最重要的网络设备。用户的需求推动着路由技术的发展和路由器的普及，人们已经不满足于仅在本地网络上共享信息，而希望最大限度地利用全球各个地区、各种类型的网络资源。而在目前的情况下，任何一个有一定规模的计算机网络（如企业网、校园网、智能大厦等），无论采用的是快速以大网技术、FDDI技术，还是ATM技术，都离不开路由器，否则就无法正常运作和管理。 1 网络互连 把自己的网络同其它的网络互连起来，从网络中获取更多的信息和向网络发布自己的消息，是网络互连的最主要的动力。网络的互连有多种方式，其中使用最多的是网桥互连和路由器互连。 1.1 网桥互连的网络 网桥工作在OSI模型中的第二层，即链路层。完成数据帧（frame）的转发，主要目的是在连接的网络间提供透明的通信。网桥的转发是依据数据帧中的源地址和目的地址来判断一个帧是否应转发和转发到哪个端口。帧中的地址称为“MAC”地址或“硬件”地址，一般就是网卡所带的地址。 网桥的作用是把两个或多个网络互连起来，提供透明的通信。网络上的设备看不到网桥的存在，设备之间的通信就如同在一个网上一样方便。由于网桥是在数据帧上进行转发的，因此只能连接相同或相似的网络（相
同或相似结构的数据帧），如以太网之间、以太网与令牌环（token ring）之间的互连，对于不同类型的网络（数据帧结构不同），如以太网与X.25之间，网桥就无能为力了。 网桥扩大了网络的规模，提高了网络的性能，给网络应用带来了方便，在以前的网络中，网桥的应用较为广泛。但网桥互连也带来了不少问题：一个是广播风暴，网桥不阻挡网络中广播消息，当网络的规模较大时（几个网桥，多个以太网段），有可能引起广播风暴（broadcasting storm），导致整个网络全被广播信息充满，直至完全瘫痪。第二个问题是，当与外部网络互连时，网桥会把内部和外部网络合二为一，成为一个网，双方都自动向对方完全开放自己的网络资源。这种互连方式在与外部网络互连时显然是难以接受的。问题的主要根源是网桥只是最大限度地把网络沟通，而不管传送的信息是什么。 1.2 路由器互连网络 路由器互连与网络的协议有关，我们讨论限于TCP／IP网络的情况。 路由器工作在OSI模型中的第三层，即网络层。路由器利用网络层定义的“逻辑”上的网络地址（即IP地址）来区别不同的网络，实现网络的互连和隔离，保持各个网络的独立性。路由器不转发广播消息，而把广播消息限制在各自的网络内部。发送到其他网络的数据茵先被送到路由器，再由路由器转发出去。 IP路由器只转发IP分组，把其余的部分挡在网内（包括广播），从而保持各个网络具有相对的独立性，这样可以组成具有许多网络（子网）互连的大型的网络。由于是在网络层的互连，路由器可方便地连接不同类型的网络，只要网络层运行的是IP协议，通过路由器就可互连起来。 网络中的设备用它们的网络地址（TCP／IP网络中为IP地址）互相通信。IP地址是与硬件地址无关的“逻辑”地址。路由器只根据IP地址来转发数据。IP地址的结构有两部分，一部分定义网络号，另一部分定义网
对路由算法的讨论 电气学院自动化1313 金莉萍131001260305 摘要：路由算法是提高路由协议功能，尽量减少路由时所带来开销的算法。路由算法在路由协议中起着至关重要的作用，采用何种算法往往决定了最终寻径结果。本文就对各路由算法在不同模型下，综合对比它们路径选择的差异以展开研究讨论。 关键词：路由算法差异不同模式研究讨论 随着科学技术的飞速发展，不仅传统业务流量大大增加，而且出现了许多新业务，如语音、数据和多媒体应用等对网络传输质量的要求差别很大，关于IP网络相关问题变得日益尖锐，特别是宽带业务，对网络性能加转发速度、流量控制以及网络的可扩展性等提出了较高的要求、随着主干网链路传输速度的不断提高，IP网络中节点上的包转发成了网络的瓶颈，在不断地需求下，人们提出了新的高效的路由算法，这种算法是通过提高网络的调节和控制功能使流量分布更加合理，以达到尽可能减少网络阻塞、最小的网络代价、分布的网络负载等目标。路由算法，又名选路算法，可以根据多个特性来加以区分。实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现。因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。 就我看来，一个理想的路由算法应该在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。 算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使得出的路由不停的变化。 算法必须是正确的和完整的。这里，“正确”的含义是指沿着各路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。 算法应能适应通信量和网络拓扑的变化，这就是说要有自适应性。当网络中的通信量发生变化时，算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时的改变路由。有时称这种自适应性为“稳健性”。 算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法，但这并不是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。 一个实际的路由选择算法，应尽可能接近于理想算法。在不同的应用条件下对以上提出的六个方面也可有不同的侧重。 所以，路由是个非常复杂的问题，因为它是网络中的所有结点共同协调工作的结果。 路由算法应是公平的。路由选择算法应对所有用户（除了少数优先级高的用户）都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显的不符合公平性的要求。 路由算法的核心是路由选择算法，常见的路由选择算法有最短路径法、扩散法、基于流量的路由选择、距离向量路由选择、链路状态路由选择、分级路由选择、移动主机的路由选择、组播路由选择、广播路由选择。 这种算法是个非常复杂的问题，因为它是网络中的所有节点共同协调工作的结果。其次，路由选择的环境往往是不断变化的，而这种变化有时无法事先知道，例如，网络中出现了某些故障。此外，当网络发生拥塞时，就特别需要有能缓解这种拥塞的路由选择策略，但恰好在这种条件下，很难从网络中的各结点获得所需的路由选择信息。
本技术提供了一种动态路由最短路径选择方法，通过路由动态更新以实时更新路由信息，然后通过执行Dijkstra算法计算pc到各个路由器的最短路径；路由动态更新实现的步骤包括：发现邻居，设置链路成本，构造链路状态包，分发链路状态包，计算新路由关系。本技术用于解决主控电脑及终端(路由器)之间动态组网及数据交互的问题。 权利要求书 1.一种动态路由最短路径选择方法，其特征在于，通过路由动态更新以实时更新路由信息，然后通过执行Dijkstra算法计算pc到各个路由器的最短路径；路由动态更新实现的步骤包括：发现邻居，设置链路成本，构造链路状态包，分发链路状态包，计算新路由关系。 2.根据权利要求1所述的一种动态路由最短路径选择方法，其特征在于，路由器发现邻居是利用自检报文及hello和helloback报文的交互来发现邻居，在每一条点到点线路上发送一个特殊的HELLO数据包，然后线路的另外一个路由器做出一个helloback的回复，这样路由器收集完所有该路由器所有的helloback报文后，就就能够确认该路由器所有的邻居信息，pc收到相邻路由器的hello报文后，返回pc端发送的helloback报文，同时构建路由器节点，并将该路由器信息加入到路由器数据表中，在此过程中，将pc也作为一个路由器来对待。 3.根据权利要求1所述的一种动态路由最短路径选择方法，其特征在于，链路状态包中包括的信息有路由器与相邻路由器相连的端口号，相邻路由器序列号，相邻路由器与路由器相连的端口号。 4.根据权利要求2所述的一种动态路由最短路径选择方法，其特征在于，路由器会进行记录，如果是个新的数据包，那么就转发它，如果是个重复的数据包，就丢弃，当pc收到来自某一路由器的链路报文后，将该路由器的信息加入到路由器数据表中，如果当前路由器数据表中已经存在相同的路由器信息，则将原来的路由器信息删除，更新为最新的路由器信息。 5.根据权利要求4所述的一种动态路由最短路径选择方法，其特征在于，通过执行Dijkstra算法寻找出pc到各个路由器的最短路径 的具体步骤为：对路由器数据表中的各个路由器进行重新标号，pc标号为0，其余路由器标号为从1开始自然数编号，对路由器
计算机网络实习报告 论文题目距离向量算法更新路由表 学生专业班级通信07级2班 学生姓名（学号） 指导教师 完成时间 2010年05月22日 实习（设计）地点信息楼139（112）机房 2010 年 05 月 22 日
距离向量算法更新路由表 一．实验目的 1．认识并掌握路由器结构组成及路由建立与更新的原理 2．理解、掌握和利用距离向量算法的应用。 3. 能够用距离向量算法建立一个路由表并根据相邻路由器发来的数据进行更新。 5．所实现的路由器模拟Internet上的IP路由器，它能确定网络的最短路由，并在其上传输分组 二．原理概述 距离向量路由算法被距离向量协议作为一个算法，它告诉在网络中每个节点的最远和最近距离。在距离表中的这个信息是根据临近接点信息的改变而时时更新的。表中数据的量和在网络中的所有的接点是等同的。每个数据包括传送数据包到每个在网上的目的地的路径和距离/或时间在那个路径上来传输。 这个表中的列代表直接和它相连的“邻居”路由器相连，行代表在网络中的所有目的地。在距离向量路由算法中，相邻路由器之间周期性（一般为3分钟）地相互交换各自的路由表。当网络拓扑结构发生变化时，路由器之间也将及时地相互通知有关变更信息。它是一种动态路由选择算法。每个路由器都定期与其相邻的所有路由器交换路由表，据此更新它们自己的路由表。 所有路由器只与其相邻路由器交换信息，在发来为RIP报文情况下更新其路由表的具体步骤为： 1.对地址为X的相邻路由器发来的RIP报文，先修改报文中的所有项目，把“下跳”字段中地址均改为X，把所有“距离”字段的值加1.每一个项目都有三项数据，即：到目的网络N，距离是d，下一条路由器是X 2.对修改后的RIP报文中每个项目，进行以下步骤： 若原来路由表中没有目的网络N，则把该项目添加到路由表中。 否则若吓一跳地址是X，把收到的项目替还原路由表中的项目 否则若收到的项目中的距离d小于路由表中的距离，则进行更新。 否则什么也不做。 3．若三分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达的路由器，即把距离置为16.（本实验将其定义为6） 4.返回。 三．设计方案 路由表的建立和更新 假设建立七个路由器，其中三个A，B和C。路由器A的两个网络接口E0和S0 分别连接在 10.1.0.0和10.2.0.0网段上；路由器B的两个网络接口S0和S1 分别连接在 10.2.0.0和10.3.0.0网段上；路由器C的两个网络接口S0和E0 分别连接在 10.3.0.0和10.4.0.0网段上； 如上面各路由表的前两行所示，通过路由表的网络接口到与之直接相连的网 络的网络连接，其向量距离设置为0。这即是最初的路由表。
经典路由算法 一、先验式路由协议(DSDV) 先验式路由协议是一种基于表格的路由协议。在这种协议中，每个节点维护一张或多张表格，这些表格包含到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化时，节点在网络中发送路由更新信息。收到更新信息的节点更新自己的表格，以维护一致的、及时的、准确的路由信息。 不同的先验式路由协议的区别在于拓扑更新信息在网络中传输的方式和需要存储的表的类型。先验式路由协议不断的检测网络拓扑和链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点一旦需要发送报文，可以立即得到到达目的节点的路由。 （DSDV、OLSR路由协议等很多普通的因特网路由协议）它们查找路由是不依赖于路径上的节点是否要发包，而是每个节点维护一张包含到达其它节点的路由信息的路由表。节点间通过周期性的交换路由信息来不断更新自身的路由表，以便能够及时的反映网络拓扑结构和变化，以维护一致的、及时的、准确的路由信息。
DSDV:目的节点序列距离矢量协议（待补充） 可以解决路由成环问题，每一个节点维持一个到其它节点的路由表，表的内容为路由的“下一跳”节点。 1）给每条路径增加了一个序列号码 2）每个目的节点会定期广播一个单调递增的偶数序列号号码 3）当一个节点发现它到某个目的节点的路径断开时，它把到这个节点的距离 设为无穷大。并且将这条路径的序列号加1（此时为奇数），然后向网络中 广播这个更新包。当这条路径修复时，它又将序列号加1然后广播出去。 换另一种方式来说，每个节点都保持着一张路由表，路由表中的每一项记录了 它到目的节点的距离和序列号，也就是（s，d）。我们假设有一目的节点为D， 当以下任何一情况发生时，都会发送更新： 1）D定期将自己的序列号加2并广播出去，即（S，0） 2）如果节点X要通过Y到达节点D，当X和Y之间的连接断开后，X将到D的路径的序列号加1，同时将路径值设为∞，然后将信息发送给邻居。 参考资料：https://www.doczj.com/doc/f98008891.html,/candycat1992/article/details/8100146CSDN博客DSDV协议 DSDV创新之处是为每一条路由设置一个序列号，序列号大的路由为优选路由，序列号相同时，跳数少的路由为优选路由。正常情况下，节点广播的序列号是单调递增的偶数，当节点B发现到节点D的路由(路由序列号为s)中断后，节点B 就广播一个路由信息，告知该路由的序列号变为s+l，并把跳数设置为无穷大，这样，任何一个通过B发送信息的节点A的路由表中就包括一个无穷大的距离，这一过程直到A收到一个到达D的有效路由(路由序列号为s+1-1)为止。 在此方案中，网络内所有的移动终端都建立一个路由表，包括所有的目的节点到达各个目标节点的跳跃次数(或标识距离矢量的路径矩阵)。每个路由记录都有一个由目标节点设定的序列号。序列号使移动终端可以区分当前有效路由路径和已过时的路由路径。路由表周期性地做全网更新以维护全网的通信有效性。通常，为了减少由于路由表更新而产生的大量路由信息传递，减少网络路由开销，可以采用两种路由更新方式。 1）第一种是全清除方式： 即通过多个网络协议数据单元将路由更新信息在全网中传输。如果网络内终端出现移动，则产生的新路由分组信息不定期的传达至网络内所有终端。 2）第二种是部分更新方式： 或称为增量更新方式，即在最后一次全清除传输后，只传递那些涉及变化了的路
数据通信与计算机网络大作业 Dijkstra 最 短 路 径 算 法
【摘要】 摘要:最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用, 对其进行优化很有必要。本文分析了传统 的最短路径算法(即Dijkstra 算法)的优化途径及现有的优化算法, 然后在Dijkstra 算法的基础上, 采用配对堆结构来实现路 径计算过程中优先级队列的一系列操作, 经理论分析与实验测试结果对比, 可以大大提高该算法的效率和性能。 【关键词】 最短路径; Dijkstra 算法; 【正文】 随着计算机网络技术和地理信息科学的发展, 最短路径问题无论是在交通运输, 还是在城市规划、物流管理、网络通讯等方面, 它都发挥了重要的作用。因此, 对它的研究不但具有重要的理论价值, 而且具有重要的应用价值。研究最短路径问题通常将它们抽象为图论意义下的网络问题, 问题的核心就变成了网络图中的最短路径问题。此时的最短路径不单指“纯距离”意义上的最短路径, 它可以是“经济距离”意义上的最短路径, “时间”意义上的最短路径, “网络”意义上的最短路径。关于最短路径问题, 目前所公认的最好的求解方法, 是由F.W.Dijkstra 提出的标号法, 即Dijkstra 算法。 1 Dijkstra 算法 Dijkstra 算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点(源点)到其余各节点的最短路径时, 经典Dijkstra 算法将网络中的节点分成三部分: 未标记节点、临时标记节点和最短路径节点(永久标记节点)。算法开始时源点初始化为最短路径节点, 其余为未标记节点, 算法执行过程中, 每次从最短路径节点往相邻节点扩展, 非最短路径节点的相邻节点修改为临时标记节点, 判断权值是否更新后, 在所有临时标记节点中提取权值最小的节点, 修改为最短路径节点后作为下一次的扩展源, 再重复前面的步骤, 当所有节点都做过扩展源后算法结束。具体算法描述如下: 设在一非负权简单连通无向图G=
车载网络综述及相关路由算法分析 Overview of V ANET and analysis of relevant routing algorithm 软网1301 王建帮 201192181 软网1301 张凯源 1车载网络综述 1.1相关概念 随着相关技术的发展，越来越多的无线设备开始被应用在汽车上，如远程钥匙、PDAs、 智能手机等，车载网络(英文术语为Vehicular Ad hoc Network，即VANET)的概念因而被 提出。在Vehicular ad hoc networks(VANETS):status, results, and challenges一文中，作者从 以下四个方面对VANET作出了较为全面的阐述： 1)Intelligent transportation systems (ITSs) VANET中节点可分为vehicles和Roadside Units(RSUs), 它们各自都有接收，存储，转发数据 以及路由的功能。两者区别在于，vehicles代表着移动的车辆，其位置是不断变化的，而 RSUs则是固定在路边的节点。 Fig. 1 Inter-vehicle communication
Fig. 2 Vehicle-to-roadside communication Fig. 3 Routing-based communication 由于实际应用的需要，在ITSs中存在三种可能的通信结构（communication configure-tion）:inter-vehicle, vehicle-to-roadside, and routing-based communication。这三者的实现都依赖于有关周围环境的精确且即时的信息，而要获取这样的信息，则需要精确的定位系统（如Bluetooth, Ultra-wide Band, ZigBee等）以及智能的通信协议（如GPS, DGPS）来提供支持。 2)Inter-vehicle communication The inter-vehicle communication configuration (Fig. 1) uses multi-hop multicast/broadcast to transmit traffic related in- formation over multiple hops to a group of receivers. 3)Vehicle-to-roadside communication The vehicle-to-roadside communication configuration (Fig. 2) represents a single hop broadcast where the road- side unit sends a broadcast message to all equipped vehicles in the vicinity. 4)Routing-based communication
距离矢量路由算法原理实验 【实验目的】 1、要求实验者利用路由选择算法模拟软件提供的通信功能，模拟距离矢量路由选择算法的初始化、路由信息扩散过程和路由计算方法； 2、掌握距离矢量算法的路由信息扩散过程； 3、掌握距离矢量算法的路由计算方法。 【预备知识】 1、路由选择算法的特征、分类和最优化原则 2、路由表的内容、用途和用法 3、距离矢量算法的基本原理 【实验环境】 1、分组实验，每组4~10人。 2、拓扑： 虚线表示节点之间的逻辑关系，构成一个逻辑上的网状拓扑结构。 3、设备：小组中每人一台计算机。 4、实验软件：路由选择算法模拟软件（routing.exe ） 【实验原理】 路由选择算法模拟软件根据给定的拓扑结构，为实验者提供基本的本地路由信息，并能发送和接收实验者所组织的路由信息，帮助实验者完成路由选择算法的路由信息扩散过程、路由计算过程和路由测试过程。 1、模拟软件的功能（图2-1） ● 在局域网内根据小组名称和成员数量建立一个模拟网络拓扑结构，每个成员模拟拓扑中的一台路由器，路由器上的本地路由信息由实验软件提供。 ● 向实验者指定的发送对象发送实验者自行组织的发送内容。 ● 提示实验者有数据需要接收，并显示接收内容。 N 路由节点2 路由节点N-1 N = 4 ~ 10
●为实验者提供记录路由计算结果的窗口——路由表窗口。 ●为实验者提供分组逐站转发方法来验证路由选择的结果。 图2-1 路由选择算法模拟软件主界面 2、模拟软件的使用方法 1）建立小组 通过建立小组，每个小组成员可以获得本节点的编号和本地直连链路信息。 a）4～10人一组，在实验前自由组合形成小组。小组人数尽量多些，每人使用一台计算机。启动实验软件后点击“建立小组”按钮。（图2-2） 图2-2 选择建立小组 b）在建立小组的窗口内填入小组名称和成员数量。同一小组成员必须填写同样的小组名称和成员数量才能正确建立小组。（图2-3） 图2-3 建立小组窗口图2-4 小组建立过程
计算机网络原理最短路径路由 在路由选择方法中，我们经常采用的算法是：求给定网络中任意两个节点间的最短路径。即求任意两个节点间的最小时延或最小费用的路径。这里已知的是整个网络拓扑和各链路的长度。 求最短路径的方法有许多种，下面我们以图6-4所示的网络为例来讨论一种由Dijkstra 提出的求最短路径的算法，即寻找从源节点到网络中其他各节点的最短路径。在本例中，设节点A为源节点，然后逐步寻找其最短路径，每次找一个节点到源节点的最短路径，直到把所有的点都找到为止。 图6-4 求最短路径算法的网络举例 令D(V)为源节点(节点A)到节点v的距离,它就是沿着某一通路的所有链路的长度之和。再令l(i,l)为节点i至节点j之间的距离。整个算法有以下部分： （1）初始化。令N表示网络节点的集合。先令N={A}，对所有不在N中的节点v，写出： λ(A,ν)若节点ν与节点A直接相连； D(ν)= { ∞若节点ν与节点A不直接相连； 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞，可以使D （v）=99。 （2）寻找一个不在N中的节点w，其D（w）值为最小。把w加入到N中，然后对所有不在N中的节点，用D（v）与[D（w）+λ(w,ν)]中较小的值去更新原有的D（v）值，即：D（v）←min[D（v）,D（w）+λ(w,ν)] （3）重得步骤（2），直到所有的网络节点都在N中为止。 6-2所示 是对图 6-4的网 络进行求 解的详细 步骤。可 以看出，上述的步骤（2）共执行了5次，表中带圆圈的数字是在每一次执行步骤（2）时所寻找的具有最小值的D（w）值。当第5次执行步骤（2）并得出了结果后，所有网络节点都已包含在N之中，整个算法即告结束。
什么是算法？ 简而言之，任何定义明确的计算步骤都可称为算法，接受一个或一组值为输入，输出一个或一组值。（来源：homas H. Cormen，Chales E. Leiserson《算法导论第3版》） 可以这样理解，算法是用来解决特定问题的一系列步骤（不仅计算机需要算法，我们在日常生活中也在使用算法）。算法必须具备如下3个重要特性： ［1］有穷性。执行有限步骤后，算法必须中止。 ［2］确切性。算法的每个步骤都必须确切定义。 ［3］可行性。特定算法须可以在特定的时间内解决特定问题， 其实，算法虽然广泛应用在计算机领域，但却完全源自数学。实际上，最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。 那么又是哪10个计算机算法造就了我们今天的生活呢？请看下面的表单，排名不分先后： 1. 归并排序（MERGE SORT），快速排序（QUICK SORT）和堆积排序（HEAP SORT） 哪个排序算法效率最高？这要看情况。这也就是我把这3种算法放在一起讲的原因，可能你更常用其中一种，不过它们各有千秋。 归并排序算法，是目前为止最重要的算法之一，是分治法的一个典型应用，由数学家John von Neumann于1945年发明。 快速排序算法，结合了集合划分算法和分治算法，不是很稳定，但在处理随机列阵（AM-based arrays）时效率相当高。 堆积排序，采用优先伫列机制，减少排序时的搜索时间，同样不是很稳定。 与早期的排序算法相比（如冒泡算法），这些算法将排序算法提上了一个大台阶。也多亏了这些算法，才有今天的数据发掘，人工智能，链接分析，以及大部分网页计算工具。 2. 傅立叶变换和快速傅立叶变换 这两种算法简单，但却相当强大，整个数字世界都离不开它们，其功能是实现时间域函数与频率域函数之间的相互转化。能看到这篇文章，也是托这些算法的福。 因特网，WIFI，智能机，座机，电脑，路由器，卫星等几乎所有与计算机相关的设备都或多或少与它们有关。不会这两种算法，你根本不可能拿到电子，计算机或者通信工程学位。（USA） 3.代克思托演算法（Dijkstra‘s algorithm）
一、路由器简介 (1).基本概念 路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传送路径并对数据进行转发的网络设备。路由器工作的目的就是选择最佳路径，把数据传递到目的地。 (2).路由表 路由器在接收到数据时，要对其传输路径进行选择。为了实现这一目标，路由器需要维护一个称为“路由表”的数据结构。概括来讲，路由表就是包含若干条目、供路由器选路时查询数据包传输路径的表项。 (3).选路策略和选路机制 一般来说，路由器要实现数据转发的功能，至少需要完成两方面的工作： a)根据数据包的目的地址和网络的拓扑结构选择一条最佳路径，把对应不同目的地址的最 佳路径存放在路由表中（找最佳路径的过程就相当于更新路由表的过程）； b)搜索路由表，决定向哪个接口转发数据，并执行相应的操作。 在上面的两方面工作中，前者是选路策略（Routing policy, 也称为路由选择策略）问题，而后者是选路机制（Routing mechanism, 也称为路由选择机制）问题。 选路策略的实质就是如何确定数据传送的最佳路径，它是通过建立并维护路由表开实现的。选路策略的不同，从本质上讲就是建立和维护路由表的方式不同；选路机制实际上就是如何查找路由表，并根据查表的结果把数据转发出去。 (4).自治系统和路由域 由于Internet规模太大，分布范围太广，所以所有路由器的路由表中对应每一个目的网络都有一个条目是不可能的，同样，也不可能采用一个全局的路由算法或协议。因此，Internet 将整个网络划分为若干个相对自治的局部系统，即自治系统（Autonomous System, AS）。自治系统可以定义为同一机构下管理的路由器和网络的集合。 世界各地的自治系统都通过自己的边界路由器连接到Internet的核心网上。一般来说，一个自治系统可以配置一个或多个边界路由器，自治系统内部的路由器或者网络通过边界路由器与其他自治系统或者Internet核心网进行通信。
Dijkstra最短路径算法 摘要 OSPF 是由 IETF 的 IGP 工作组为 IP 网开发的一种能适应大型网络需要的典型的链路状态路由协议，它可以迅速地检测 AS 内的拓扑变化，经过一个
比较短的收敛期后，重新计算出无环路由。在 OSPF 中采用的是 Dijkstra 算法来实现最短路径的计算，做到了选路的高效、可靠。不同的算法在时间上的开销是不一样的，可能会有很大的差别，而对于一个大型的网络来讲，选路的效率往往就是网络的生命，算法的重要性不言而喻。 关键词 OSPF 最短路径Dijkstra 第1章绪论 最短路径算法是计算机科学与地理信息科学等领域研究的热点，其算法有很多种，其中传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，并且能够适应网络拓扑的变化，性能稳定，因而可以在运输路线规划等领域都应用广泛． 1.1 国内外最短路径算法的发展及其概况 最短路径在20世纪初开始受到人们的重视，关于它的求解方法，当时有很多科学家在研究．但给出求解的基本思想的人直到1959年才出现，是一位名叫Edsger Wybe Dijkstra（迪杰斯特拉）的荷兰计算机科学家，他不仅给出了求解
的基本思想，还给出了算法．他给出的算法主要解决的问题是从某一个固定的点到其他各点的最短路径问题．后来这个算法被誉为一代经典，被称作Dijkstra 算法．后来，人们逐渐从两个方面来研究最短路径，分为完全信息情况下和不确定情况下．确定情况下对最短路径的研究的过程中，发展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyfus算法已成为确定情况下的经典算法[1]．而不确定情况下对最短问题的研究又分成了四个方面：研究路段长度随机变化的最短路径问题，以Frank和Mirchandani为代表；研究不同费用函数最短路径问题，以Loui、Muethy和Sarkar为代表；研究时间独立情况下的路段长度随机变化的最短路径问题，Hall、LiPing Fu、L.R.Rilett、Elise和Hani为代表；研究路段长度为区间范围的最短路径问题，以Tomas和Rajeev为代表．其中，第二方面问题的研究得出的结论是“当目标是期望最短路径时问题转化为将边的权重用期望值表示的最短路径问题”． 1.2 传统Dijkstra算法仍然存在的一些问题 原始Dijkstra算法在存储图形数据和运算时，基于网络的权矩阵，需要根据其节点与距离之间的关系，形成关联矩阵、邻接矩阵与距离矩阵，需要定义N 的数组来存储数据，其中N为网络的节点数，当网络的节点数较大时，将N 占用大量的计算机内存． 原始Dijkstra算法在运行时一般将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型．网络中所有节点首先初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距离原点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法．根据算法的描述可知对临时标记节点的遍历成为Dijkstra算法的瓶颈，影响了算法的执行效率． 第2章 Dijkstra经典算法 2.1 引言 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径．主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止．Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，
路由算法介绍 网络层的作用：1、路由选择 2、网络互连 3、拥塞控制 4、为上层提供服务 网络层的主要功能是将分组从源机器路由到目标机器。完成路由选择的路由算法是网络层设计的最主要内容。 路由算法：它负责确定一个进来的分组应该被传送到哪一条输出线路上。 如果是数据报子网，将在每一个分组到达时作此决定 如果是虚电路子网，是在虚电路建立时决定，该连接上所有分组都将沿此线路传输 路由算法设计必须考虑的问题：正确性简单性健壮性稳定性公平性最优性路由算法的原则：按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径。 静态算法：不会根据当前测量或者估计的流量和拓扑结构，来调整它们的路由决策，所有的路由选择是预先在离线情况下计算好的，在网络启动的时候被下载到路由器中。 1、最短路径路由：
如图所示，图中的每个节点代表一台路由器，每条弧代表一条通信线路，线路上的数字是它的开销。现在我们想找到从A到D的最短路径。过程： （1）节点A标记为永久节点，依次检查每一个与A相邻的节点，并检查它们与A之间的距离。 （2）如果新的标记距离小于该节点原来的标记，说明找到了一条更短路径，该节点需要重新标记，作为暂时性标记 （3）检查整个图中所有有暂时性标记的节点，使其中具有最小标记的那个节点成为永久节点，并且作为下一个工作节点。 （4）重复上述过程，直到没有新的永久节点为止。 如下图所示 2、扩散法：每一个进来的分组将被发送到除了它进来的那条线路之外的每一条输出线路上。 产生的问题：会产生大量的重复分组。
解决办法： 在数据包头设一个计数器初值，每经过一个节点自动减1，计数值 为0 时，丢弃该数据包 在每个节点上建立登记表，则数据包再次经过时丢弃 缺点：重复数据包多，浪费带宽 优点：可靠性高，可用于并发数据库更新。极好的健壮性，可用于军事应用。常作为衡量标准，评价其它路由算法 现代计算机网络通常使用动态的路由算法（自适应算法），而不是上面介绍的静态路由算法，因为静态路由算法不会考虑到网络的当前负载情况。 自适应算法：随拓扑结构和流量的变化改变它们的路由决策，又称为动态路由算法。 1、 距离矢量路由：每个路由器维护一张表（即一个矢量），表中列出了当前抑制的到每个目标的最佳距离，以及所使用的线路。通过邻居之间互相交换信息，路由器不断更新它们内部的表。 举例： B A E F D C 2 3 7 6 1 8 5 4 延迟信息B
《通信网理论基础》 实 验 指 导 书 适用专业—信息工程 实验三：端间最短路径算法 一、实验目的 通信网络中为传输信息，需要求网络中端点之间的最短距离和路由。此时网络可以用图,)G V E ＝（来表示，每条边(,)i j 的权,i j w 可为该边的距离、成本或容 量等物理意义。端间最短径问题主要分为两种情况：寻找指定端至其它端的最短距离和路由，可以使用Dijkstra 算法解决；寻找任意两端之间的最短距离和路由, 使用Floyd 算法解决。 Dijkstra 算法为标号置定法，通过依次置定指定端与当前端的最短距离和回溯路由来实现；Floyd 算法为标号修正法，通过初始化图的距离矩阵和路由矩阵、并在转接过程中不断刷新，直至算法结束才能求出任意两点间的最短距离矩阵和前向或反向路由矩阵。 本次实验要求利用MATLAB 分别实现Dijkstra 算法和Floyd 算法，可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。 二、实验原理 2.1 Dijkstra 算法可描述如下： D 算法的每个端点i v 的标号为(,)i l λ，其中i λ表示1v 到i v 的距离，而l 为端点是1v 到i v 最短路径的最后一个端点。 图G V E =（，）的每一边上有一个权()0w e ≥。
D0：初始(0)1{}X v =，记10λ=，设1v 的标号为1(,1)λ。 D1：对任一边()()()(,)()(,)k k k i l i l X v X v X ∈Φ∈?反圈，计算i il w λ+的值。在()()k X Φ中选一边，设为00()()00(,)(,)k k i l i l v X v X ∈?。使000()(,)()()min k i i l i il i l X w w λλ∈Φ+= +，并令 0000l i i l w λλ=+，并且0l v 的标号为00,l i λ（）。 D2：当出现下面情况之一时停止。 1）()k j v X ∈；2）()k j v X ?但()(k X Φ=Φ） 2.2 Floyd 算法可描述如下： 给定图G 及其边(,)i j 的权,(1,1)i j w i n j n ≤≤≤≤ F0：初始化距离矩阵(0)W 和路由矩阵(0)R 。其中： (0) 0ij ij ij ij w e E w e E i j ∈??=∞???=? 若 若 若 (0)(0)w 0, ij ij j r ?≠∞=?? 若 其它 F1：已求得(-1)k W 和(-1)k R ，依据下面的迭代求()k W 和()k R ()(1)(1)(-1),,,,min(,)k k k k i j i j i k k j w w w w --=+ (1)()(1),,,(),(1)()(1),,,k k k i k i j i j k i j k k k i j i j i j r w w r r w w ----?，终止。 三、实验内容 用MATLAB 仿真工具实现D 算法和F 算法：给定图G 及其边(,)i j 的权 ,(1,1) i j w i n j n ≤≤≤≤，可用D 算法和F 算法分别求出其各个端点之间的最小距离以及路由。