【正文】 ；④若＝，則停止，已選出的諸邊即給出最小樹；否則返②．例65　試求圖68所示網(wǎng)絡(luò)的最小樹，各邊旁邊的數(shù)字為各邊的權(quán)．圖68解　由題意可知這是一個最小樹問題．先按原圖畫出7個點(diǎn)，令＝{1}，＝{2，3，4，5，6，7}．由于聯(lián)結(jié)與的邊共有三條，其中最短邊為(1，2)故用線把點(diǎn)1和2連結(jié)起來，令＝{1，2}，＝{3，4，5，6，7}，如圖68(a)所示，重復(fù)上述步驟，直到7個點(diǎn)全都連通為止．具體求解過程如圖68（a）到圖68（f）所示，其中圖68（f）)即給出本例的最小樹，()＝13．圖68（a）（b）圖68（c）—（f）(2)破圈法用破圈法求最小樹時，先從圖中任取一圈，去掉該圈的一條最大邊，然后重復(fù)這一步驟，直到無圈為止．例66 　圖69所示的一賦權(quán)連通圖是某一具有9個居民點(diǎn)的交通網(wǎng)絡(luò)圖，其中邊權(quán)表示該段道路的長，現(xiàn)欲沿小區(qū)道路架設(shè)一聯(lián)絡(luò)各個居民點(diǎn)的閉路電視系統(tǒng)，求可使閉路電視系統(tǒng)所架線路總長最短的方案．圖69解 　這是一個求網(wǎng)絡(luò)最小樹的問題．可利用破圈法求解．過程如圖69（a—i）所示．圖69（a——i）圖69（i）所示的是網(wǎng)絡(luò)最小樹．按圖安排閉路電視系統(tǒng)可使所架線路總長最短，()＝19．第三節(jié) 最短路徑問題在生產(chǎn)實(shí)踐，運(yùn)輸管理和工程建設(shè)的很多活動中，諸如各種工藝路線的安排、廠區(qū)及貨場的布局、管道線網(wǎng)的鋪設(shè)及設(shè)備的更新等等問題，都與尋找一個“圖的最短路徑”問題(shortestpath problem )密切相關(guān)，它是網(wǎng)絡(luò)規(guī)劃中的一個最基本的問題．一、基本概念給定一個賦權(quán)有向圖＝(，)，對每一條?。?，)，相應(yīng)地有權(quán)（）＝，又有兩點(diǎn)、∈V，設(shè)是中從到的一條路，路的權(quán)是中所有弧的權(quán)之和，記為()．最短路問題就是求從到的路中一條權(quán)最小的路：()＝()二、最短路問題的算法1．Dijkstra算法(Dijkstra algorithm)該算法是由Dijkstra于1959年提出來，用于求解指定兩點(diǎn)之間的最短路，或從指定點(diǎn)到其余各點(diǎn)的最短路，目前被認(rèn)為是求解最短路問題的最好方法．算法的基本思路基于以下原理.定理62　若是從到的最短路，是中的一個點(diǎn)，那么從沿到的路必定是從到的最短路．引理　若是從到的最短路，是中的一個點(diǎn)，則從到的最短路必定包含于之內(nèi)．根據(jù)定理62及引理，我們可以從s出發(fā)試探所有可能到達(dá)t的下一個結(jié)點(diǎn)i，取距離最短的一個?。ǎ?，則必然包含于從到的最短路中；從開始對沒有試探過的結(jié)點(diǎn)進(jìn)行進(jìn)一步的試探、推進(jìn)，直至，最終可以找出從到的最短路．Dijstra算法采用（雙標(biāo)號法）T標(biāo)號與P標(biāo)號，來實(shí)現(xiàn)這一試探、推進(jìn)過程．T標(biāo)號為試探性標(biāo)號；P為永久性標(biāo)號．給點(diǎn)一個P標(biāo)號時，表示從到點(diǎn)的最短路權(quán)，一旦點(diǎn)得到P標(biāo)號則意味著從到點(diǎn)的最短距離已經(jīng)確定，標(biāo)號不再改變．給點(diǎn)一個T標(biāo)號時，表示從到點(diǎn)的估計最短路權(quán)的上界，這是一種臨時標(biāo)號．凡沒有得到P標(biāo)號的點(diǎn)都有T標(biāo)號．算法每一步都把某一點(diǎn)的T標(biāo)號改為P標(biāo)號，當(dāng)終點(diǎn)得到P標(biāo)號時，全部計算結(jié)束．Dijstra算法基本步驟：(1)給以P標(biāo)號，P()＝0，其余各點(diǎn)均給T號，T()＝＋∞．(2)若點(diǎn)為剛得到P標(biāo)號的點(diǎn)，考慮，(，)∈A且為T標(biāo)號．對的T標(biāo)號進(jìn)行如下的更改：T()＝min[T()，P()＋] (61)(3)比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號，即：P()＝min[ T() ] (62)當(dāng)存在兩個以上最小者時，可同時改為P標(biāo)號．(4)若全部點(diǎn)均為P標(biāo)號，則停止計算．否則用代替并轉(zhuǎn)至步驟（2）．例67　用Dijkstra算法求圖610中從到的最短距離，以及相應(yīng)的路線．圖610解?。?）首先給以P標(biāo)號，P（ ）＝ 0，給其余所有點(diǎn)T標(biāo)號，T（i）＝＋∞（i = 2，3，… 7）．（2）考察，由于（，），（，），（，）∈A，且、是T標(biāo)號，所以修改T標(biāo)號為：T（）＝min [ T（），P（）＋ ]＝min [∞，0＋2]＝2T（）＝min [ T（），P（）＋]＝min [∞，0＋5]＝5T（）＝min [ T（），P（）＋]＝min [∞，0＋3]＝3在所有T標(biāo)號中，T()＝2最小，于是令P()＝2．將結(jié)果記在圖610（a）上：P標(biāo)號以（）形式標(biāo)在結(jié)點(diǎn)旁邊，T標(biāo)號以不帶（）的數(shù)字標(biāo)在結(jié)點(diǎn)旁邊，圖中沒有標(biāo)號的結(jié)點(diǎn)均代表T（）＝＋∞(3)考察．因為（，），（，）∈A，且、是T標(biāo)號，故、新的T標(biāo)號為：T（）＝min [ T（），P（）＋]＝min [∞，2＋2]＝4T（）＝min [ T（），P（）＋]＝min [∞，2＋7]＝9在所有T標(biāo)號中，T()＝3最小，故令P()＝3．圖上標(biāo)號如圖610（b）．(4)考察，因（，）∈A，T（）＝min [ T（），P（）＋]＝min [∞，3＋5]＝8在所有T標(biāo)號中，T()＝4最小，令P()＝4．圖上標(biāo)號如圖610（c）．(5)考察，（，），（，）∈A，T（）＝min [ T（），P（）＋]＝min [∞，4＋3]＝7T（）＝min [ T（），P（）＋]＝min [∞，4＋5]＝9在所有T標(biāo)號中，T()＝7最小，令P()＝7．圖上標(biāo)號如圖610（d）．(6)考察，（，），（，）∈A，T（）＝min [ T（），P（）＋]＝min [∞，7＋1]＝8T（）＝min [ T（），P（）＋]＝min [∞，7＋7]＝14在所有T標(biāo)號中，T()＝8最小，故令P()＝8．圖上標(biāo)號如圖610（e）．(7)考察，（，）∈A，T（）＝min [ T（），P（）＋ ]＝min [14，8＋5]＝13令P()＝13，圖上標(biāo)號如圖610（f）．所有點(diǎn)都標(biāo)上P標(biāo)號，計算結(jié)束．從到的最短路徑，可從開始根據(jù)永久性標(biāo)號數(shù)值回溯得到．最短路徑是：→→→→→→，路長13．同時得到到其余各點(diǎn)的最短路，即各點(diǎn)的永久性標(biāo)號P（i）．Dijkstra算法只適用于所有0的情形，當(dāng)賦權(quán)有向圖中存在負(fù)權(quán)時，則算法失效．圖610（a）（b）（c）（d）（e）（f）2．逐次逼近算法為方便起見，不妨設(shè)從任一點(diǎn)到任一點(diǎn)都有一條弧，如果在中，不存在弧(，)，則添加虛設(shè)弧(，)，令＝＋∞．從起點(diǎn)到任意點(diǎn)的最短路可以視為一個兩階段過程，如圖611所示：圖611(1)從出發(fā)，沿著一條路走－1步到某點(diǎn)，其最短距離表示為(，)(2)再從沿(，)到，其最短距離就是弧(，)上的權(quán)． 所以，從到的最短距離必滿足如下遞推公式：(，)＝（＝1，2，…，n） 　 （63）(，)＝{(，)＋} 　 （64）式（63）是任意兩點(diǎn)間的一步距離，由前面假設(shè)可知其存在，這可以作為初始條件．式（64）是任意兩點(diǎn)間的k步距離，這是一個遞推公式．利用初始條件和遞推公式通過逐步迭代就可以確定網(wǎng)絡(luò)中任意點(diǎn)之間經(jīng)步到達(dá)的最短距離并得到與之相應(yīng)的路線．下面以實(shí)例來說明迭代過程．例68　用逐次逼近算法求例66圖610中從到各點(diǎn)的最短距離．解　根據(jù)初始條件可知(，)＝0　　　　(，)＝2　　　　(，)＝5(，)＝3　　　(，)＝＋∞　　　(，)＝＋∞(，)＝＋∞；初始條件僅僅表達(dá)了從出發(fā)到的一步到達(dá)的距離，在有向簡單網(wǎng)絡(luò)中即為從到各點(diǎn)的最短距離．到各點(diǎn)的步距離由公式（64）遞推得出．為方便、直觀可列表計算如表63：表63　到各點(diǎn)的步距離jvii(，)＝{(，)＋}k=1k=2k=3k=4k=5k=60253000000027222222013554444405333333017877770598880141313⑴⑵⑶⑷⑸⑹⑺⑻⑼⑽⑾⑿⒀表的左半部是一個nn的關(guān)于結(jié)點(diǎn)兩兩之間的一步距離矩陣，由式（63）可知，到的一步距離就是弧（，）上的權(quán)．一步距離矩陣中0元素表示原地踏一步，沒有填寫數(shù)字的空格是∞的省略．表右半部是公式（64）的計算結(jié)果．k=h時，第h+n列數(shù)據(jù)表示到各點(diǎn)的h步最短距離．譬如k=3為第 ⑽ 列，表示經(jīng)3步到達(dá)各點(diǎn)的最短距離．計算過程如下：（1）當(dāng)k=1時(，)＝這是初始條件，表示從出發(fā)到各點(diǎn)的一步距離，將其依次列于第 ⑻列．由此推算(，)．（2）k=2時(，)＝{(，)＋}即用表中第 ⑻ 列數(shù)字與表左邊一步距離矩陣中第列相應(yīng)數(shù)字相加取小，得到從出發(fā)到各點(diǎn)的二步距離：（0 ＋ 0）（∞ ＋ 2）（∞ ＋ 5）(，)＝min （∞ ＋ 3） ＝0（∞ ＋ ∞）（∞ ＋ ∞）（∞ ＋ ∞）（2 ＋ 0）（0 ＋ 2）（∞ ＋ 5）(，)＝min （∞ ＋ 3） ＝2（∞ ＋ ∞）（∞ ＋ ∞）（∞ ＋ ∞）同理： (，)＝4　　　(，)＝3　　(，)＝8　(，)＝∞　　　(，)＝∞得：024(，)＝ 38∞∞將其填入表63第 ⑼ 列（3）重復(fù)上述步驟得到(，)、(，)、(，)、(，)；分別填入表63第 ⑽、⑾、⑿、⒀ 列（4）當(dāng)k=6時，發(fā)現(xiàn)(，)＝(，)，說明對于整個有向圖D而言，繼續(xù)增加步數(shù)已不起作用，即已得到從到各點(diǎn)的最短距離，即表中 ⑿ 或 ⒀ 列數(shù)字：＝0；原地一步＝2；一步到達(dá)＝4；二步到達(dá)＝3；一步到達(dá)＝7；三步到達(dá) ＝8；四步到達(dá) ＝13；五步到達(dá)從表63中還可以用回溯方法推知到各點(diǎn)最短距離的相應(yīng)最短路線，以到為例：由第⑿列行可知，到經(jīng)5步到達(dá)，最短距離13．回溯13的來源：（，）=13因（，）＝[ ⑿ 列行 ]＋[ ⑺ 列行 ]＝（，）＋＝8＋5＝13故記下（，）．因（，）＝ [ ⑽ 列行 ]＋[ ⑹ 列行 ]＝（，）＋＝7＋1＝8故記下（，）.因（，）＝ [ ⑼ 列行 ]＋[ ⑸ 列行 ]＝（，）＋＝4＋3＝7故記下（，）．因（，）＝ [ ⑻ 列行 ]＋[ ⑶ 列行 ]＝（，）＋＝2＋2＝4故記下（，）．因（，）＝＝0＋2＝2，記下（，）． 得到最短路徑：．當(dāng)網(wǎng)絡(luò)圖存在負(fù)權(quán)時，Dijkstra算法失效，必須采取逐次逼近算法來求解最短路．例69　試求網(wǎng)絡(luò)圖612中到各點(diǎn)的距離．圖612解　初始條件：(，)＝0　　　(，)＝1(，)＝＋∞　　(，)＝2(，)＝＋∞　　(，)＝＋∞計算結(jié)果如表64所示：表64　到各點(diǎn)的距離vjvi(，)=1=2=3=4=501200000034111112051411140322222330111120求得到各點(diǎn)的最短距離：(，)＝0；原地一步(，)＝1；四步到達(dá)(，)＝1；三步到達(dá)(，)＝2；一步到達(dá)(，)＝1；二步到達(dá)(，)＝∞；無法到達(dá)逐次逼近算法，因其類似于矩陣乘法，在有些書籍表述為距離矩陣摹乘法，它們的實(shí)質(zhì)一致．這種算法在n個結(jié)點(diǎn)的網(wǎng)絡(luò)圖中，至多經(jīng)過n1次迭代必然收斂．但前提條件是圖中不含有總權(quán)小于0的回路，否則最短路權(quán)沒有下界．第四節(jié)　最大流問題網(wǎng)絡(luò)流(network flow)是一類普遍存在的現(xiàn)象．例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等．在20世紀(jì)50年代Ford和Fulkerson建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分．網(wǎng)絡(luò)最大流問題(maxflow problem)尤為重要．這是因為絕大部分網(wǎng)絡(luò)流研究，旨在尋求在一定條件下使網(wǎng)絡(luò)流達(dá)到最大的方法．如圖613是輸油管道網(wǎng)，為起點(diǎn)，是終點(diǎn)，為中轉(zhuǎn)站，弧上的數(shù)表示該管道的最大輸油能力，問應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大?圖613一、基本概念和基本定理1．網(wǎng)絡(luò)流．所謂網(wǎng)絡(luò)流，是指在一定的條件下流過一個網(wǎng)絡(luò)的某種流在各邊上的流量的集合．表達(dá)為＝{(，)| (，)∈}所謂一定條件，一般是指如下規(guī)定：(1)網(wǎng)絡(luò)有一個始點(diǎn)和一個終點(diǎn)，始點(diǎn)是流的源，終點(diǎn)是流的匯；(2)流具有一定的方向，流經(jīng)各弧的流，其方向就是相應(yīng)弧的方向；(3)對每一弧(，)∈，都賦予一個容量(，)0，簡記為，表示容許通過該弧的最大流量．并稱(，)為通過弧(，)流，簡記為．凡做出上述規(guī)定的網(wǎng)絡(luò)都可稱為容量網(wǎng)絡(luò)，記為＝（，）圖613所示的就是一個容量網(wǎng)絡(luò)．圖中每條弧上的數(shù)對為(，)，標(biāo)明了弧的容量以及流經(jīng)該弧的流量．2．可行流和最大流可行流是指滿足容量限制條件和平衡條件的流．(1)容量限制條件：對于任一弧(，)，都有0，即任何弧上的流量不能超過弧的容量．(2)平衡條件：對于任一