搜索
实验八、LinkStatesAlgorithm的实现序号：姓名：学号：成绩1．实验目的：通过编程模拟实现LSA.2．实验环境：VS.net软件开发平台，可以使用任何编程语言。3．实验要求（1）求网络中任何两个结点之间的最短路径（网络中至少有4个节点）。（2）得到任何一个节点上的转发表。4.实验内容、拓扑结构通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。算法提示：Initialization:2N'={u}/*uissourcenode*/3forallnodesj/*jisdestnode*/4ifjadjacenttou5thenD(j)=c(u,j)6elseD(j)=∞78Loop9findinotinN'suchthatD(i)isaminimum10additoN'11updateD(j)foralljadjacenttoiandnotinN':12D(j)=min(D(j),D(i)+c(i,j))13/*newcosttojiseitheroldcosttojorknown14shortestpathcosttoipluscostfromitoj*/15untilallnodesinN'4．实验分析，回答下列问题（1）给出LSA算法的主要思想。答：LSA算法的主要思想为：该算法用迭代算法，其性质是经算法的第Ｋ次迭代后，可知道Ｋ个目的节点的最低费用路径。ABECD718122A：邻居节点发现与测试：各节点主动测试所有与之相邻的节点的状态。方法是周期性的向邻,居节点广播简短的查询报文，通过接收邻居节点的响应报文,来获取与邻居的状态信息。B：链路状态信息发布：根据收集到的状态信息，构造一个包含所有邻居列表在内的分组LS，并通过洪泛法通告给算法作用区域内的所有节点。C：路由选择算法：收到LS分组的节点，采用Dijkstra算法，为每个节点选择最短的路径。（2）通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。代码：#includestdio.h#includestring.h#defineMAXV20#defineMAXSIZE20#defineMAXLEN500#defineINF10000/*用表示∞*/inta=0;typedefstruct{intnum;charname[MAXSIZE];charcontent[MAXLEN];}VertexType;typedefstruct{intedges[MAXV][MAXV];intvexnum,arcnum;VertexTypevexs[MAXV];}MGraph;intvisited[MAXV];intp[MAXV];voidPath(MGraphg,inti,intj,intk)/*确定路径上第k+1个节点的编号*/{ints;if(p[k]==j)/*找到一条路径*/{a++;/*路径的条数值加*/printf(第%d条:\n,a);for(s=0;s=k-1;s++)/*输出一条路径*/printf(%s-,g.vexs[p[s]].name);printf(\n);}s=0;while(sg.vexnum){if(s!=i)/*保证找到的是简单路径*/{if(g.edges[p[k]][s]!=INF&&visited[s]==0)/*当vk与vs之间有边存在且vs未被访问过*/{visited[s]=1;/*置访问标志位为,即已访问的*/p[k+1]=s;/*将顶点s加入到p数组中*/Path(g,i,j,k+1);visited[s]=0;/*重置访问标志位为，以便该顶点能被重新使用*/}}s++;}}voidDisplay(MGraphg,inti,intj){intk;p[0]=i;for(k=0;kg.vexnum;k++)visited[i]=0;/*初始化各节点的访问标志位*/a=0;/*初始化路径的条数*/Path(g,i,j,0);/*通过调用path函数，找到从vi到vj的所有路径并输出*/}voidPath2(MGraphg,intpath1[],inti,intv0){intk;k=path1[i];if(k==v0)/*找到最短路径，则返回*/return;Path2(g,path1,k,v0);/*否则，递归调用之*/printf(%s-,g.vexs[k].name);/*依次输出路径中的节点*/}voidDispath(MGraphg,intdist[],intpath1[],ints[],intn,intv0,inti){if(s[i]==1&&i!=v0)/*当v0不等于i，且i∈s*/{printf(\n从%s到%s的最短路径是:\n,g.vexs[v0].name,g.vexs[i].name);printf(%s-,g.vexs[v0].name);Path2(g,path1,i,v0);/*调用ppath函数，输出路径中的节点*/printf(%s,g.vexs[i].name);printf(路径长度：%d\n,dist[i]);}}voidDijkstra(MGraphg,intv0,intp){intdist[MAXV],path1[MAXV];ints[MAXV];intmindis,i,j,u,n=g.vexnum;for(i=0;in;i++){dist[i]=g.edges[v0][i];/*距离初始化*/s[i]=0;/*s[]置空*/if(g.edges[v0][i]INF)/*路径初始化*/path1[i]=v0;elsepath1[i]=-1;}s[v0]=1;path1[v0]=0;/*源点编号v0放入s中*/for(i=0;in;i++){mindis=INF;u=-1;for(j=0;jn;j++)/*选取不在s中具有最小距离的节点u*/if(s[j]==0&&dist[j]mindis){u=j;mindis=dist[j];}s[u]=1;/*顶点u加入s中*/for(j=0;jn;j++)/*修改不在s中的节点的距离*/if(s[j]==0)if(g.edges[u][j]INF&&dist[u]+g.edges[u][j]dist[j])/*修正dist[i],path1[i]*/{dist[j]=dist[u]+g.edges[u][j];path1[j]=u;}}Dispath(g,dist,path1,s,n,v0,p);/*输出最短路径*/}voidSearch(MGraphg){printf(节点：\n1.A\n2.B\n3.C\n4.D\n5.E);inti=0,j=0;chars=0;printf(\n\n请选择出发节点的编号：);scanf(%d,&i);printf(请选择目的节点的编号：);scanf(%d,&j);for(intk=0;kg.vexnum;k++)/*g.vexnum表示网中的顶点个数*/if(i==g.vexs[k].num)i=k;/*在网中找到其编号与输入的出发景点的编号相同的顶点*/for(intl=0;lg.vexnum;l++)if(j==g.vexs[l].num)j=l;/*在网中找到其编号与输入的目地景点的编号相同的顶点*/Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/}voidmain(){inti=0,j=0;intb[5]={1,2,3,4,5};/*整型数组,用来给每个顶点的编号进行赋值*/char*c[5]={A,B,C,D,E};/*字符串指针数组,用来给每个顶点的名称进行赋值*/MGraphg;/*定义一个MGraph类型的变量g,用来创建一个无向网*//*建立一个无向网，并用无向网表示节点的平面图*/intA[5][5]={/*用INF表示对应顶点间没有直达的路径，用其它整型变量表示对应顶点间有直达的路径，且路径的长度就是该整型变量的值*/{0,7,INF,INF,1},{7,0,1,INF,8},{INF,1,0,2,INF},{INF,INF,2,0,2},{1,8,INF,2,0}};g.vexnum=5;/*网中顶点的个数为*/g.arcnum=6;/*网中边的个数为*/for(i=0;ig.vexnum;i++)for(j=0;jg.vexnum;j++)g.edges[i][j]=A[i][j];/*建立无向网的邻接矩阵*/for(i=0;ig.vexnum;i++){g.vexs[i].num=b[i];/*给每个节点一个编号*/strcpy(g.vexs[i].name,c[i]);/*通过字符串复制函数给每个节点一个名称*/}intselect;/*定义一个整型变量,用来输入不同的选择*/do/*可提供循环输入选择,当输入的选择为时,退出循环*/{printf(\n1.求节点间的最短路径0.退出);printf(\n请选择操作:);scanf(%d,&select);switch(select)/*判断select的值，根据其值跳转到相应的子模块继续执行*/{case1:Search(g);/*节点间的最短路径*/break;case0:/*退出程序*/break;}}while(select!=0);/*当select的值不为时，继续循环*/}截图：