lab模拟网络层路由算法.pptVIP

计算机网络实验7 模拟网络层路由算法 实验目的 熟悉分组的路由过程 模拟最短路由选择算法 实验要求 设计出最短路由选择算法流程图 编写模拟最短路由选择算法程序 模拟距离向量路由算法（选做） 实验环境 硬件：PC机 软件：实际编译环境 实验项目性质 设计性 实验内容 设计出工作流程图 编写程序模拟算法的实现 建立一个子网图，图中的每个节点代表路由器，每条狐线代表一条通信线路。为了选择一对路由器的路由，算法采用dijkstra算法求出最短路径。注意要保留中间节点的信息。 扩展（模拟距离向量路由算法RIP的工作流程图和代码实现） 实验课后作业 按规定格式，撰写实验报告 实验学时： 4学时 实验7报告提交时间： 最短路径 单源点最短路径 单源点最短路径--Dijkstra算法要点 1.用带权邻接矩阵A表示带权图,A[i][j]表示弧vi,vj上的权值。若vi,vj不存在,则置A[i][j]＝∞，S为已求得最短路径的终点集合,初始状态为空集。 D[i]:表示已找到的从v到其余各顶点vi可能达到的最短路径长度,初值:若从v0到vi有弧,则D[i]为弧上权值,否则为∞。 2.选择vj，使得： D[j]=Min{D[i]|vi∈V-S} vj就是当前求得的一条从v出发的最短路径的终点。令 S＝S ∪{j} 3.从v到其它顶点的最短路径有可能通过vj得到改变。下一条次短路径是终点vk,则这条路径或者是（v0，vk），或者是（v0，vj，vk）。它的长度或者是从v0到vk的权值，或者是D[j]与从vj到vk的权值之和,因此要修改D的值。 修改从v到V-S上任一顶点vk可达的最短路径长度。若 D[j]+A[j][k]D[k] 则修改D[k]为: D[k]=D[j]+A[j][k] 4.重复2、3至n-1次，由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。 图的邻接矩阵表示法 单源点最短路径 所有顶点对之间的最短路径 * 假设：顶点表示路由器R，用边表示路由器间的链路，则由这些顶点和边组成的图可以表示网络的拓扑结构。若把两个路由器之间的路由度量（距离、带宽等）作为权值，赋于图中的边，就构成了一个带权的图。 路由关心的问题是： 1、从R1到R2是否有通路？ 2、若从R1到R2有若干条通路，哪一条通路最短或代价最小。 最短路径：指带权图中，两顶点间所经过的边上的权值之和为最小的路径。(不是指路径上经过的边的数目最小)。 源点：路径上的第一个顶点。 终点：路径上最后一个顶点。 单源点最短路径：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。 迪杰斯特拉（Dijkstra）算法: 按路径长度递增的次序产生最短路径。 若 G=(V,E) 为网,则邻接矩阵可以表示为: Ａ[i][j]= Wij 若(Vi,Vj) 或Vi,Vj∈VR ∞ 反之 1 3 2 4 5 6 3 9 4 7 8 1 2 ∞ 6 1 ∞ 3 ∞ ∞ 8 9 1 ∞ ∞ 2 4 ∞ 8 2 ∞ 7 3 9 4 7 ∞ V0 v4 v1 v2 v3 100 10 50 30 10 60 邻接矩阵G.arcs= ∞ 10 ∞ 30 100 10 ∞　 50 ∞ ∞ ∞ 50　∞ 20 10 30 ∞　 20 ∞ 60 100 ∞ 10 60 ∞ 设源点v0 s={v0} 初值dist={∞,10,∞,30,100} 第一条最短路径是:(v0,v1),长度为10 s={v0,v1} 修改（v0,v1,v2）=60，即：dist={∞，10，60，30，100} 第二条最短路径是：(v0,v3),长度为30。S={v0,v1,v3} 修改(v0,v3,v2）=50，（v0,v3,v4）=90 即：dist={∞，10，50，30，90} 第三条最短路径是：（v0,v3,v2）=50 s={v0,v1,v3,v2} 修改（v0,v3,v2,v4）=60, dist={∞，10，50，30，60} 第五条最短路径是:(v0,v3,v2,v4)=60, s={v0,v1,v3,v2,v4} 20 V0 v4 v1 v2 v3 100 10 50 30 10 60 20 解决方法1:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次总的时间复杂度为O(n3)。