圖的最短路徑拓?fù)渑判蚝完P(guān)鍵路徑

本文格式為Word版，下載可任意編輯——圖的最短路徑拓?fù)渑判蚝完P(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)課程輔導(dǎo)

圖的最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑

一、最短路徑

由圖的概念可知，在一個(gè)圖中，若從一頂點(diǎn)到另一頂點(diǎn)存在著一條路徑(這里只探討無回路的簡單路徑)，則稱該路徑長度為該路徑上所經(jīng)過的邊的數(shù)目，它也等于該路徑上的頂點(diǎn)數(shù)減1。由于從一頂點(diǎn)到另一頂點(diǎn)可能存在著多條路徑，每條路徑上所經(jīng)過的邊數(shù)可能不同，即路徑長度不同，我們把路徑長度最短（即經(jīng)過的邊數(shù)最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。

上面所述的圖的最短路徑問題只是對(duì)無權(quán)圖而言的，若圖是帶權(quán)圖，則把從一個(gè)頂點(diǎn)i到圖中其余任一個(gè)頂點(diǎn)j的一條路徑上所經(jīng)過邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長度，從vi到vj可能不止一條路徑，我們把帶權(quán)路徑長度最短（即其值最小）的那條路徑也稱作最短路徑，其權(quán)值也稱作最短路徑長度或最短距離。

例如，在圖3-1中，從v0到v4共有三條路徑：{0,4},{0,1,3,4}和{0,1,2,4}，其帶權(quán)路徑長度分別為30,23和38，可知最短路徑為{0,1,3,4}，最短距離為23。

圖3-1帶權(quán)圖和對(duì)應(yīng)的鄰接矩陣

1

實(shí)際上，這兩類最短路徑問題可合并為一類，這只要把無權(quán)圖上的每條邊標(biāo)上數(shù)值為1的權(quán)就歸屬于有權(quán)圖了，所以在以后的探討中，若不特別指明，均認(rèn)為是求帶權(quán)圖的最短路徑問題。

求圖的最短路徑問題用途很廣。例如，若用一個(gè)圖表示城市之間的運(yùn)輸網(wǎng)，圖的頂點(diǎn)代表城市，圖上的邊表示兩端點(diǎn)對(duì)應(yīng)城市之間存在著運(yùn)輸線，邊上的權(quán)表示該運(yùn)輸線上的運(yùn)輸時(shí)間或單位重量的運(yùn)費(fèi)，考慮到兩城市間的海拔高度不同，流水方向不同等因素，將造成來回運(yùn)輸時(shí)間或運(yùn)費(fèi)的不同，所以這種圖尋常是一個(gè)有向圖。如何能夠使從一城市到另一城市的運(yùn)輸時(shí)間最短或者運(yùn)費(fèi)最省呢？這就是一個(gè)求兩城市間的最短路徑問題。

求圖的最短路徑問題包括兩個(gè)方面：一是求圖中一頂點(diǎn)到其余各頂點(diǎn)的最短路徑，二是求圖中每對(duì)頂點(diǎn)之間的最短路徑。下面分別進(jìn)行探討。

1.從一頂點(diǎn)到其余各頂點(diǎn)的最短路徑

對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的圖G，從某一頂點(diǎn)vi(稱此為源點(diǎn))到其余任一頂點(diǎn)vj(稱此為終點(diǎn))的最短路徑，可能是它們之間的邊(i,j)或，也可能是經(jīng)過k個(gè)（1≤k≤n-2，最多經(jīng)過除源點(diǎn)和終點(diǎn)之外的所有頂點(diǎn)）中間頂點(diǎn)和k+1條邊所形成的路徑。例如在圖3-1中，從v0到v1的最短路徑就是它們之間的有向邊，其長度為3；從v0到v4的最短路徑經(jīng)過兩個(gè)中間點(diǎn)v1和v3以及三條有向邊,和，其長度為23。

那么，如何求出從源點(diǎn)i到圖中其余每一個(gè)頂點(diǎn)的最短路徑呢？狄克斯特拉(Dijkstra)于1959年提出了解決此問題的一般算法，具體做法是依照從源點(diǎn)到其余每一頂點(diǎn)的最短路徑長度的升序依次求出從源點(diǎn)到各頂點(diǎn)的最短路徑及長度，每次求出從源點(diǎn)i到一個(gè)終點(diǎn)m的最短路徑及長度后，都要以該頂點(diǎn)m作為新考慮的中間點(diǎn)，用vi到vm的最短路徑和最短路徑長度對(duì)vi到其它尚未求出最短路徑的那些終點(diǎn)的當(dāng)前最短路徑及長度作必要地修改，使之成為當(dāng)前新的最短路徑和最短路徑長度，當(dāng)進(jìn)行n-2次（因最多考慮n-2個(gè)中間點(diǎn)）后算法終止。

狄克斯特拉算法需要設(shè)置一個(gè)集合，假定用S表示，其作用是保存已

2

求得最短路徑的終點(diǎn)序號(hào)，它的初值中只有一個(gè)元素，即源點(diǎn)i，以后每求出一個(gè)從源點(diǎn)i到終點(diǎn)m的最短路徑，就將該頂點(diǎn)m并入S集合中，以便作為新考慮的中間點(diǎn)；還需要設(shè)置一個(gè)整型（假定權(quán)值類型為整型）數(shù)組dist[MaxVertexNum]，該數(shù)組中的第j個(gè)元素dist[j]用來保存從源點(diǎn)i到終點(diǎn)j的目前最短路徑長度，它的初值為(i,j)或邊上的權(quán)值，若vi到vj沒有邊，則權(quán)值為MaxValue，以后每考慮一個(gè)新的中間點(diǎn)時(shí)，dist[j]的值可能變?。涣硗?，再設(shè)置一個(gè)與dist數(shù)組相對(duì)應(yīng)的、類型為adjlist的鄰接表表頭向量數(shù)組path，該數(shù)組中的第j個(gè)元素path[j]指向一個(gè)單鏈表，該單鏈表中保存著從源點(diǎn)i到終點(diǎn)j的目前最短路徑，即一個(gè)頂點(diǎn)序列，當(dāng)vi到vj存在著一條邊時(shí)，則path[j]初始指向由頂點(diǎn)i和j構(gòu)成的單鏈表，否則path[j]的初值為空。

此算法的執(zhí)行過程是：首先從S集合以外的頂點(diǎn)（即待求出最短路徑的終點(diǎn)）所對(duì)應(yīng)的dist數(shù)組元素中，查找出其值最小的元素，假定為dist[m]，該元素值就是從源點(diǎn)i到終點(diǎn)m的最短路徑長度(證明從略)，對(duì)應(yīng)path數(shù)組中的元素path[m]所指向的單鏈表鏈接著從源點(diǎn)i到終點(diǎn)m的最短路徑，即經(jīng)過的頂點(diǎn)序列或稱邊序列；接著把已求得最短路徑的終點(diǎn)m并入集合S中；然后以vm作為新考慮的中間點(diǎn)，對(duì)S集合以外的每個(gè)頂點(diǎn)j，比較dist[m]+GA[m][j]（GA為圖G的鄰接矩陣）與dist[j]的大小，若前者小于后者，說明參與了新的中間點(diǎn)vm之后，從vi到vj的路徑長度比原來變短，應(yīng)用它替換dist[j]的原值，使dist[j]始終保持到目前為止最短的路徑長度，同時(shí)把path[m]單鏈表復(fù)制到path[j]上，并在其后插入vj結(jié)點(diǎn)，使之構(gòu)成從源點(diǎn)i到終點(diǎn)j的目前最短路徑。重復(fù)n-2次上述運(yùn)算過程，即可在dist數(shù)組中得到從源點(diǎn)i到其余每個(gè)頂點(diǎn)的最短路徑長度，在path數(shù)組中得到相應(yīng)的最短路徑。為了簡便起見，可采用一維數(shù)組s[n]來保存已求得最短路徑的終點(diǎn)的集合S，具體做法是：若頂點(diǎn)j在集合S中，則令數(shù)組元素s[j]的值取1，否則取0。這樣，當(dāng)判斷一個(gè)頂點(diǎn)j是否在集合S以外時(shí)，只要判斷對(duì)應(yīng)的數(shù)組元素s[j]是否為0即可。

例如，對(duì)于圖3-1來說，若求從源點(diǎn)v0到其余各頂點(diǎn)的最短路徑，則開始時(shí)三個(gè)一維數(shù)組s,dist和path的值為：

3

01234s10000dist03∞∞30pathv0,v1v0,v4

下面開始進(jìn)行第一次運(yùn)算，求出從源點(diǎn)v0到第一個(gè)終點(diǎn)的最短路徑。首先從s元素為0的對(duì)應(yīng)dist元素中，查找出值最小的元素，求得dist[2]的值最小，所以第一個(gè)終點(diǎn)為v1,最短距離為dist[2]=3，最短路徑為path[2]={0,1}，接著把s[1]置為1，表示v1已參與S集合中，然后以v1為新考慮的中間點(diǎn)，對(duì)s數(shù)組中元素為0的每個(gè)頂點(diǎn)j（此時(shí)2≤j≤4）的目前最短路徑長度dist[j]和目前最短路徑path[j]進(jìn)行必要地修改，因dist[1]+GA[1][2]=3+25=28，小于dist[2]=∞，所以將28賦給dist[2]，將path[1]并上v2后賦給path[2]，同理因dist[1]+GA[1][3]=3+8=11，小于dist[3]=∞，所以將11賦給dist[3]，將path[1]并上v3后賦給path[3]，最終再看從v0到v4，以v1作為新考慮的中間點(diǎn)的狀況，由于v1到v4沒有出邊，所以GA[1][4]=∞，故dist[1]+GA[1][4]不小于dist[4]，因此dist[4]和path[4]無需修改，應(yīng)維持原值。至此，第一次運(yùn)算終止，三個(gè)一維數(shù)組的當(dāng)前狀態(tài)為：

01234s

11000dist

03281130path

v0,v1v0,v1,v2v0,v1,v3v0,v4

下面開始進(jìn)行其次次運(yùn)算，求出從源點(diǎn)v0到其次個(gè)終點(diǎn)的最短路徑。首先從s數(shù)組中元素為0的對(duì)應(yīng)dist元素中，查找出值最小的元素，求得dist[3]的值最小，所以其次個(gè)終點(diǎn)為v3,最短距離為dist[3]=11，最短路徑為path[3]={0,1,3}，接著把s[3]置為1，然后以v3作為新考慮的中間點(diǎn)，對(duì)s中元素為0的每個(gè)頂點(diǎn)j（此時(shí)j=3,5）的dist[j]和path[j]進(jìn)行必要的修改，因dist[3]+GA[3][2]=11+4=15，小于dist[2]=28，所以將15賦給dist[2]，將path[3]并上v2后賦給path[2]，同理，因

4

dist[3]+GA[3][4]=11+12=23，小于dist[4]=30，所以將23賦給dist[4]，將path[3]并上v4后賦給path[4]。至此，其次次運(yùn)算終止，三個(gè)一維數(shù)組的當(dāng)前狀態(tài)為：

01234s

11010dist

03151123path

v0,v1v0,v1,v3,v2v0,v1,v3v0,v1,v3,v4

下面開始進(jìn)行第三次運(yùn)算，求出從源點(diǎn)v0到第三個(gè)終點(diǎn)的最短路徑。首先從s中元素為0的對(duì)應(yīng)dist元素中，查找出值最小的元素為dist[2]，所以求得第三個(gè)終點(diǎn)為v2，最短距離為dist[2]=15，最短路徑為path[2]={0,1,3,2}，接著把s[2]置為1，然后以v2作為新考慮的中間點(diǎn)，對(duì)s中元素為0的每個(gè)頂點(diǎn)j（此時(shí)只有v4一個(gè)）的dist[j]和path[j]進(jìn)行必要的修改，因dist[2]+GA[2][4]=15+10=25，大于dist[4]=23，所以無需修改，原值不變。至此，第三次運(yùn)算終止，三個(gè)一維數(shù)組的當(dāng)前狀態(tài)為：

01234s11110dist0