迪杰斯特拉算法和Floyd算法實(shí)現(xiàn)無向圖的最短路徑的計(jì)算和求解

-1-摘要本次課程設(shè)計(jì)主要核心為利用迪杰斯特拉算法和Floyd算法實(shí)現(xiàn)無向圖的最短路徑的計(jì)算和求解。要求理解算法的具體實(shí)現(xiàn)流程、學(xué)會(huì)正確使用該算法求解實(shí)際問題。本次課程設(shè)計(jì)具體內(nèi)容是：通過對(duì)兩個(gè)算法的理解與應(yīng)用來比較兩個(gè)算法的優(yōu)缺點(diǎn)。本程序要求結(jié)合最短路算法以及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)的定義和使用，實(shí)現(xiàn)一個(gè)最短路徑算法的簡單應(yīng)用。本課程設(shè)計(jì)是對(duì)書本知識(shí)的簡單應(yīng)用，以此培養(yǎng)大家用書本知識(shí)解決實(shí)際問題的能力；培養(yǎng)實(shí)際工作所需要的動(dòng)手能力；培養(yǎng)以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件。關(guān)鍵字：迪杰斯特拉算法，F(xiàn)loyd算法，最短路徑，算法設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)目錄TOC\o"1-3"\h\u613摘要 113789一、Dijkstra算法 3221581.1定義概覽 3277461.2算法描述 319541.2.1算法思想： 346991.1.2算法步驟 4175871.3算法代碼實(shí)現(xiàn) 5159501.4算法實(shí)例 618181二、Floyd算法 856272.1定義概覽 8206612.2算法描述 8166132.2.1算法思想原理 824812.3算法代碼實(shí)現(xiàn) 1113286三、結(jié)論 1230055四、參考文獻(xiàn) 13一、Dijkstra算法1.1定義概覽Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊。問題描述：在無向圖G=(V,E)中，假設(shè)每條邊E[i]的長度為w[i]，找到由頂點(diǎn)V0到其余各點(diǎn)的最短路徑。

1.2算法描述1.2.1算法思想：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合V分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合（用S表示，初始時(shí)S中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑,就將加入到集合S中，直到全部頂點(diǎn)都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。1.1.2算法步驟：a.初始時(shí)，S只包含源點(diǎn)，即S＝{v}，v的距離為0。U包含除v外的其他頂點(diǎn)，即:U={其余頂點(diǎn)}，若v與U中頂點(diǎn)u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點(diǎn)，則<u,v>權(quán)值為∞。b.從U中選取一個(gè)距離v最小的頂點(diǎn)k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。c.以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v到頂點(diǎn)u的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。d.重復(fù)步驟b和c直到所有頂點(diǎn)都包含在S中。

執(zhí)行動(dòng)畫過程如下圖1.3算法代碼實(shí)現(xiàn)：constintMAXINT=32767;constintMAXNUM=10;intdist[MAXNUM];intprev[MAXNUM];

intA[MAXUNM][MAXNUM];

voidDijkstra(intv0)

{

boolS[MAXNUM];//判斷是否已存入該點(diǎn)到S集合中

intn=MAXNUM;

for(inti=1;i<=n;++i){

dist[i]=A[v0][i];

S[i]=false;//初始都未用過該點(diǎn)

if(dist[i]==MAXINT)

prev[i]=-1;

else

prev[i]=v0;

}

dist[v0]=0;

S[v0]=true;

for(inti=2;i<=n;i++)

{

intmindist=MAXINT;

intu=v0;//找出當(dāng)前未使用的點(diǎn)j的dist[j]最小值

for(intj=1;j<=n;++j)

if((!S[j])&&dist[j]<mindist)

{

u=j;//u保存當(dāng)前鄰接點(diǎn)中距離最小的點(diǎn)的號(hào)碼

mindist=dist[j];

}

S[u]=true;

for(intj=1;j<=n;j++)

if((!S[j])&&A[u][j]<MAXINT)

{

if(dist[u]+A[u][j]<dist[j])//在通過新加入的u點(diǎn)路徑找到離v0點(diǎn)更短的路徑{

dist[j]=dist[u]+A[u][j];//更新dist

prev[j]=u;//記錄前驅(qū)頂點(diǎn)}

}

}

}1.4算法實(shí)例先給出一個(gè)無向圖用Dijkstra算法找出以A為起點(diǎn)的單源最短路徑步驟如下

二、Floyd算法2.1定義概覽Floyd-Warshall算法（Floyd-Warshallalgorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題，同時(shí)也被用于計(jì)算有向圖的傳遞閉包。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N3)，空間復(fù)雜度為O(N2)。

2.2算法描述2.2.1算法思想原理：

Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋（這個(gè)詮釋正是動(dòng)態(tài)規(guī)劃最富創(chuàng)造力的精華所在）

從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j)=Dis(i,k)+Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。2.2.2算法描述：a.從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。b.對(duì)于每一對(duì)頂點(diǎn)u和v，看看是否存在一個(gè)頂點(diǎn)w使得從u到w再到v比己知的路徑更短。如果是更新它。2.2.3Floyd算法過程矩陣的計(jì)算十字交叉法方法：兩條線，從左上角開始計(jì)算一直到右下角如下所示給出矩陣，其中矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點(diǎn)之間最短路徑所必須經(jīng)過的點(diǎn)相應(yīng)計(jì)算方法如下：最后A3即為所求結(jié)果。

2.3算法代碼實(shí)現(xiàn)typedefstruct

{

charvertex[VertexNum];//頂點(diǎn)表

intedges[VertexNum][VertexNum];//鄰接矩陣,可看做邊表

intn,e;//圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)}MGraph;

voidFloyd(MGraphg)

{

intA[MAXV][MAXV];

intpath[MAXV][MAXV];

inti,j,k,n=g.n;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{

A[i][j]=g.edges[i][j];

path[i][j]=-1;

}

for(k=0;k<n;k++)

{

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(A[i][j]>(A[i][k]+A[k][j]))

{

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;

}

}

}三、結(jié)論Dijkstra算法求單源、無負(fù)權(quán)的最短路時(shí)效性較好，時(shí)間復(fù)雜度為O（V*V+E）,可以用優(yōu)先隊(duì)列進(jìn)行優(yōu)化，優(yōu)化后時(shí)間復(fù)雜度變?yōu)?（v*lgn）。源點(diǎn)可達(dá)的話，O（V*lgV+E*lgV）=>O（E*lgV）。當(dāng)是稀疏圖的情況時(shí)，此時(shí)E=V*V/lgV，所以算法的時(shí)間復(fù)雜度可為O（V^2）?？梢杂脙?yōu)先隊(duì)列進(jìn)行優(yōu)化，優(yōu)化后時(shí)間復(fù)雜度變?yōu)?（v*lgn）。Floyd算法求多源、無負(fù)權(quán)邊的最短路。用矩陣記錄圖。時(shí)效性較差，時(shí)間復(fù)雜度O(V^3)。Floyd-Warshall算法（Floyd-Warshallalgorithm）是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。Floyd-Warshall算法的時(shí)間復(fù)雜度為O(N^3)，空間復(fù)雜度為O(N^2)。Floyd-Warshall的原理是動(dòng)態(tài)規(guī)劃：設(shè)Di,j,k為從i到j(luò)的只以(1..k)集合中的節(jié)點(diǎn)為中間節(jié)點(diǎn)的最短路徑的長度。若最短路徑經(jīng)過點(diǎn)k，則Di,j,k=Di,k,k-1+Dk,j,k-1；若最短路徑不經(jīng)過點(diǎn)k，則Di,j,k=Di,j,k-1。因此，Di,j,k=min(Di,k,k-1+Dk,j,k-1,Di,j,k-1)。在實(shí)際算法中，為了節(jié)約空間，可以直接在原來空間