鏈路狀態(tài)路由算法的實(shí)現(xiàn)

鏈路狀態(tài)路由算法的實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容與要求1.程實(shí)現(xiàn)右圖所示簡單網(wǎng)絡(luò)拓?fù)涞逆溌窢顟B(tài)路由算法。1.1結(jié)點(diǎn)之間的連接關(guān)系固定；1.2鏈路開銷可以由用戶設(shè)定。2.鏈路狀態(tài)算法的實(shí)現(xiàn)：2.1鏈路狀態(tài)消息的交換(可選，簡單起見，可基于靜態(tài)網(wǎng)絡(luò)拓?fù)溥\(yùn)行Dijkstra算法)；2.2網(wǎng)絡(luò)拓?fù)涞拿枋?構(gòu)造；2.3利用Dijkstra算法計(jì)算路由；2.4路由表的輸出。3.網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的描述(數(shù)據(jù)結(jié)構(gòu))，拓?fù)浣Y(jié)構(gòu)利用文件存儲。4.用可視化界面進(jìn)行程序演示。實(shí)驗(yàn)環(huán)境與知識實(shí)驗(yàn)的運(yùn)行環(huán)境Windows7QTcreatorQT4.8編程語言C++實(shí)驗(yàn)的基礎(chǔ)知識算法思想按路徑長度遞增次序產(chǎn)生最短路徑算法：把頂點(diǎn)集合V分成兩組：（1）S：已求出最短路徑的頂點(diǎn)的集合（初始時(shí)只含有源點(diǎn)V0）（2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：（1）從源點(diǎn)V0到S中其他各頂點(diǎn)的最短路徑長度都不大于從V0到T中任何頂點(diǎn)的最短路徑長度（2）每個頂點(diǎn)對應(yīng)一個距離值S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長度T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長度依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和（反證法可證）實(shí)驗(yàn)程序的設(shè)計(jì)流程設(shè)計(jì)思路算法思路的設(shè)計(jì)首先，引進(jìn)一個輔助向量D，它的每個分量D表示當(dāng)前所找到的從始點(diǎn)v到每個終點(diǎn)vi的最短路徑的長度。如D[3]=2表示從始點(diǎn)v到終點(diǎn)3的路徑相對最小長度為2。這里強(qiáng)調(diào)相對就是說在算法過程中D的值是在不斷逼近最終結(jié)果但在過程中不一定就等于最短路徑長度。它的初始狀態(tài)為：若從v到vi有弧，則D為弧上的權(quán)值；否則置D為∞。顯然，長度為D[j]=Min{D|vi∈V}的路徑就是從v出發(fā)的長度最短的一條最短路徑。此路徑為(v,vj)。那么，下一條長度次短的最短路徑是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權(quán)值，或者是D[j]和從vj到vk的弧上的權(quán)值之和。一般情況下，假設(shè)S為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為X）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D|vi∈V-S}其中，D或者是弧(v,vi)上的權(quán)值，或者是D[k](vk∈S)和弧(vk,vi)上的權(quán)值之和。迪杰斯特拉算法描述如下：1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)vi可能達(dá)到的最短路徑長度的初值為D=arcs[LocateVex(G,v),i]vi∈V2）選擇vj，使得D[j]=Min{D|vi∈V-S}3）修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長度。1.2界面的設(shè)計(jì)與實(shí)現(xiàn)利用QTmainwindow為載體，添加spinbox作為輸入來源，tableview作為輸出控件。與迪杰斯特拉算法類交互。流程圖設(shè)開始開始輸入路由間的鏈路的值輸入路由間的鏈路的值調(diào)用dijkstra算法選擇路由調(diào)用dijkstra算法選擇路由更新鏈路信息更新鏈路信息輸出路由表輸出路由表是否退出否是否退出是退出退出關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)和代碼關(guān)鍵的數(shù)據(jù)結(jié)構(gòu) 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();};采用的是矩陣來存放網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，其中0表示自身，N表示的是兩個路由之間彼此沒有直接的聯(lián)系，其中i1i2i3i4i5的值是在程序的執(zhí)行過程中動態(tài)分配intlength[4][4]={0};該矩陣是用來存放兩個路由之間的最短路徑長introute[4][4]={0};該矩陣是用來存放下一跳的路由關(guān)鍵的代碼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++;}

上面的部分代碼是用來實(shí)現(xiàn)dijkstra算法的，通過這個算法可以求出彼此兩個路偶之間的最短路徑的值并且的出嚇一跳的路由編號，將結(jié)果保存到到矩陣中，從而得出了每個路由的路由表。程序的