文档介绍：计算机网络实验 7模拟网络层路由算法?实验目的?熟悉分组的路由过程?模拟最短路由选择算法?实验要求?设计出最短路由选择算法流程图?编写模拟最短路由选择算法程序?模拟距离向量路由算法(选做) ?实验环境?硬件: PC 机?软件: 实际编译环境?实验项目性质?设计性?实验内容?设计出工作流程图?编写程序模拟算法的实现?建立一个子网图,图中的每个节点代表路由器,每条狐线代表一条通信线路。为了选择一对路由器的路由,算法采用 dijkstra 算法求出最短路径。注意要保留中间节点的信息。?扩展(模拟距离向量路由算法 RIP 的工作流程图和代码实现) ?实验课后作业?按规定格式,撰写实验报告?实验学时: ?4学时?实验 7报告提交时间: 最短路径假设:顶点表示路由器 R ,用边表示路由器间的链路,则由这些顶点和边组成的图可以表示网络的拓扑结构。若把两个路由器之间的路由度量(距离、带宽等)作为权值,赋于图中的边,就构成了一个带权的图。路由关心的问题是: 1、从 R1到R2是否有通路? 2 、若从 R1到R2 有若干条通路,哪一条通路最短或代价最小。最短路径:指带权图中,两顶点间所经过的边上的权值之和为最小的路径。(不是指路径上经过的边的数目最小)。源点:路径上的第一个顶点。终点:路径上最后一个顶点。单源点最短路径单源点最短路径:给定一个出发点( 单源点) 和一个有向网G=(V ,E), 求出源点到其它各顶点之间的最短路径。迪杰斯特拉( Dijkstra ) 算法: 按路径长度递增的次序产生最短路径。单源点最短路径-- Dijkstra 算法要点 A表示带权图,A[i][j ]表示弧<vi,vj >上的权值。若<vi,vj >不存在,则置 A[i][j ]=∞,S为已求得最短路径的终点集合, 初始状态为空集。 D[i ]:表示已找到的从 v到其余各顶点 vi可能达到的最短路径长度,初值:若从 v0到vi有弧,则D[i ] 为弧上权值,否则为∞。 vj,使得: D[j ]=Min{D[i]|vi ∈V-S} vj就是当前求得的一条从 v出发的最短路径的终点。令 S=S ∪{j} 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 ] 2、3至n-1 次,由此求得从 v到图上其余各顶点的最短路径是依路径长度递增的序列。图的邻接矩阵表示法若G=(V,E) 为网,则邻接矩阵可以表示为: A[i][j]= W ij若(Vi,Vj ) 或<Vi,Vj >∈VR ∞反之 13 24 5 6394 7 812 ∞6 1 ∞ 3 6∞∞ 8 9 1 ∞∞ 2 4 ∞8 2 ∞73 9 4 7 ∞单源点最短路径 V 0v 4v 1v 2v 3100 1050 3010 60邻接矩阵 = ∞ 1 0 ∞ 3 0 1 0 0 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 V 0v 4v 1v 2v 3100 1050 3010 6020