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