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