【正文】 //建立入度為零頂點棧 S if (indegree[k]==0) (k)。 106 有向圖的應(yīng)用 —— 關(guān)健路徑 while (!()) { j=()。 (j)。 count++。 //頂點 j入棧并計數(shù) for (p=ghead[j].firstout。 p。 p=plink) { //對頂點 j的每個后繼頂點入度減 1 k=padjvex。 if (indegree[k]==0) (k)。 //若入度為 0，則入棧 S if (ee[j]+dut(j,k)ee[k]) ee[k]=ee[j]+dut(j,k)。 //對 j的各后繼點 k修改 ee[k] } } if(countn) return false。 //有回路 else return true。 } // TopologicalSort 107 有向圖的應(yīng)用 —— 關(guān)健路徑 void CriticalPath( ) { Stack T。 if (!TopLogicalSort(T)) return。 le[0..n1]=ee[n1]。 while (!( )) for (j=(), p=ghead[j].firstout。 p。 p=plink) { k=padjvex。 if (le[k]dut(j,k)le[j]) le[j]=le[k]dut(j,k)。 } for (j=0。 jn。 j++) for (p=ghead[j].firtout。p。p=plink) { k=padjvex。 tag=(ee[j]==le[k]dut(j,k))?’*’:’ ‘。 coutjkdut(j,k)ee[j]le[k]dut(j,k)tag。 } }//CriticalPath 108 有向圖的應(yīng)用 —— 關(guān)健路徑 ?例 頂點 ee[i] le[i] v0 v1 v2 v3 v4 v5 v6 v7 v8 0 6 4 5 7 7 16 14 18 0 6 6 8 7 10 16 14 18 活動 e[k] l[k] le a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 0 0 0 0 2 2 0 3 3 6 6 0 4 6 2 5 8 3 7 7 0 7 7 0 7 10 3 16 16 0 14 14 0 ????????????????????)}(|,)(m i n {)()1()1()}(|,)(m a x {)(0)0(jSiijdutilejleneenlejPijidutieejeeee????????),()()()()(vudutvleilueeie109 有向圖的應(yīng)用 —— 關(guān)健路徑 算法分析 ?拓撲排序求 ee[i] 和逆拓撲有序求 le[i] 時，所需時間為 O(n+e) ?求各個活動的 e[k] 和 l[k] 時所需時間為 O(e) ?總共花費時間仍然是 O(n+e) 110 最短路徑（ Shortest Path） 111 最短路徑（ Shortest Path） 求從某個源點到其余各點的最短路徑 ?—— Dijkstra 算法 每一對頂點之間的最短路徑 ?—— Floyd 算法 112 最短路徑 —— 求單源最短路徑 單源最短路徑問題 ?如果從圖中某一頂點（稱為源點）到達另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。 問題解法 ? Dijkstra 算法 ?給定一個網(wǎng) G = { V, E,W }與源點 v0，求從 v0 到 G中其它頂點的最短路徑。 ?規(guī)定各邊（或?。┥系臋?quán)值大于或等于 0。 113 最短路徑 —— 求單源最短路徑 Dijkstra 算法思想 ?按路徑長度的遞增次序，逐步產(chǎn)生各條最短路徑。 ?第一條最短路徑長度的求法 ?這條路徑必定只含一條弧 v0, v1 ，并且這條弧的權(quán)值最小。 w1 w2 wk wn1 114 最短路徑 —— 求單源最短路徑 ?第二條最短路徑長度的求法 它只可能有兩種情況 ?直接從源點到某頂點 v2 （只含一條?。? ?從源點經(jīng)過頂點 v1，再到達該頂點 v2（由兩條弧組成） 115 最短路徑 —— 求單源最短路徑 ?其余最短路徑的求法 ?或者是直接從源點到某頂點 vk（只含一條?。? ?或者是從源點經(jīng)過已求得最短路徑的頂點，再到達該頂點 116 最短路徑 —— 求單源最短路徑 ?例 60 20 10 30 50 100 0 3 4 2 1 10 源點 終點 最短路徑 路徑長度 v0 v1 v0, v1 10 v2 v3 v0, v3 30 v4 v0, v4 100 60 v0, v1, v2 v0, v3, v4 v0, v3, v2, v4 v0, v3, v2 50 90 60 117 最短路徑 —— 求單源最短路徑 Dijkstra 算法實現(xiàn) ?引入一個輔助數(shù)組 dist ?它的每一個分量 dist[i] 表示當前找到的從源點 v0 到終點 vi 的最短路徑的長度 ?初始狀態(tài) ? 若從源點 v0 到頂點 vi 有邊，則 dist[i]為該邊上的權(quán)值 ? 若從源點 v0 到頂點 vi 沒有邊，則 dist[i]為 +? ?每次求得一條最短路徑之后，其終點 vk 加入集合 S，然后對所有的 vi?VS，修改其 dist[i] 值 118 最短路徑 —— 求單源最短路徑 Dijkstra 算法描述如下 ?初始化 ?置 S＝ { v0 }。 ?dist[i] ← cost[0][i], i= 1, …,n 1。 // n為圖中頂點個數(shù) ? (1) 求出最短路徑的長度 ?dist[k] ← min{ dist[i] }, i ?VS 。 ?S ← S ∨ { k }。 ? (2) 修改 ?對于每一個 i?VS， dist[i] ← min{ dist[i], dist[k] + cost[k][i] } ； ? (3) 重復(fù) (1) 和 (2) n1次。 119 最短路徑 —— 求單源最短路徑 計算最短路徑的圖鄰接矩陣類的定義 const int Vexnum =20； //圖中最大頂點個數(shù) define max ∞ //定義無窮大 class Graph { //圖的類定義 float cost[Vernum][Vernum]； float dist [Vexnum]； //最短路徑長度數(shù)組 int path[Vexnum]； //最短路徑頂點序列數(shù)組 int find[Vexnum]； //最短路徑頂點集 public: void ShortestPath (int， int)； int choose ( int )； }； // Graph 120 最短路徑 —— 求單源最短路徑 Dijkstra 描述的單源最短路徑算法 void ShortestPath_DIJ (int v0。 int path。 int *dist) { for (v=0。 vVexnum。 v++) { find[v]=0。 path[v]=0。 dist[v]=cost[v0][v]。 } find[v0]=1。 for (i=1。 i Vexnum。 i++){ k=mininum(dist)。 find[k]=1。 for (w=1。 wVexnum。 w++) if (!find[w] amp。amp。 cost[k][w]max) if (dist[w]dist[k]+cost[k][w]) { dist[w]=dist[k]+cost[k][w]。 path[w]=k。 } } }// ShortestPath_DIJ 算法的時間復(fù)雜度 ： O(n2) 121 最短路徑 —— 求單源最短路徑 Dijkstra算法中各輔助數(shù)組的變化 選 取 頂點 1 頂點 2 頂點 3 頂點 4 終 點 f [1] d [1] p [1] f [2] d [2] p [2] f [3] d [3] p [3] f [4] d [4] p [4] 0 0 10 0 0 ? 1 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 2 如何從表中讀取源點 0到終點 v的最短路徑？舉頂點 4為例 path[4]=2 →path[2]=3 → path[3] = 0 ， 反過來排列，得到路徑 0324，這就是源點 0到終點 4的最短路徑。 122 最短路徑 —— 求單源最短路徑 思考 ?當網(wǎng)中有負的權(quán)值時， Dijkstra 算法是否還能正確執(zhí)行？ 1 5 5 7 2 0 123 最短路徑 —— 所有頂點之間的最短路徑 問題的提法 ?已知一個各邊權(quán)值均大于 0的帶權(quán)有向圖，對每一對頂點 vi ? vj，要求求出 vi 與 vj 之間的最短路徑和最短路徑長度 解決辦法 ?方法一：每次以一個頂點為源點，重復(fù)執(zhí)行Dijkstra 算法 n 次 —— T(n)=O(n179。) ?方法二： Floyd算法 —— T(n)=O(n179。) 形式簡單 124 最短路徑 —— 所有頂點之間的最短路徑 Floyd 算法思想 ?逐個頂點試探法 ?求最短路徑步驟 ?初始時設(shè)圖以相鄰矩陣存儲； ?逐步試著在原路徑中增加中間頂點，若加入中間頂點后路徑變短，則修改之；否則，維持原值。 ?所有頂點試探完畢，算法結(jié)束。 125 最短路徑 —— 所有頂點之間的最短路徑 ?例 0 2 1 2 6 4 3 11 0 4 11 6 0 2 3 ? 0 初始： 路徑： 0 0 0 1 0 1 2 1 0 0 4 6 6 0 2 3 7 0 加入 1： 0 0 1 路徑： 1 0 1 2 0 0 0 4 6 5 0 2 3 7 0 加入