链路状态路由算法的实现

链路状态路由算法的实现实验内容与要求1.程实现右图所示简单网络拓扑的链路状态路由算法。1.1结点之间的连接关系固定；1.2链路开销可以由用户设定。2.链路状态算法的实现：2.1链路状态消息的交换(可选，简单起见，可基于静态网络拓扑运行Dijkstra算法)；2.2网络拓扑的描述/构造；2.3利用Dijkstra算法计算路由；2.4路由表的输出。3.网络拓扑结构的描述(数据结构)，拓扑结构利用文件存储。4.用可视化界面进行程序演示。实验环境与知识实验的运行环境Windows7QTcreatorQT4.8编程语言C++实验的基础知识算法思想按路径长度递增次序产生最短路径算法：把顶点集合V分成两组：（1）S：已求出最短路径的顶点的集合（初始时只含有源点V0）（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中其他各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）实验程序的设计流程设计思路算法思路的设计首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为D[j]=Min{D|vi∈V}的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。迪杰斯特拉算法描述如下：1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[LocateVex(G,v),i]vi∈V2）选择vj，使得D[j]=Min{D|vi∈V-S}3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。1.2界面的设计与实现利用QTmainwindow为载体，添加spinbox作为输入来源，tableview作为输出控件。与迪杰斯特拉算法类交互。流程图设开始开始输入路由间的链路的值输入路由间的链路的值调用dijkstra算法选择路由调用dijkstra算法选择路由更新链路信息更新链路信息输出路由表输出路由表是否退出否是否退出是退出退出关键的数据结构和代码关键的数据结构 classdj_arithme{public:intdj(int,int,int,int,int);intout[20][4];//起始目的距离下一跳private:intoutrow;intconvertout(int,int,int,int);intdist[4][4];intlength[4][4];introute[4][4];//下一跳地址存放intmin,minLength,start,end,i,j,n;};classMainWindow:publicQMainWindow{Q_OBJECTpublic:explicitMainWindow(QWidget*parent=0);~MainWindow();voidpaintEvent(QPaintEvent*event);private:Ui::MainWindow*ui;intua01,ua02,ua03,ua12,ua23;publicslots:voidupdateroute();};采用的是矩阵来存放网络的拓扑结构，其中0表示自身，N表示的是两个路由之间彼此没有直接的联系，其中i1i2i3i4i5的值是在程序的执行过程中动态分配intlength[4][4]={0};该矩阵是用来存放两个路由之间的最短路径长introute[4][4]={0};该矩阵是用来存放下一跳的路由关键的代码intdj_arithme::dj(inta01,inta12,inta23,inta02,inta03){outrow=0;a01=1,a12=2,a23=2,a02=6,a03=6;dist[0][0]=0;dist[1][1]=0;dist[2][2]=0;dist[3][3]=0;dist[1][0]=dist[0][1]=a01;dist[1][3]=dist[3][1]=a12;dist[2][0]=dist[0][2]=a02;dist[0][3]=dist[3][0]=a03;dist[2][3]=dist[3][2]=a23;length[4][4]={};//最短路径长度的保存route[4][4]={};//下一跳地址存放for(i=0;i<4;i++){for(j=0;j<4;j++){route[i][j]=j;}}for(start=0;start<4;start++){intvisited[4]={0};visited[start]=1;

for(intend=1;end<4;end++){min=-1;minLength=MAX;for(i=0;i<4;i++){if(visited[i]==0&&dist[start][i]<minLength){minLength=dist[start][i];min=i;}}visited[min]=1;for(i=0;i<4;i++){if(visited[i]==0&&dist[start][min]+dist[min][i]<dist[start][i]){dist[start][i]=dist[start][min]+dist[min][i];//dist[i][j]=dist[start][i];route[start][i]=route[start][min];}}}for(i=0;i<4;i++){for(j=0;j<4;j++)length[i][j]=dist[i][j];

}for(n=0;n<4;n++){if(start==n)continue;cout<<start<<"===>"<<n<<"length"<<length[start][n]<<"nextroute"<<route[start][n]<<endl;convertout(start,n,length[start][n],route[start][n]);}}out[outrow][0]=N;return1;}

intdj_arithme::convertout(intbegin,inttarget,intlength,intnext){out[outrow][0]=begin;out[outrow][1]=target;out[outrow][2]=length;out[outrow][3]=next;outrow++;}

上面的部分代码是用来实现dijkstra算法的，通过这个算法可以求出彼此两个路偶之间的最短路径的值并且的出吓一跳的路由编号，将结果保存到到矩阵中，从而得出了每个路由的路由表。程序的