【文章內(nèi)容簡介】 合內(nèi)哪個頂點 最近 (即權(quán)值最小 )。 ? 例子 ? 若選擇從頂點 0出發(fā)，即 u0 = 0，則兩個輔助數(shù)組的初始狀態(tài)為： ? 然后反復(fù)做以下工作： ? 在 lowcost [ ]中選擇 nearvex[i] ? 1 amp。amp。 lowcost[i]最小的邊 i 用 v 標(biāo)記它。則選中的權(quán)值最小的邊為 (nearvex[v], v)，相應(yīng)的權(quán)值為 lowcost[v]。 ? 將 nearvex[v] 改為 1, 表示它已加入生成樹頂點集合。將邊 ( nearvex[v], v, lowcost[v] ) 加入生成樹的邊集合。 ? 取 lowcost[i] = min{ lowcost[i], Edge[v][i] }，即用生成樹頂點集合外各頂點 i 到剛加入該集合的新頂點 v 的距離 Edge[v][i] 與原來它們到生成樹頂點集合中頂點的最短距離 lowcost[i] 做比較 , 取距離近的作為這些集合外頂點到生成樹頂點集合內(nèi)頂點的最短距離。 ? 如果生成樹頂點集合外頂點 i 到剛加入該集合的新頂點 v 的距離比原來它到生成樹頂點集合中頂點的最短距離還要近，則修改 nearvex[i]：nearvex[i] = v。表示生成樹外頂點 i到生成樹內(nèi)頂點 v當(dāng)前距離最近。 繼續(xù)重復(fù)得 ： 頂點 5加入生成樹頂點集合： v = 5 v = 4 最后生成樹中邊集合里存入得各條邊為 ： (0, 5, 10), (5, 4, 25), (4, 3, 22), (3, 2, 12), (2, 1, 16), (1, 6, 14) 利用普里姆算法建立最小生成樹 void Graphstring, float :: Prim ( MinSpanTree amp。T ) { int NumVertices = 。 //圖頂點數(shù) float * lowcost = new float[NumVertices]。 int * nearvex = new int[NumVertices]。 for ( int i = 1。 i NumVertices。 i++ ) { lowcost[i] = Edge[0][i]。 //頂點 0到各邊的代價 nearvex[i] = 0。 //及最短帶權(quán)路徑 } nearvex[0] = 1。 //頂點 0加到生成樹頂點集合 MSTEdgeNode e。 //最小生成樹結(jié)點輔助單元 for ( i = 1。 i NumVertices。 i++ ) { //循環(huán) n1次 , 加入 n1條邊 float min = MAXNUM。 int v = 0。 for ( int j = 0。 j NumVertices。 j++ ) if ( nearvex[j] != 1 amp。amp。 lowcost[j] min ) { v = j。 min = lowcost[j]。 } //求生成樹外頂點到生成樹內(nèi)頂點具有最小 //權(quán)值的邊 , v是 當(dāng)前具最小權(quán)值的邊的位置 if ( v ) { //v==0表示再也找不到要求頂點了 = nearvex[v]。 = v。 = lowcost[v]。 (e)。 //選出的邊加入生成樹 nearvex[v] = 1。 //作該邊已加入生成樹標(biāo)記 for ( j = 1。 j NumVertices。 j++ ) if ( nearvex[j] != 1 amp。amp。 // j 不在生成樹中 Edge[v][j] lowcost[j] ) { //需要修改 lowcost[j] = Edge[v][j]。 nearvex[j] = v。 } } } } 分析以上算法，設(shè)連通網(wǎng)絡(luò)有 n 個頂點 ，則該算法的時間復(fù)雜度為 O(n2), 它適用于邊稠密的網(wǎng)絡(luò)。 最短路徑 (Shortest Path) ? 最短路徑問題： 如果從圖中某一頂點 (稱為源點 )到達(dá)另一頂點 (稱為終點 )的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。 ? 問題解法 ? 邊上權(quán)值非負(fù)情形的單源最短路徑問題 — Dijkstra算法 ? 邊上權(quán)值為任意值的單源最短路徑問題 — Bellman和 Ford算法 ?所有頂點之間的最短路徑 — Floyd算法 邊上權(quán)值非負(fù)情形的單源最短路徑問題 ? 問題的提法： 給定一個帶權(quán)有向圖 D與源點 v，求從 v到 D中其它頂點的最短路徑。 限定各邊上的權(quán)值大于或等于 0。 ? 為求得這些最短路徑， Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點 v到其它各頂點的最短路徑全部求出為止。 ? 舉例說明 Dijkstra逐步求解的過程 源點 終點 最 短 路 徑 路徑長度 v 0 v 1 ( v 0 , v 1 ) 10 v 2 — ( v 0 , v 1 , v 2 ) ( v 0 , v 3 , v 2 ) — 60 50 v 3 ( v 0 , v 3 ) 30 v 4 ( v 0 , v 4 ) ( v 0 , v 3 , v 4 ) ( v 0 , v 3 , v 2 , v 4 ) 100 0 60? 引入一個輔助數(shù)組 dist。它的每一個分量 dist[i]表示當(dāng)前找到的從源點 v0到終點 vi 的最短路徑的長度。初始狀態(tài)： ?若從源點 v0到頂點 vi有邊，則 dist[i]為該邊上的權(quán)值； ?若從源點 v0到頂點 vi 沒有邊，則 dist[i]為 +? 。 ? 一般情況下，假設(shè) S 是已求得的最短路徑的終點的集合，則可證明： 下一條最短路徑必然是從 v0 出發(fā)，中間只經(jīng)過 S中的頂點便可到達(dá)的那些頂點 vx (vx ?VS )的路徑中的一條。 ? 每次求得一條最短路徑之后，其終點 vk 加入集合 S，然后 對所有的 vi ?VS，修改其 dist[i]值。 Dijkstra算法可描述如下： ? 初始化： S ← { v0 }。 dist[j] ← Edge[0][j], j = 1, 2, …, n1。 // n為圖中頂點個數(shù) ? 求出最短路徑的長度： dist[k] ← min{ dist[i] }, i ? V S 。 S ← S U { k }。 ? 修改： dist[i] ← min{ dist[i], dist[k] + Edge[k][i] }, 對于每一個 i ? V S 。 ? 判斷： 若 S = V, 則算法結(jié)束，否則轉(zhuǎn) ?。 用于計算最短路徑的圖鄰接矩陣類的定義 const int NumVertices = 6。 //圖中最大頂點個數(shù) class Graph { //圖的類定義 private: float Edge[NumVertices][NumVertices]。 float dist[NumVertices]。 //最短路徑長度數(shù)組 int path[NumVertices]。 //最短路徑數(shù)組 int S[NumVertices]。 //最短路徑頂點集 public: void ShortestPath ( int, int )。 int choose ( int )。 }。 計算從單個頂點到其它各個頂點的最短路徑 void Graph :: ShortestPath ( int n, int v ){ //Graph是一個具有 n 個頂點的帶權(quán)有向圖 , 各邊 //上的權(quán)值由 Edge[i][j]給出。本算法建立起一個 //數(shù)組 : dist[j], 0 ? j n, 是當(dāng)前求到的從頂點 v // //到頂點 j 的最短路徑長度 , 同時用數(shù)組 path[j], // 0 ? j n, 存放求到的最短路徑。 for ( int i = 0。 i n。 i++) { dist[i] = Edge[v][i]。 //dist數(shù)組初始化 S[i] = 0。 if ( i != v amp。amp。 dist[i] MAXNUM) path[i] = v。 else path[i] = 1。 //path數(shù)組初始化 } S[v] = 1。 dist[v] = 0。 //頂點 v加入頂點集合 //選擇當(dāng)前不在集合 S中具有最短路徑的頂點 u for ( i = 0。 i n1。 i++ ) { float min = MAXNUM。 int u = v。 for ( int j = 0。 j n。 j++ ) if ( !S[j] amp。amp。 dist[j] min ) { u = j。 min = dist[j]。 } S[u] = 1。 //將頂點 u加入集合 S for ( int w = 0。 w n。 w++ ) //修改 if ( !S[w] amp。amp。 Edge[u][w] MAXNUM amp。amp。 dist[u] + Edge[u][w] dist[w] ) { dist[w] = dist[u] + Edge[u][w]。 path[w] = u。 } } 算法的時間復(fù)雜度 ： O(n2) Dijkstra算法中各輔助數(shù)組的變化 如何從表中讀取源點 0到終點 v的最短路徑？舉頂點 4為例 path[4] = 2 →path[2] = 3 → path[3] = 0，反過來排列，得到路徑 0, 3, 2, 4，這就是源點 0到終點 4的最短路徑。 選取 頂點 1 頂點 2 頂點 3 頂點 4 終點 S [ 1] d [ 1] p [ 1] S [ 2] d [ 2] p [ 2] S [ 3] d [ 3] p [ 3] S [ 4] d [ 4] p [ 4] 0 0 10 0 0 ? 0 0 30 0 0 100 0 1 1 10 0 0 60 1 0 30 0 0 100 0 3 1 10 0 0 50 3 1 30 0 0 90 3 2 1 10 0 1 50 3 1 30 0 0 60 2 4 1 10 0 1 50 3 1 30 0 1 60 20 4 1 2 3 10 50 10 20 60 30 100 邊上權(quán)值為任意值的單源最短路徑問題 ? 帶權(quán)有向圖 D的某幾條邊或所有邊的長度可能為負(fù)值。利用 Dijkstra算法，不一定能得到正確的結(jié)果。 ? 源點 0到終點 2的最短路徑應(yīng)是 0, 1, 2，其長度為 2，它小于算法中計算出來的 dist[2]的值。 若設(shè)源點 v = 0，使用Dijkstra算法所得結(jié)果 選取 頂 點 0 頂 點 1 頂 點 2 頂點 S [0 ] d [0 ] p [0 ] S [1 ] d [1 ] p [1 ] S [2 ] d [2 ] p [2 ] 0 1 0 1 0 7 0 0