迪克斯屈拉最短路徑算法圖論論文正稿

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