鏈路狀態路由算法的實現實驗內容與要求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算法的，通過這個算法可以求出彼此兩個路偶之間的最短路徑的值并且的出嚇一跳的路由編號，將結果保存到到矩陣中，從而得出了每個路由的路由表。程序的