【文章內(nèi)容簡介】 對 G中的每一條邊 ，相應地有一個數(shù) wij，則稱這樣的圖 G為賦權圖， wij稱為邊 上的權。 [ , ]ijvv[ , ]ijvv湖州師范學院商學院 27 2022年 2月 11日 一、圖與樹 第八講 圖與網(wǎng)絡優(yōu)化 最小支撐樹問題 設有一個連通圖 G=(V， E)，每一邊 e= ，有一個非負權： w(e)=wij (wij≥0) [ , ]ijvv 定義 如果 T=(V， E′) 是 G的一個支撐樹，稱 E′中所有邊的權之和為支撐樹 T的權，記為 w(T)。即： [ ] T( T )ijijv ,v???? ? 如果支撐樹 T* 的權 w(T*)是 G的所有支撐樹的權中最小者，則稱 T*是 G的最小支撐樹 (簡稱最小樹 )。即 *T( T ) m in ( T )???湖州師范學院商學院 28 2022年 2月 11日 一、圖與樹 第八講 圖與網(wǎng)絡優(yōu)化 最小支撐樹問題 1. 避圈法： 從圖中任取一點 令 ，圖中其余的點都在 中；從 與 的連線中找出最小邊，這條邊一定在最小支撐樹內(nèi)，不停重復，一直到圖中所有點均包含在 V中為止。 2. 破圈法：任取一個圈，從圈中去掉一條權最大的邊 (如果有兩條或兩條以上的邊都是權最大的邊，則任意去掉其中一條 )。在余下的圖中，重復這個步驟，直至得到一個不含圈的圖為止，這時的圖便是最小樹。 下面介紹兩個求解最小支撐樹的方法。 ,iv Vvi ?V VV湖州師范學院商學院 29 2022年 2月 11日 例： 如圖 S,A,B,C,D,E,T代表村鎮(zhèn) ,村鎮(zhèn)之間的連線上賦予了權值 (可代表距離 ,費用 ,流量等 )現(xiàn)沿圖中連線架設電線 ,使各村鎮(zhèn)全部通電 ,問如何架設使電線總長最短 .(該圖稱為賦權圖或無向網(wǎng)絡 ). SABCDET2 25557734411第八講 圖與網(wǎng)絡優(yōu)化 湖州師范學院商學院 30 2022年 2月 11日 SABCDET2 25557734411最小支撐樹總長 =2+2+1+3+1+5=14 第八講 圖與網(wǎng)絡優(yōu)化 湖州師范學院商學院 31 2022年 2月 11日 SABCDET2 25557734411電線總長 =2+2+1+3+1+5=14 湖州師范學院商學院 32 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 引例 已知如 下圖 所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條單行線所需要的費用?，F(xiàn)在某人要從 v1出發(fā)，通過這個交通網(wǎng)到 v8去，求總費用最小的旅行路線。 湖州師范學院商學院 33 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 引例 結論 1： 由上例可見 ， 從 v1到 v8的旅行路線有很多 ； 結論 2： 不同的路線所需總費用是不同的 ； 結論 3： 用圖的語言來描述，從 v1到 v8的一條旅行路線就是圖中從 v1到 v8的一條路；一條旅行路線的總費用就是相應的從 v1到 v8的路中所有弧旁數(shù)字之和。 湖州師范學院商學院 34 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 一般意義的最短路問題 給定一個賦權有向圖，即給了一個有向圖 D=(V， A)，對每一個弧 a=(vi， vj)，相應地賦予了權數(shù)；又給定 D中的兩個頂點 vs， vt。設 P是 D中從 vs到 vt的一條路，定義路 P的權是 P中所有弧的權之和，記為 w(P)。最短路問題就是要在所有從 vs到 vt的路中，求一條權最小的路，即求一條從 vs到 vt的路 P0，使 ： 0 P( P ) m in ( P )??? 上 式中對 D中所有從 vs到 vt的路 P取最小，稱 P0是從vs到 vt的最短路。路 P0的權稱為從 vs到 vt的距離，記為d(vs， vt)。顯然， d(vs， vt)與 d(vt， vs)不一定相等。 湖州師范學院商學院 35 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 最短路算法 Dijkstra算 法 的基本思想： 從 vs出發(fā)，逐步向外探尋最短路。執(zhí)行過程中，與每個點對應，記錄下一個數(shù)(稱為這個點的標號 )，它或者表示從 vs到該點的最短路的權 (稱為 P標號 )，或者是從 vs到該點的最短路的權的上界 (稱為 T標號 )，方法的每一步是去修改 T標號，并且把某一個具 T標號的點改變?yōu)榫?P標號的點，從而使 D中具 P標號的頂點數(shù)多一個，這樣，至多經(jīng)過 p?1步，就可以求出從 vs到各點的最短路。 湖州師范學院商學院 36 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 Dijkstra算法 P， T分別表示某個點的 P標號、 T標號， 為了在求出從 vs到各點的距離的同時，也求出從 vs到各點的最短路，給每個點 v以一個 λ值。算法終止時，如果 λ (v)=vm，表示在從 vs到 v的最短路上， v的前一個點是 vm； λ (v)=0表示 v=vs。 湖州師范學院商學院 37 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 例題 用 Dijkstra方法求 前例 中從 v1 到各個頂點的最短路 ？ 標 P(v1)=0。其余點標 T(vi)= +∞ ， i＝ 2， 3， … ， 9； T(v2)＝ min｛ +∞ ， 0＋ 6｝＝ 6， λ (v2)=v1； T(v3)＝ min｛ +∞ ， 0＋ 3｝＝ 3， λ (v3)=v1； T(v4)＝ min｛ +∞ ， 0＋ 1｝＝ 1， λ (v4)=v1； 將具有最小 T標號的 v4點的標號改為 P標號： P(v4)＝ 1； T(v6)＝ min｛ +∞ ， 1＋ 10｝＝ 11， λ (v6)=v4； 將具有最小 T標號的 v3點的標號改為 P標號： P(v3)＝ 3； T(v2)＝ min｛ 6 ， 3＋ 2｝＝ 5， λ (v2)=v3； 將具有最小 T標號的 v2點的標號改為 P標號： P(v2)＝ 5； 湖州師范學院商學院 38 2022年 2月 11日 例題 用 Dijkstra方法求 前例 中從 v1 到各個頂點的最短路 ？ T(v5)＝ min｛ +∞ ， 5＋ 1｝＝ 6， λ (v5)=v2； 將具有最小 T標號的 v5點的標號改為 P標號： P(v5)＝ 6； T(v6)＝ min｛ 11 ， 6＋ 4｝＝ 10， λ (v6)=v5； T(v7)＝ min｛ +∞ ， 6＋ 3｝＝ 9， λ (v7)=v5； T(v8)＝ min｛ +∞ ， 6＋ 6｝＝ 12， λ (v8)=v5； 將具有最小 T標號的 v7點的標號改為 P標號： P(v7)＝ 9； T(v8)＝ min｛ 12 ， 9＋ 4｝＝ 12， λ (v8)=v5； 將具有最小 T標號 v6點的標號改為 P標號： P(v6)＝ 11； 將具有最小 T標號 v8點的標號改為 P標號： P(v8)＝ 12； 湖州師范學院商學院 39 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 Dijkstra算法缺陷 Dijkstra算法只適用于所有 wij≥0 的情形，當賦權有向圖中存在負權時，則算法失效。例如在 下圖 所示的賦權有向圖中，如果用 Dijkstra方法，可得出從 v1到 v2的最短路的權是 1，但這顯然是不對的，因為從 v1到 v2的最短路是 (v1， v3， v2)，權是 1。 湖州師范學院商學院 40 2022年 2月 11日 二、最短路問題 第八講 圖與網(wǎng)絡優(yōu)化 練習題 V1 V2 V3 V4 V5 V6 V7 9 8 5 2 8 7 3 7