【文章內(nèi)容簡介】 )2(1最小連接問題 作為最小樹的應(yīng)用問題之一是所謂的連接問題：欲建造一個連接若干城鎮(zhèn) （ 礦區(qū)或工業(yè)區(qū) ） 的鐵路網(wǎng) ， 給定城鎮(zhèn) i和 j之間直通線路的造價(jià)為 cij， 試設(shè)計(jì)一個總造價(jià)最小的鐵路運(yùn)輸圖 。 ?把每個城鎮(zhèn)看作是具有權(quán) cij的賦權(quán)圖 G的一個頂點(diǎn)。顯然連接問題可以表述成：在賦權(quán)圖 G中，求出具有最小權(quán)的支撐樹。 167。 最短路問題 ?Dijkstra算法 ?求任意兩點(diǎn)的最短路算法 Floyd算法 ?求帶負(fù)權(quán)網(wǎng)絡(luò)圖的最短路的算法 ?用線性規(guī)劃求最短路 賦權(quán)圖 ?給定賦權(quán)圖的一個子圖 H，定義 H的權(quán)為 H的所有邊權(quán)的總和。 ?對圖 G的每條邊 e，賦予一實(shí)數(shù) ω(e)，稱為邊 e的權(quán)，可得一 賦權(quán)圖。 S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 ?賦權(quán)圖中一條路的權(quán)稱為路長。 ?在一個賦權(quán)圖 G上，給定兩個頂點(diǎn) u和 v，所謂 u和 v最短 路是指所有連接頂點(diǎn) u和 v 的路中路長最短的路； ?u和 v最短路的路長也稱為 u和 v的距離。 S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 ?如何求從 u到 v的 最短路的長？ ? Dijkstra算法的基本思想： ),(),(),( 00 vuwuudvud ??},),(),(m i n {),( 00 SvSuvuwuudSud ????(1) u vu0 u1 SP PSVSSu ??? ,0設(shè) S是 V的真子集， vuuP ?0? S如果 是從 u0 到 的最短路， Su ? ),( 0 uu ),( 0 uu則 ，并且 P的 段是最短的 路，所以 算法標(biāo)號 ? 令 dij表示連接頂點(diǎn) vi與頂點(diǎn) vj邊上的權(quán)，即 ??????? )(,)(,GEvvGEvvwdjijiijij},),(),(m i n {),( 00 SvSuvuwuudSud ????(1) 公式（ 1）是 Dijkstra算法的基礎(chǔ)。 定義結(jié)點(diǎn) vj 的標(biāo)號為 0],[],[ ??? ijijij didlil始點(diǎn)的標(biāo)號為 [0,], 表明這個點(diǎn)前面沒有點(diǎn)。 結(jié)點(diǎn) vj 的標(biāo)號分為兩種： 臨時性標(biāo)號和永久性標(biāo)號 。如果找到一條更短的路，臨時性標(biāo)號即被修改，如果找不到一條更短的路，臨時性標(biāo)號即被改為永久性標(biāo)號。 ? Step0 令 始點(diǎn)的標(biāo)號為 [0, ]. 令 i=1 ?Step i (a) 對于由結(jié)點(diǎn) i可達(dá)的還沒有永久性標(biāo)號的結(jié)點(diǎn) j，計(jì)算其 臨時性標(biāo)號 [li+dij, i]（ dij0） . 如果 j 已經(jīng)通過另一個結(jié)點(diǎn) k標(biāo)號為 [lj, k] 且 li+dijlj, 則用 [li+dij, i]取代 [lj, k] 。 (b) 如果所有的結(jié)點(diǎn)都是永久性標(biāo)號，停止。否則選擇最小的臨時性標(biāo)號 [lr, s] 。 令 i=r ， 返回 Step i. 計(jì)算實(shí)例 求連接 S、 T的最短路 S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s 9， A 4， A ， s S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s 9， A 4， A ， s ，8， C S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s 9， A 4， A ， s ，8， C 7， B ，S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s 9， A 4， A ， s ，8， C 7， B， 8， E14， E ，lST = 13。ST最短路為 SABEDT S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s 9， A 4， A ， s ，8， C 7， B， 8， E14， E ，13， D實(shí)例評述 ? Dijkstra算法不僅找到了所求最短路，而且找到了從 S點(diǎn)到其他所有頂點(diǎn)的最短路；這些最短路構(gòu)成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。 S D B T C E A 7 1 2 2 4 4 7 3 1 5 5 5 0 5， s 4， s 2， s ， s 9， A 4， A ， s ，8， C 7， B， 8， E14， E ，13， D注 : Dijkstra算法只適用于所有 wij≥0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時，算法失效。如 v1 v2 v3 1 2 3 用 Dijkstra算法可以得出從 v1到 v2的最短路的權(quán)是 1，但實(shí)際上從 v1到 v2的最短路是（ v1， v3 ， v2），權(quán)是 1。 下面介紹具有負(fù)權(quán)賦權(quán)有向圖 D的最短路的算法。 不妨假設(shè)從任一點(diǎn) vi到任一點(diǎn) vj都有一條?。ㄈ绻?D中，（ vi， vj ） A，則添加?。? vi， vj ）令 wij=+∞ ）。 ?顯然，從 vs到任一點(diǎn) vj的最短路總是從 vs出發(fā)到某個點(diǎn) vi，再沿（ vi， vj）到 vj的，由前面的結(jié)論可知，從 vs到 vi的這條路必定是從 vs到 vi的最短路，所以 d（ vs， vj）必滿足如下方程： ? ?ijisijs wvvdvvd ?? ),(m i n),(? ?ijisjs wvvdivvd ?? ),(m i n),(可用如下遞推公式：為了求得這個方程的解 ),(,),(),( 21 nsss vvdvvdvvd ?），，（令 ）（ njwvvd sjjs ?21),(1 ??? ? ),2,1(),(m i n),(321 njwvvdvvdtijistijst ??????? ）（）（，，對有，，步時，對所有第若進(jìn)行到某一步，例如 njk ?21?),(),( 1 jskjsk vvdvvd ）（）（ ??到各點(diǎn)的最短路的權(quán)。）既為，，（則 ）（ sjsk vnjvvd ?21),( ?1v2v3v4v5v6v7v8v6 1 3 2 8 3 5 2 1 1 1 1 2 1 7 3 5 例：求 v1到各點(diǎn)的最短路。 wij v1 v2 v3 v4 v5 v6 v7 v8 t=1 t=2 t=3 t=4 v1 0 1 2 3 0 0 0 0 v2 6 0 2 1 5 5 5 v3 3 0 5 1 2 2 2 2 v4 0 2 3 7 7 7 v5 1 0 1 3 3 v6 1 0 1 7 1 1 1 v7 1 3 0 5 5 5 v8 5 0 6 6 ),( 1 jt vvd ）（? ? ),2,1(),(),(321m i n njwvvdvvdtijistijst ??????? ）（）（，，對 ? 例一個連接 11個城鎮(zhèn)的交通圖以及城市 u與 v之間的一條最短路。（粗線表示） 222221111334 456677899u v 222221111334 456677899u v 求任意兩點(diǎn)的最短路算法 Floyd算法 這種算法用一個 n階方陣來表示一個 n結(jié)點(diǎn)網(wǎng)絡(luò) .矩陣中的 (i, j)元 dij 表示從 i 到 j邊上的權(quán) , 即 ??????? )(,)(,GEvvGEvvwdjijiijiji j k ikd kjdijdFloyd’s algorithm 的基本思想：給定結(jié)點(diǎn) i, j 和 k ，若有如下三角形，且 ，則從 i經(jīng)過 k到 j 比直接到 j所經(jīng)過路線短。 ijkjik ddd ??此時用 i→ k→ j 代替 i→ j最好 .三角形運(yùn)算 ?????????????????????????????njnnjnjjnjnjdddndddjddddddnjD21212221111202121?????????????????????????????jnnjnjnjnjS212112212101 2 4 5 3 3 5 4 6 15 10 1 2 3 4 5 1 2 3 4 5 － 3 10 ∞ ∞ 3 － ∞ 5 ∞