云南大学软件学院计算机网络原理实验七.doc
实验七、Link States Algorithm的实现序号： ： 学号： 2021 成绩 1实验目的：通过编程模拟实现LSA.2实验环境：VS.net软件开发平台，可以使用任何编程语言。3实验要求1求网络中任何两个结点之间的最短路径网络中至少有4个节点。2得到任何一个节点上的转发表。4.实验内容、拓扑结构ABDCE232111F2535通过链路状态算法计算A点到其它各点的cost，最终输出A的路由表。算法提示：Initialization: 2 N' = u /*u is source node*/3 for all nodes j /* j is dest node*/4 if j adjacent to u 5 then D(j) = c(u,j) 6 else D(j) = 7 8 Loop 9 find i not in N' such that D(i) is a minimum 10 add i to N' 11 update D(j) for all j adjacent to i and not in N' : 12 D(j) = min( D(j), D(i) + c(i,j) ) 13 /* new cost to j is either old cost to j or known 14 shortest path cost to i plus cost from i to j */ 15 until all nodes in N' 4实验分析，答复以下问题1给出LSA算法的主要思想。LSA算法即链路状态选路算法，该算法中，网络拓扑和所有的链路费用都是的。它的具体实现依据Dijkstra算法，其主要思想是计算从某节点源节点，u到网络中所有其他节点的最短路径。其算法是迭代算法，即经算法的第k次迭代后，可知道到k个目的节点的最低费用路径，在在到所有目的节点的最低费用路径之中，这k条路径具有k个最低费用。2通过图表算出任何两个节点之间的最短路径，并给出每个节点上的转发表。截图：转发表：A:目的地链路最低费用BA->B2CA->D->E->C3DA->D1EA->D->E2FA->D->E->F4B：目的地链路最低费用AB->A2CB->C3DB->D2EB->D->E3FB->D->E->F5C:目的地链路最低费用AC->E->D->A3BC->B3DC->E->D2EC->E1FC->E->F3D:目的地链路最低费用AD->A1BD->B2CD->E->C2ED->E1FD->E->F3E:目的地链路最低费用AE->D->A2BE->D->B3CE->C1DE->D1FE->F2F:目的地链路最低费用AF->E->D->A4BF->E->D->B5CF->E->C3DF->E->D3EF->E2源代码：#include<iostream>#include<stdio.h>using namespace std;const int MAX=1000;const int OK=1;const int FALSE=0;const int TRUE=1;void createGraph(int *arcs,int &num)cout<<"请依次输入各点的各条路径的cost:"<<endl<<"(如果拓扑图中的顶点没有直接相连，那么输入1000)"<<endl;cout<<"-"<<endl;for (int i=0;i<num;i+)arcsi=new int num;for(int j=0;j<num;j+)cin>>arcsij;void initRoute(int * R ,int RL,int vNum)for(int i=0;i<vNum;i+)RLi=MAX;Ri=new intvNum;for(int j=0;j<vNum;j+)Rij=-1;void updateRoute(int R1, int R2,int dest,int num)for(int i=0;i<num;i+)R1i=R2i;for(int j=0;j<num;j+)if (R1j=-1)R1j=dest;break;void Dijkstra(int * arcs,int * R,int RL,int vexnum)char temp;int v0;bool * visit=new bool vexnum;cout<<"请输入起始节点："cin>>temp;v0=(int)temp-65; /A的ASCII码是65cout<<endl;if(v0>=vexnum)cout<<"输入错误，请重新输入"<<endl;cin>>v0;elsefor(int cnt=0;cnt<vexnum;cnt+)visitcnt=FALSE; /visit临时存储已经求得的最短路径RLcnt=arcsv0cnt;if(RLcnt<MAX)Rcnt0=v0;Rcnt1=cnt;RLv0=0;visitv0=TRUE;for(int i=1;i<vexnum;i+)int min=MAX;int v=v0;for(int j=0;j<vexnum;j+)if(!visitj)if(RLj<min)v=j;min=RLj;visitv=TRUE;for(int k=0;k<vexnum;k+)if(!visitk&&(min+arcsvk<RLk)RLk=min+arcsvk;updateRoute(Rk,Rv,k,vexnum); visit=NULL;void printRoute(int * R,int RL, int vNum)int q=0;for(int dest=0;dest<vNum;dest+)if(RLdest!=0)printf("目标节点 :%c n",dest+65);if (Rdest0=-1)cout<<"最短路径不存在!"<<endl;continue;elsecout<<"最低费用路径是:"<<endl;for(int j=0;j<vNum;j+)if(Rdestj!=-1)printf("%c",Rdestj+65);cout<<(Rdestj=dest?"n":"->");elsebreak;cout<<"最低费用:"<<RLdest<<endl; cout<<"*"<<endl;int main()int vNum;cout<<"请输入节点个数："cin>>vNum;while(vNum<0)cout<<"输入个数错误！请重新输入："cin>>vNum;cout<<"-"<<endl;cout<<"你输入的"<<vNum<<"个节点将按0-"<<vNum-1<<"顺序组成的邻接矩阵存储权值"<<endl;int * weight=new int * vNum;int * shortestRoute=new int * vNum;int * routeLen=new int vNum;createGraph(weight,vNum);cout<<"-"<<endl;char isExit='y'doinitRoute(shortestRoute,routeLen,vNum);Dijkstra(weight,shortestRoute ,routeLen,vNum);printRoute(shortestRoute,routeLen,vNum);cout<<"是否继续: y:是 n:否 "cin>>isExit;cout<<endl;if(isExit='n')break;while(isExit='y');return OK;
