云南大学软件学院计算机网络原理实验八

《云南大学软件学院计算机网络原理实验八》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验八、LinkStatesAlgorithm的实现序号：姓名：—学号：_成绩1.实验目的:通过编程模拟实现LSA.2.实验环境：VS.net软件开发平台，可以使用任何编程语言。3.实验要求（1）求网络中任何两个结点Z间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。4.实验内容、拓扑结构通过链路状态算法计算A点到其它各点的cost,最终输出A的路由表。算法提示：Initialization:2N，={u}/*uissourcenode*/3forallnodesj/*jisdostnode*/4ifjadjacen

2、ttou5thenD(j)=c(u,j)6elseD(j)=0077Loop8findinotinN‘suchthatD(i)isaminimum9additoN'10updateD(j)foralljadjacenttoiandnotinN‘11D(j)二min(D(j),D(i)+c(i,j))12/*newcosttojiseitheroldcosttojorknown13shortestpathcosttoipluscostfromitoj*/14untilallnodesinN‘4.实验分析，回答下列问题（1）给出LSA算法的主

3、要思想。1、路由器初始化（所冇节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。2、路由器更新与源T节点直接相连的所冇暂时性节点的状态记录集。3、路由器在所有的暂时性节点中选择距离VI的权值最低的节点。这个节点将是新的T节点。4、如果这个节点不是V2（冃的节点），路由器则返回到步骤5。5、如果节点是V2,路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到VI为止。这个节点列表便是从VI到V2的最佳路由。源程序如下：#inelude#include#defi

4、nemaxlen10#definelarge999//（该处设置路径最大值，表示不存在该路线）typedefstruct{intvexnum;charvexs[maxlen];intarcs[maxlen][maxlen];}graph;voidinit_graph（graph*g）//初始化图{inti=0,j=0;g->vexnum=5;//根据题目此处将图的节点数初始化为5个for（i二0;i〈5;i++）〃经过两层循环将条路径初始化为无穷大for（j=0;j<5;j++）g->arcs[i][j]=999;g->arcs[0][1

5、]二7;g->arcs[1][0]二7;//将相邻两个节点的路径初始化为具权值g->arcs[0][4]=1;g->arcs[4][0]=1；g->arcs[l][2]=1;g->arcs[2][1]=1；g->arcs[2][3]=2;g->arcs[3][2]=2;g->arcs[1][4]二8;g->arcs[4][1]二8;g->arcs[3][4]二2;g->arcs[4][3]二2;g->vexs[0]='A';〃将节点值初始化g->vexs[l]='B';g->vexs[2]='C，;g->vexs[3]二’D';g->ve

6、xs[4]二'R，；voidshortpathdijkstra(graphg)//寻找最短路径{"intcost[maxien][maxien];//cost[i][j]:节点i至『节点j的成本intdist[maxlen];//dist[i]:源节点到i节点的距离或者是成木intpath[maxlen];//已经经过了的节点intstmaxlen];//如果s[i]=1,那么i节点已经纳入最短路径集合inti,j,vO,min,u;chare;printf(〃请输入源节点：(比如输入'A')〃);〃用户输入源节点scanf(〃%c〃,&

7、e);switch(e){case，A，:vO二0;break;case'B，:vO=l;break;case'C":v0=2;break;case'D‘:v0=3;break;case'E‘:vO二4;break;}for(i=0;i

8、]0)path[i]=vO;s[i]=0;}s[v0]二1;for(i=0;i