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

精品文档实验七、Link States Algorithm的实现序号： 姓名： 学号： 2016 成绩 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#includeusing 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;inum;i+)arcsi=new int num;for(int j=0;jarcsij;void initRoute(int * R ,int RL,int vNum)for(int i=0;ivNum;i+)RLi=MAX;Ri=new intvNum;for(int j=0;jvNum;j+)Rij=-1;void updateRoute(int R1, int R2,int dest,int num)for(int i=0;inum;i+)R1i=R2i;for(int j=0;jnum;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;couttemp;v0=(int)temp-65; /A的ASCII码是65cout=vexnum)cout输入错误，请重新输入v0;elsefor(int cnt=0;cntvexnum;cnt+)visitcnt=FALSE; /visit临时存储已经求得的最短路径RLcnt=arcsv0cnt;if(RLcntMAX)Rcnt0=v0;Rcnt1=cnt;RLv0=0;visitv0=TRUE;for(int i=1;ivexnum;i+)int min=MAX;int v=v0;for(int j=0;jvexnum;j+)if(!visitj)if(RLjmin)v=j;min=RLj;visitv=TRUE;for(int k=0;kvexnum;k+)if(!visitk&(min+arcsvkRLk)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;destvNum;dest+)if(RLdest!=0)printf(目标节点 :%c n,dest+65);if (Rdest0=-1)cout最短路径不存在!endl;continue;elsecout最低费用路径是:endl;for(int j=0;jvNum;j+)if(Rdestj!=-1)printf(%c,Rdestj+65);cout);elsebreak;cout最低费用:RLdestendl; cout*endl;int main()int vNum;coutvNum;while(vNum0)coutvNum;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(short