---圖的最短路徑、拓撲排序和關鍵路徑
一、最短路徑
由圖的概念可知，在乙個圖中，若從一頂點到另一頂點存在著一條路徑(這裡只討論無迴路的簡單路徑)，則稱該路徑長度為該路徑上所經過的邊的數目，它也等於該路徑上的頂點數減1。由於從一頂點到另一頂點可能存在著多條路徑，每條路徑上所經過的邊數可能不同，即路徑長度不同，我們把路徑長度最短（即經過的邊數最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。 上面所述的圖的最短路徑問題只是對無權圖而言的，若圖是帶權圖，則把從乙個頂點i到圖中其餘任乙個頂點j的一條路徑上所經過邊的權值之和定義為該路徑的帶權路徑長度，從vi到vj可能不止一條路徑，我們把帶權路徑長度最短（即其值最小）的那條路徑也稱作最短路徑，其權值也稱作最短路徑長度或最短距離。
例如，在圖3-1中，從v0到v4共有三條路徑：,和，其帶權路徑長度分別為30,23和38，可知最短路徑為，最短距離為23。
圖3-1 帶權圖和對應的鄰接矩陣
實際上，這兩類最短路徑問題可合併為一類，這只要把無權圖上的每條邊標上數值為1的權就歸屬於有權圖了，所以在以後的討論中，若不特別指明，均認為是求帶權圖的最短路徑問題。
求圖的最短路徑問題用途很廣。例如，若用乙個圖表示城市之間的運輸網，圖的頂點代表城市，圖上的邊表示兩端點對應城市之間存在著運輸線，邊上的權表示該運輸線上的運輸時間或單位重量的運費，考慮到兩城市間的海拔高度不同，流水方向不同等因素，將造成來回運輸時間或運費的不同，所以這種圖通常是乙個有向圖。如何能夠使從一城市到另一城市的運輸時間最短或者運費最省呢？
這就是乙個求兩城市間的最短路徑問題。
求圖的最短路徑問題包括兩個方面：一是求圖中一頂點到其餘各頂點的最短路徑，二是求圖中每對頂點之間的最短路徑。下面分別進行討論。
1. 從一頂點到其餘各頂點的最短路徑
對於乙個具有n個頂點和e條邊的圖g，從某一頂點vi(稱此為源點)到其餘任一頂點vj(稱此為終點)的最短路徑，可能是它們之間的邊(i,j)或，也可能是經過k個（1≤k≤n-2，最多經過除源點和終點之外的所有頂點）中間頂點和k+1條邊所形成的路徑。例如在圖3-1中，從v0到v1的最短路徑就是它們之間的有向邊<0,1>，其長度為3；從v0到v4的最短路徑經過兩個中間點v1和v3以及三條有向邊<0,1>,<1,3>和<3,4>，其長度為23。
那麼，如何求出從源點i到圖中其餘每乙個頂點的最短路徑呢？狄克斯特拉(dijkstra)於2023年提出了解決此問題的一般演算法，具體做法是按照從源點到其餘每一頂點的最短路徑長度的公升序依次求出從源點到各頂點的最短路徑及長度，每次求出從源點i到乙個終點m的最短路徑及長度後，都要以該頂點m作為新考慮的中間點，，使之成為當前新的最短路徑和最短路徑長度，當進行n-2次（因最多考慮n-2個中間點）後演算法結束。
狄克斯特拉演算法需要設定乙個集合，假定用s表示，其作用是儲存已求得最短路徑的終點序號，它的初值中只有乙個元素，即源點i，以後每求出乙個從源點i到終點m的最短路徑，就將該頂點m併入s集合中，以便作為新考慮的中間點；還需要設定乙個整型（假定權值型別為整型）陣列dist[maxvertexnum]，該陣列中的第j個元素dist[j]用來儲存從源點i到終點j的目前最短路徑長度，它的初值為(i,j)或邊上的權值，若vi到vj沒有邊，則權值為maxvalue，以後每考慮乙個新的中間點時，dist[j]的值可能變小； 另外，再設定乙個與dist陣列相對應的、型別為adjlist的鄰接表表頭向量陣列path，該陣列中的第j個元素path[j]指向乙個單鏈表，該單鏈表中儲存著從源點i到終點j的目前最短路徑，即乙個頂點序列，當vi到vj存在著一條邊時，則path[j]初始指向由頂點i和j構成的單鏈表，否則path[j]的初值為空。
此演算法的執行過程是：首先從s集合以外的頂點（即待求出最短路徑的終點）所對應的dist陣列元素中，查詢出其值最小的元素，假定為dist[m]，該元素值就是從源點i到終點m的最短路徑長度(證明從略)，對應path陣列中的元素path[m]所指向的單鏈錶鏈接著從源點i到終點m的最短路徑，即經過的頂點序列或稱邊序列；接著把已求得最短路徑的終點m併入集合s中；然後以vm作為新考慮的中間點，對s集合以外的每個頂點j，比較dist[m]+ga[m][j]（ga為圖g的鄰接矩陣）與dist[j]的大小，若前者小於後者，表明加入了新的中間點vm之後，從vi到vj的路徑長度比原來變短，應用它替換dist[j]的原值，使dist[j]始終保持到目前為止最短的路徑長度，同時把path[m]單鏈表複製到path[j]上，並在其後插入vj結點，使之構成從源點i到終點j的目前最短路徑。重複n-2次上述運算過程，即可在dist陣列中得到從源點i到其餘每個頂點的最短路徑長度，在path陣列中得到相應的最短路徑。
為了簡便起見，可採用一維陣列s[n]來儲存已求得最短路徑的終點的集合s，具體做法是：若頂點j在集合s中，則令陣列元素s[j]的值取1，否則取0。這樣，當判斷乙個頂點j是否在集合s以外時，只要判斷對應的陣列元素s[j]是否為0即可。
例如，對於圖3-1來說，若求從源點v0到其餘各頂點的最短路徑，則開始時三個一維陣列s,dist和path的值為：
01234#brbr##end#dist
path
下面開始進行第一次運算，求出從源點v0到第乙個終點的最短路徑。首先從s元素為0的對應dist元素中，查詢出值最小的元素，求得dist[2]的值最小，所以第乙個終點為v1, 最短距離為dist[2]=3，最短路徑為path[2]=，接著把s[1]置為1，表示v1已加入s集合中，然後以v1為新考慮的中間點，對s陣列中元素為0的每個頂點j（此時2≤j≤4）的目前最短路徑長度dist[j]和目前最短路徑path[j]進行必要地修改，因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作為新考慮的中間點的情況，由於v1到v4沒有出邊，所以ga[1][4]=∞，故dist[1]+ga[1][4]不小於dist[4]，因此dist[4]和path[4]無需修改，應維持原值。至此，第一次運算結束，三個一維陣列的當前狀態為：
01234#brbr##end#dist
path
下面開始進行第二次運算，求出從源點v0到第二個終點的最短路徑。首先從s陣列中元素為0的對應dist元素中，查詢出值最小的元素，求得dist[3]的值最小，所以第二個終點為v3, 最短距離為dist[3]=11，最短路徑為path[3]=，接著把s[3]置為1，然後以v3作為新考慮的中間點，對s中元素為0的每個頂點j（此時j=3,5）的dist[j]和path[j]進行必要的修改，因dist[3]+ga[3][2]=11+4=15，小於dist[2]=28，所以將15賦給dist[2]，將path[3]並上v2後賦給path[2]，同理，因dist[3]+ga[3][4]=11+12=23，小於dist[4]=30，所以將23賦給dist[4]，將path[3]並上v4後賦給path[4]。至此，第二次運算結束，三個一維陣列的當前狀態為：
01234#brbr##end#dist
path
下面開始進行第三次運算，求出從源點v0到第三個終點的最短路徑。首先從s中元素為0的對應dist元素中，查詢出值最小的元素為dist[2]，所以求得第三個終點為v2，最短距離為dist[2]=15，最短路徑為path[2]=，接著把s[2]置為1，然後以v2作為新考慮的中間點，對s中元素為0的每個頂點j（此時只有v4乙個）的dist[j]和path[j]進行必要的修改，因dist[2]+ga[2][4]=15+10=25，大於dist[4]=23，所以無需修改，原值不變。至此，第三次運算結束，三個一維陣列的當前狀態為：
01234#brbr##end#dist
path
由於圖中有5個頂點，只需運算3次，即n-2次，雖然此時還有乙個頂點未加入s集合中，但它的最短路徑及最短距離已經最後確定，所以整個運算結束。最後在dist中得到從源v0到每個頂點的最短路徑長度，在path中得到相應的最短路徑。
如果用圖形表示上述過程中每次運算的結果，則對應的圖形分別如圖3-2(b)~(e)所示，其中實線有向邊所指向的頂點為集合s中的頂點，虛線有向邊所指向的頂點為集合s外的頂點；s集合中的頂點上所標數值為從源點v0到該頂點的最短路徑長度，從源點v0到該頂點所經過的有向邊為從v0到該頂點的最短路徑；s集合外的頂點上所標數值為從源點v0到該頂點的目前最短路徑長度，從v0到該頂點所經過的有向邊為從v0到該頂點的目前最短路徑。為了便於對照分析，把圖3-1(a)重畫於圖3-2(a)中。
圖3-2 利用狄克斯特拉演算法求最短路徑的圖形說明
根據以上分析和舉例，不難給出狄克斯特拉演算法的描述：
void dijkstra(adjmatrix ga, int dist,
adjlist path, int i, int n)
利用狄克斯特拉演算法求圖ga中從頂點i到其餘每個頂點間的
最短距離和最短路徑，它們分別被存於陣列dist和path陣列中
{int j,k,w,m;
定義作為集合使用的動態陣列s
資料結構課程要點
1 緒論 演算法的概念 幾種常見的資料結構型別 線 樹 圖等 程式的時間複雜度和空間複雜度 2 線性表 線性表的定義 線性表的順序和鏈式儲存結構 兩種儲存結構上操作的時間效能分析 3 棧 佇列 棧和佇列操作的特點 棧和佇列的幾個基本操作 4 串 串的定義及相關概念 5 陣列 求二維資料按行 列儲存時...
資料結構課程總結
1 知識點概述 1 資料結構和演算法 本章作為全書的導引，全面介紹了相關概念，如資料 資料元素 資料型別以及資料結構的定義。其中，資料結構包括邏輯結構 儲存結構和運算集合。邏輯結構分為四類 集合型 線性 樹形和圖形結構 資料元素的儲存結構分為 順序儲存 鏈結儲存 索引儲存和雜湊儲存四類 最後介紹演算...
資料結構專科輔導七
查詢的輔導練習題及解答 一 單項選擇題 1 若查詢每個元素的概率相等，則在長度為n的順序表上查詢任一元素的平均查詢長度為 a n b n 1 c n 1 2 d n 1 2 2.對長度為10的順序表進行查詢，若查詢前面5個元素的概率相同，均為1 8，查詢後面5個元素的概率相同，均為3 40，則查詢任...