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