计算机网络路由算法以及LS算法

姓名：卢佳毅学号:23320122203951实验五一、实验内容1、基础部分（6分）对于给定的网络拓扑图（给定路由器之间的距离/代价），通过DV算法实现路由表的建立过程，具体要求见本PPT15-17页，可提前准备，必须当场完成。2.对于给定的网络拓扑图，通过LS算法实现路由表的建立过程。（5分）二、实验过程1.DV算法#includestdio.h#includestdlib.h#defineMAX30000intflag=0,n;intArraya[100][100];intArrayb[100][100],next[100][100];intBeginningPath()//说明初始化的路由连接信息{inti,j,t;printf(请输入节点的个数：);scanf(%d,&n);//一共有n个节点for(i=0;in;i++){for(j=i+1;jn;j++){printf(从第%d个节点到第%d个节点的费用：,i,j);scanf(%d,&t);if(t==-1)t=MAX;Arraya[j][i]=t;Arraya[i][j]=t;next[i][j]=j;next[j][i]=i;}Arraya[i][i]=0;}printf(\n\n在交换路由之前:\n);for(i=0;in;i++)//显示初始化的数据{printf(\t);for(j=0;jn;j++){if(Arraya[i][j]==MAX)printf(∞);elseprintf(%d,Arraya[i][j]);}printf(\n);}return0;}intDVRound(intround){//DV算法inti,j,k;flag=0;for(i=0;in;i++){//通过三个循环来判定Arraya中的数据是否需要更新for(j=0;jn;j++){if(j!=i)for(k=0;kn;k++){if(k!=i)if(Arraya[i][j]Arrayb[i][k]+Arrayb[k][j]){Arraya[i][j]=Arrayb[i][k]+Arrayb[k][j];Arraya[j][i]=Arraya[i][j];next[i][j]=k;next[j][i]=j;flag=1;/*如果数据发生了改变，那么flag数据就会改变，输出就不是最后一轮*/}}}}if(!flag){//数据始终没有改变，即达到了最后一轮输出printf(交换完信息网络的最短路由费用情况:\n);for(i=0;in;i++){printf(\t);for(j=0;jn;j++){if(Arraya[i][j]==-1)printf(∞);elseprintf(%d,Arraya[i][j]);}printf(\n);}return-1;//最后一轮输出已经结束，退出程序}else{printf(第%d次交换路由的情况:\n,round);for(i=0;in;i++){printf(\t);for(j=0;jn;j++){if(Arraya[i][j]==MAX)printf(∞);elseprintf(%d,Arraya[i][j]);}printf(\n);}for(i=0;in;i++){printf(r%dnextcost\n,i);for(j=0;jn;j++){if(j!=i)printf(r%d%d%d\n,j,next[i][j],Arraya[i][j]);}}}return0;}intmain(){inti,j;intround=1;BeginningPath();while(1){for(i=0;in;i++)for(j=0;jn;j++)Arrayb[i][j]=Arraya[i][j];if(DVRound(round)==-1)break;round+=1;}printf(请输入要查看的路由：);scanf(%d,&i);printf(r%dnextcost\n,i);for(j=0;jn;j++){if(j!=i)printf(r%d%d%d\n,j,next[i][j],Arraya[i][j]);}return0;}2.LS算法#includestdio.h#includestdlib.h#defineMAX30000intn;intArraya[100][100];intBeginningPath()//说明初始化的路由连接信息{inti,j,t;printf(请输入节点的个数：);scanf(%d,&n);//一共有n个节点for(i=0;in;i++){for(j=i+1;jn;j++){printf(从第%d个节点到第%d个节点的费用：,i,j);scanf(%d,&t);if(t==-1)t=40000;Arraya[j][i]=t;Arraya[i][j]=t;}Arraya[i][i]=0;}printf(\n\n在交换路由之前:\n);for(i=0;in;i++)//显示初始化的数据{printf(\t);for(j=0;jn;j++){if(Arraya[i][j]==40000)printf(∞);elseprintf(%d,Arraya[i][j]);}printf(\n);}return0;}voidDijkstra(ints){intflag[100],d[100]={0},next[100]={0};inti,j,k,min;for(i=0;in;i++)//初始化{d[i]=Arraya[s][i];flag[i]=0;next[i]=i;}flag[s]=1;for(i=0;in;i++){min=MAX;for(j=0;jn;j++)//找出最小值d[k]if(d[j]min&&flag[j]==0){min=d[j];k=j;}flag[k]=1;//标志是否放入集合for(j=0;j=n;j++)//松弛邻边if(d[j]Arraya[k][j]+d[k]&&flag[j]==0){d[j]=Arraya[k][j]+d[k];next[j]=next[k];}}printf(r%dnextcost\n,s);for(i=0;in;i++){if(i==s)continue;printf(%d:%d%d\n,i,next[i],d[i]);}}intmain(){inti;BeginningPath();for(i=0;in;i++)Dijkstra(i);return0;}三、实验结果四、实验心得经过这次实验，熟悉了路由器交换的原理，对课本上的知识有了更深的理解。