【正文】 5 4 3 ?路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長(zhǎng)度，試用 Dijkstra 算法求s到 t的最短路線 示例 () s a b c d t 初始值 T( ) 第 1次 P( )+ lij T( ) 第 2次 P( )+ lij T( ) 第 3次 P( )+ lij T( ) 第 4次 P( )+ lij T( ) 第 5次 P( )+ lij T( ) 0 ∞ ∞ ∞ ∞ ∞ 0+5 0+8 0+∞ 0+∞ 0+∞ 5 8 ∞ ∞ ∞ 5+∞ 5+3 5+9 5+∞ 8 8 14 ∞ 8+∞ 8+4 8+∞ 8 12 ∞ 8+3 8+9 11 17 11+5 16 1 2 3 4 5 示例 () s a b c d t 5 8 3 9 1 4 9 5 4 3 海斯算法 (1) ?該算法有兩個(gè)依據(jù) ?從 v1 到 vn 的最短路線也是從 vn 到 v1 的最短路線 ?對(duì)于無(wú)向圖必定成立 ?對(duì)于有向圖而言， vn 到 v1 的最短路線是指將圖中弧的方向反過(guò)來(lái)，但權(quán)值不變時(shí)的最短路線 ?若從 vi 到 vj 的最短路線經(jīng)過(guò) vk ，則 vi 到 vk 、 vk 到vj 的都是相應(yīng)的最優(yōu)路線 ?第一條依據(jù)保證了從 vi 到 vj 的最短路線也是從 vj 到 vi 的最短路線 ?則根據(jù)動(dòng)態(tài)規(guī)劃最優(yōu)性原理， vk 到 vj 和 vk 到 vi都是相應(yīng)的最優(yōu)路線，由此得到上面的結(jié)論 海斯算法 (2) ?算法步驟 ?已知網(wǎng)絡(luò)的距離矩陣 L=(lij)， lij表示 vi到 vj的弧上的距離權(quán)值 ?令 dij(0)= lij， i=1～ n， j=1～ n ?dij(t)表示從 vi到 vj的 2t步距離 ?當(dāng) dij(m1)已知時(shí)，令 dij(m)=min{dik(m1)+dkj(m1)| k=1～ n} ?當(dāng)對(duì)所有的 i, j有 dij(m)=dij(m1)時(shí)， dij(m)是 vi到 vj的最短距離。無(wú)向圖的邊 eij=(vi, vj)=(vj, vi)= eji ?當(dāng)圖中的邊都有方向時(shí)，稱為 有向圖 。尋找增廣鏈方法如下 ?將 vs 標(biāo)記上 (, ∞)， S1={vs}， S2=VS1 ?若存在以 S1中點(diǎn)為起點(diǎn)、以 S2中點(diǎn)為終點(diǎn)的非飽和弧(vi , vj )，則為 vj 標(biāo)記上 (vi+, zj )， zj=min{zi , bijxij}，S1=S1+{vj}， S2=S2{vj} ?若存在以 S2中點(diǎn)為起點(diǎn)、以 S1中點(diǎn)為終點(diǎn)的非零流弧(vj , vi )，則為 vj 標(biāo)記上 (vi, zj )， zj=min{zi , xji}，S1=S1+{vj}， S2=S2{vj} ?若 S1中已包含 vt ，則已找到一條增廣鏈，否則轉(zhuǎn)向第二步 最大流問(wèn)題 (6) ?調(diào)整流量，方法如下 ?設(shè) vt 上的標(biāo)記為 (vk+, zt )，則整個(gè)增廣鏈上最大的調(diào)整量為 z=zt ?由 vt 上 的標(biāo)記可以得到增廣鏈上的前一個(gè)頂點(diǎn) vk ，依次向前可以找到整個(gè)增廣鏈 ?在增廣鏈上，正向弧流量增加 z，逆向弧流量減少 z ?返回第二步繼續(xù)尋找下一個(gè)增廣鏈 示例 () (9) (8) (3) (7) (4) (4) (2) (6) (11) 7 11 10 6 9 15 5 4 3 vs vt v2 v3 v4 v5 (, ∞) (vs+, 7) (v2, 3) (v3+, 1) (v3+, 3) (v5+, 3) ?用標(biāo)號(hào)法求出從 vs 到 vt 的最大流 示例 () ?調(diào)整流量，得 7 11 10 6 9 15 5 4 3 vs vt v2 v3 v4 v5 (11) (0) (9) (7) (4) (4) (5) (9) (11) (, ∞) (vs+, 4) ?找不到增廣鏈，則當(dāng)前流量 20為最優(yōu) 最小費(fèi)用 最大流問(wèn)題 (1) ?一般情況下，最大流量是唯一的，而相應(yīng)的每條弧上的流量分布卻是不唯一的 ?如果已知流過(guò)弧 (vi , vj )的單位流量要發(fā)生 cij 的費(fèi)用，要求使得總費(fèi)用為最小的最大流流量分配方案，這種問(wèn)題稱為最小費(fèi)用 最大流問(wèn)題 ?可以使用對(duì)偶法解決這個(gè)問(wèn)題 最小費(fèi)用 最大流問(wèn)題 (2) ?對(duì)偶法原理 ?對(duì)原圖求出從 vs 到 vt 的所有初等路 ?將這些初等路按照單位流量費(fèi)用之和從小到大排序，編號(hào) 1, 2, 3, … , m ?使第 1號(hào)初等路上的流量為最大 ?在余下的允許流量中，使第 2號(hào)初等路上的流量為最大 ?在余下的允許流量中，使第 3號(hào)初等路上的流量為最大 ?… ?在余下的允許流量中，使第 m號(hào)初等路上的流量為最大 ?此時(shí)，圖中的流量分布即為最小費(fèi)用 最大流 ?在實(shí)際使用時(shí)，要對(duì)原圖求出從 vs 到 vt 的所有初等路有一定的難度，容易遺漏 最小費(fèi)用 最大流問(wèn)題 (3) ?因此，對(duì)偶法在實(shí)際操作時(shí) ?求出最大流量，以 0流為初始可行流 ?對(duì)原圖求出從 vs 到 vt 的單位流量費(fèi)用之和為最小的初等路 ?調(diào)整使得該初等路上的流量為最大，若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費(fèi)用 最大流，否則進(jìn)入下一步 ?對(duì)當(dāng)前可行流生成擴(kuò)展費(fèi)用圖。前例中， A, B是邊 e1 的端點(diǎn)，e1 是 A, B的關(guān)聯(lián)邊 ?若頂點(diǎn) u和 v與同一條邊相關(guān)聯(lián)，則稱 u和 v為 相鄰點(diǎn) ?若兩條邊 ei 和 ej 有同一個(gè)端點(diǎn)，則稱 ei 和 ej 為 相鄰邊 圖的基本概念 (4) ?若一條邊的兩個(gè)端點(diǎn)是同一個(gè)頂點(diǎn)，則稱該邊為 環(huán) ?若兩個(gè)端點(diǎn)之間有多于一條邊，則稱為 重邊 (書上稱為多重邊 )，前例中， A, C之間和 B, C之間都有兩條邊 ?無(wú)環(huán)也無(wú)重邊的圖稱為 簡(jiǎn)單圖 ?與頂點(diǎn) v相關(guān)聯(lián)的邊的數(shù)目，稱為該頂點(diǎn)的“ 度 ” (書上稱為次 )，記為 d(v) ?度數(shù)為奇數(shù)的頂點(diǎn)稱為 奇點(diǎn) ，度數(shù)為偶數(shù)的頂點(diǎn)稱為 偶點(diǎn) ?在有向圖中，由頂點(diǎn)指向外的弧的數(shù)目稱為 正度 ，記為 d+，指向該頂點(diǎn)的弧的數(shù)目稱為 負(fù)度 ，記為 d– ?度數(shù)為 0的點(diǎn)稱為 孤立點(diǎn) ，度數(shù)為 1的點(diǎn)稱為 懸掛點(diǎn) 圖的基本概念 (5) ?與懸掛點(diǎn)連接的邊稱為 懸掛邊 ?若圖中所有的點(diǎn)都是孤立點(diǎn)，則稱為空?qǐng)D ?