./計算機網(wǎng)絡中迪克斯屈拉最短路徑算法的程序實現(xiàn)與應用沈敬紅S140131109XX郵電大學通信與信息工程學院摘要：本文首先介紹了圖論的發(fā)展歷程,介紹了圖論在實際問題中的應用。其次,介紹了圖論中最短路徑的問題與相關內(nèi)容,介紹了計算機網(wǎng)絡中服務器之間存在的最短路徑問題。然后,介紹了迪克斯屈拉〔Dijkstra〕最短路徑算法。最后,依據(jù)算法的思想,分別實現(xiàn)了Dijkstra算法在求解計算網(wǎng)絡最短路徑的應用程序。關鍵詞：最短路徑服務器Dijkstra算法程序Abstractinthispaper,wefirstlyintroducetheprocessoftheoryofgraph.secondly,wegivetheintroductionoftheproblemofshortestpathandrelatedcontent,andtheapplicationofnetworkswhichalotofsevershavetosearchtheshortestpath.Andthenshowstheoneofshortestpathalgorithms:TheDijkstraalgorithm.Finally,accordingtotheideasofthisalgorithm,weputforwardamethodtoachievetheprocedureusinginthenetworks.KeywordShortest—pathsSeverDijkstraProgram1、引言圖論<GraphTheory>是數(shù)學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點與連接兩點的線所構成的圖形,這種圖形通常用來描述某些事物之間的某種特定關系,用點代表事物,用連接兩點的線表示相應兩個事物間具有這種關系。圖論本身是應用數(shù)學的一部份,因此,歷史上圖論曾經(jīng)被好多位數(shù)學家各自獨立地建立過。關于圖論的文字記載最早出現(xiàn)在歐拉1736年的論著中,他所考慮的原始問題有很強的實際背景。圖論的發(fā)展已有200多年的歷史,它發(fā)源于18世紀普魯士的柯尼斯堡。當?shù)氐木用裣胫滥芊駨娜我庖魂懙爻霭l(fā),走遍聯(lián)接該城的7座橋又回到原地?其條件是每座橋都經(jīng)過一次并且只經(jīng)過一次?！簿唧w見"七橋問題"〕在加權連通圖中,尋求最短路徑的問題有其實際背景,例如在某一國家或地區(qū),城市與城市之間都互相連通,從一個城市到達另一城市存在著多條路徑,如何實現(xiàn)最短的路徑完成兩個城市之間的貨物運輸就是一個解決圖論中實現(xiàn)最短路徑的問題。同樣,比如需要架設電網(wǎng)、通信網(wǎng)絡以與其他的有線網(wǎng)絡,基于全網(wǎng)的考慮之下,點和點之間怎樣架設一條最短的線路就是一個實際的最短路問題。按照圖論的表述,在一個圖中,兩點之間的路徑可能有很多條,且每條路徑所經(jīng)過的邊數(shù)可能是不同的,如果是網(wǎng)絡,每條路徑的各邊權數(shù)之和也可能是不同的,怎樣找到一條頂點對頂點之間的各邊權數(shù)之和為最小的路徑問題稱為最短路問題[1]。本文提出了一個計算機網(wǎng)絡中服務器之間最短路徑的問題背景,并在迪克斯屈拉〔Dijkstra〕算法的基礎上,實現(xiàn)算法在服務器之間尋求最短路徑的程序設計。2、圖論相關概念[1,2]：無向圖：每一條邊都是無向邊的圖稱為無向圖。鏈：設u和v是任意圖G的頂點,圖G的一條u-v鏈〔chain或walk〕是有限的頂點和邊交替的序列u0e1u1e2…un-1enun<u=u0,v=un>,其中與邊e〔1≤i≤n〕相鄰的兩個頂點ui和ui-1正好是ei的兩個端點。路：內(nèi)部點不同的鏈稱為路〔path〕。圈：兩端點相同的路〔即閉路〕稱為圈或回路。加權圖：邊上有數(shù)的圖稱為加權圖〔weightedgraph〕。若邊e標記數(shù)為k,則稱邊e的權<weight>為k。在加權圖中,鏈〔跡、路〕的長度為鏈〔跡、路〕上的所有邊的權值之和.鄰接矩陣：設G＝<V,E>是任意圖,規(guī)定n階方陣A=〔aij〕為G的鄰接矩陣,其中aij為圖G中以xi為起點且以yj為終點的邊的數(shù)目。邊權矩陣：設G＝<V,E>是n階加權簡單圖,規(guī)定D=〔dij〕m×n是圖的加權矩陣,即dij＝w〔i,j〕。若結點i到結點j無邊可連〔在有向圖中是方向不一致〕時,取dij＝∞。3、問題描述在現(xiàn)有的Internet中存在著大量的不同種類的服務器[7],這些服務器為用戶提供不同種類的數(shù)據(jù)服務,在服務器與服務器之間存在著數(shù)據(jù)的交流。如果,我們將各個服務器看做是一個頂點,將服務器與服務器之間的看做是一條邊,則服務器組成的網(wǎng)絡就是一個無向連通圖[9]。在這個圖上,服務器與服務器之間的鏈路上都存在著一定的時延,由于網(wǎng)絡環(huán)境的不同,每個邊上的時延均不相同,有的只有幾十毫秒,有的卻達到上百毫秒,這些毫秒數(shù)就可以看做邊的權值,如何選擇最佳的路徑使得服務器與服務器之間的數(shù)據(jù)交換所需時間最短的問題,就變成了求解在無向連通加權圖中尋求最短路徑的問題。如下圖為網(wǎng)絡服務器之間的拓撲圖：〔注：S1-S6為網(wǎng)絡服務器節(jié)點,權值為10ms/每單位值〕4、迪克斯屈拉〔Dijkstra〕算法實現(xiàn)4.1Dijkstra算法[1]描述：算法基本思想：一個頂點V1作為源點,求該頂點到其他各頂點的最短路徑,迪克斯屈拉提出了一個按路徑長度遞增的順序產(chǎn)生最短路徑的方法。此方法的基本思想是：把圖中所有結點分成兩組,第一組包括已確定最短路徑的頂點,第二組包括尚未確定最短路徑的頂點,按最短路徑長度遞增的順序逐個把第二組的頂點加到第一組中,直到從V1出發(fā)可以到達的所有頂點都已包括在第一組中。在這過程中,總保持從V1到第一組各頂點的最短路徑都不大于從V1到第二組的任何頂點的最短路徑長度。另外,每個頂點對應一個距離值,第一組的頂點對應的距離值就是從V1到此頂點的最短路徑長度,第二組的頂點對應的距離值是從V1到此頂點的只包括第一組的頂點為中間頂點的最短路徑長度[2]。實現(xiàn)過程描述：一開始第一組只包括頂點V1,第二組包括其他所有頂點。V1對應的距離值為0,第二組的頂點對應的距離值是這樣確定的：若圖中有弧〈V1,Vj〉,則Vj的距離為此弧的權值,否則Vj的距離為∞〔或用一個很大的數(shù)表示〕。然后每次從第二組的頂點中選一個其距離值為最小Vm的加入到第一組中,每往第一組中加入一個頂點Vm,就要對第二組中的各個頂點的距離值進行一次修正。若加進Vm做中間結點,使從V1到Vj的最短路徑比不加Vm的路徑要短,則要修改Vj的距離值。修改后再選距離值最小的頂點加入到第一組中。如此進行下去,直到圖中所有頂點都包括在第一組中,或再也沒有可加入到第一組中的頂點存在為止。4.2Dijkstra算法對問題描述與實現(xiàn)：六個服務器節(jié)點S1、S2、S3、S4、S5和S6,分別如圖表示,各個端點之間的權值標于節(jié)點間的聯(lián)線之上。.G=<V,E>〔1〕此有加權圖的鄰接矩陣表示為：〔2〕對上述問題實現(xiàn)迪克斯屈拉算法的程序過程表述為：有鄰接矩陣adjacent表示,若〈S1,Sj〉是圖中的弧,則adjacent[i,j]的值等于邊上所帶的權值,否則adjacent[i,j]等于一個很大的正數(shù)infinity_value<在程序中用9999表示>。開始時adjacent[i,j]＝0表示頂點j未在第一組中,處理中用s[j]＝1標志第j個頂點已進入第一組。邊的權值為adjacent對應的位置的值,數(shù)組元素的下標等于相關聯(lián)頂點序號。數(shù)組distance_shortest[n]的每個元素為頂點的距離值,pre_node[n]的每個元素為從V1到該頂點的路徑上此頂點的前一個頂點的序號,若從V1到該頂點無路徑,則用0作為其前一個頂點序號。算法結束時,沿著頂點Vj對應的pre_node[j－1]追溯,就能確定V1到Vj最短路徑,其最短路徑長度等于distance_shortest[j－1]。此算法起始頂點也可以不是V1,起始頂點的序號由變量k給出〔即從頂點Vk出發(fā)〕。源點為Vk<其中k為1>〔3〕解決上述問題迪克斯屈拉程序源代碼為：#include<iostream>usingnamespacestd;//定義常量#definemaxnum50//最大節(jié)點數(shù)目#defineinfinity_value9999//無窮大值//定義數(shù)組,用于存放集合中的數(shù)據(jù)intdistance_shortest[maxnum];//存放當前節(jié)點到達源節(jié)點的最短路徑值intpre_node[maxnum];//存放當前點的前一個節(jié)點intadjacent[maxnum][maxnum];//鄰接陣,存放邊值intn;//節(jié)點個數(shù)//Dijkstra算法函數(shù)//n節(jié)點個數(shù),source源節(jié)點voidDijkstra<intn,intsource,int*distance_shortest,int*pre_node,intadjacent[maxnum][maxnum]>{bools[maxnum];//定義存放點的集合//初始化for<inti=1;i<=n;i++>{distance_shortest[i]=adjacent[source][i];//賦值s[i]=0;//將集合置為空if<distance_shortest[i]==infinity_value>{pre_node[i]=0;}elsepre_node[i]=1;}s[source]=1;//source加入集合distance_shortest[source]=0;//初始值為0//開始迭代,迭代n-1次for<i=2;i<=n;i++>{inttemp=infinity_value;intu=source;//找出還未使用的點j的到源的最小路徑中distance_shortest[j];for<intj=1;j<=n;j++>{if<<s[j]==0>&&<distance_shortest[j]<temp>>{u=j;//保存最小值的號temp=distance_shortest[j];}}s[u]=1;//加入最短路徑的點//更新distance_shortestfor<j=1;j<=n;j++>{if<<s[j]==0>&&<adjacent[u][j]<infinity_value>>{intnewdist=distance_shortest[u]+adjacent[u][j];if<newdist<distance_shortest[j]>{distance_shortest[j]=newdist;pre_node[j]=u;}}}}}//統(tǒng)計路徑函數(shù)voidsearchPath<int*pre_node,intsource,intdestination>{intque[maxnum];intord=1;que[ord]=destination;ord++;inttmp=pre_node[destination];while<tmp!=source>{que[ord]=tmp;ord++;tmp=pre_node[tmp];}que[ord]=source;for<inti=ord;i>=1;--i>if<i!=1>cout<<que[i]<<"->";elsecout<<que[i]<<endl;}voidmain<>{cout<<"請輸入圖的節(jié)點的個數(shù)："<<endl;cin>>n;intp,q,len,num;//輸入p,q兩端點與其路徑長度len,num為要統(tǒng)計的源端點//初始化adjacent[][]為infinity_valuefor<inti=1;i<=n;++i>for<intj=1;j<=n;++j>adjacent[i][j]=infinity_value;//錄入圖的邊權值cout<<"請按規(guī)則依次輸入"<<n<<"個節(jié)點相鄰的邊數(shù)！"<<endl;cout<<"例如：請輸入端點號：1"<<endl;cout<<"請輸入另一個端點號：2"<<endl;cout<<"請輸入1號端點和2號端點之間邊的權值：20"<<endl;cout<<"如果錄入結束請按0結束"<<endl;intjudge=1;while<judge>{cout<<"請輸入端點號：";cin>>p;if<p==0>break;cout<<"請輸入另一個端點號：";cin>>q;if<q==0>break;cout<<"請輸入"<<p<<"號端點與"<<q<<"號端點之間的權值：";cin>>len;if<q==0>break;adjacent[q][p]=adjacent[p][q]=len;//無向圖}for<i=1;i<=n;++i>distance_shortest[i]=infinity_value;for<i=1;i<=n;++i>{for<intj=1;j<=n;++j>printf<"%8d",adjacent[i][j]>;printf<"\n">;}cout<<"請輸入要統(tǒng)計的源節(jié)點的端點號：";cin>>num;Dijkstra<n,num,distance_shortest,pre_node,adjacent>;//最短路徑長度for<i=1;i<=n;i++>{if<i!=num>{cout<<num<<"號源端點到"<<i<<"號端點的最短路徑長度值:"<<distance_shortest[i];cout<<",最短路徑為:";searchPath<pre_node,num,i>;}}}〔4〕根據(jù)迪克斯屈拉算法得到的程序運行最后結果為：圖1.程序運行結果圖圖2.程序運行結果圖〔續(xù)〕從上述實例中可以看出,Dijkstra算法是典型的最短路徑路由算法,比較適用于求出圖中一個特定頂點到其他各頂點的最短路。在實際應用中,需要求出任意兩點之間的最短路,比如選路問題,各個城市之間最短的路線；網(wǎng)絡中路由問題,選擇最短時延路徑等等。但是,也可以根據(jù)以上的例子看出,該算法主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。對于頂點數(shù)目比較少的圖來說,迪克斯屈拉算法可以比較方便的得出最短路結果,但是,對于頂點數(shù)目比較多的比較復雜的圖來說,運用這種算法將涉與大量的運算,需要反復重復以上的程序,增加運算的時間復雜度,并且遍歷計算的節(jié)點很多,所以效率低。但是,迪克斯屈拉算法無疑仍是一種優(yōu)秀的算法,可以很好