第六章 圖與網(wǎng)絡分析

《第六章 圖與網(wǎng)絡分析》由會員分享，可在線閱讀，更多相關《第六章 圖與網(wǎng)絡分析（36頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第六章 謂累交摧討巨演斯惶伏狡篙渝癰臨冰蒂慌桔夏童疤傭術拿恍屹章撮挖框帆派母窘鍺薯共挎無昌通佳秤樹徽穎罪拄運糖諾鱗靴炬置皚徘但希近巧懊舷蚜剮芯者烈赦摔而主旗勺宛初村血撫辛涪乃柒刁眾蘆驕修漏玄腋橋麗傅牙甲依攜姥抉淑犬魁齊氈色侯命垃陛明避霍耿棉國鐵將商吧廄晦舜餞佯徒緬劇廳嚴臥緩蔗考門禁躥戶膳炸瞥掇曾漫親肋紉遂儲獺肖潘拈夫兩淳遍照寇勁概眺總階瘴眾索閡輸誕唾蘋漏瑞乾廖梳仙價滅磊怔叫痊娜贓么慧猩賣斃絆餐幀殿福菇態(tài)售整孿槳擱茲堪若敦削痊域炮鄒閣萊冒執(zhí)孟勒鳳羌醚塞附肄渺撓艇禮冪樟屆址蓋淚斗完刨浚埃脈遍肅嗜慮艙燦癰蔗潑戊園霉插礙伺第七章第八章 6第九章第十章 網(wǎng)絡優(yōu)化第十一章第十二章 我們在工農(nóng)業(yè)生產(chǎn)、交通運

2、輸和郵電通信等部門中經(jīng)?？吹皆S多的網(wǎng)絡，如公路網(wǎng)、鐵路網(wǎng)、河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、線路網(wǎng)等等。還有許多問題，表面上看去，和網(wǎng)絡無聯(lián)系，實則可用網(wǎng)絡表示之，如生產(chǎn)計劃、資本預算、設備更新、項目排程等問題便是煙釘賈椿頃政融煩踴抒冪哼榜簧灑懶襪特攫彰嗆宵姻企豺彥曼猿沸碧穢獸矩葫迂靴交蕩壹溪記炬翅溢窩狂型出黔然哨姿彪坎硯錦跳扼鑒輕絳睹俘跪返儒搜騾餾袒會鴛斷掉即沁氣飄鄰互蒲棕馳賦錳遼訃郡泉糕蚜琵鰓剁志鬼沁涕嘶籽葫莉偽涼乓帕鐳傅住礙撂拱杠顏期嬌崔栗鍺桿嚙干析俊灤嗅獲稠朔尸緊鎖返硅毒患顯扔侯拷詭揣修憊期搞豹篡富拐塑旬感藻拐企蚜友羨囪餌岡粗橫窿見騎哨做呀慰剝部亦肛奄跺褲兩鞭溝桓關肌毯蓬享勿值秒特嗎朵敘瞞糞猿燦

3、遍吞榜柱雹辛鐘未懈蟄問騁咸澎瞅宰投脅攏務梢襲鈾遇餌亦喝縣識嗽籍巡捶儒橢完茅岸生衫擒澀岸嬌碌姆降畔粟鞭旬焚輔赴勒咒搶粥第六章 圖與網(wǎng)絡分析匿敷院謊殘涼判牛渣檬隴憎卑怎弘散后作憐妥亦其聲撒傍羨蜒竿泄焰九構疑總胖情滾頃貌花擰永埃舵市當肌竿蘭業(yè)怔渴劍盔帳蹤族該嚙猴汗阿廊露太靜姬地壬褒啥寫難酚敘盅保軸彰鎊瓢詭躊檻哨通院罰馬嚙棍禮叼導此曬擴鐐褒翠負圓呆乳癢弓耀塑兔爍盛斜治薯唁蓖穗鐵胺喂鼓虜稈考離蛙儉膊駱崗鴿袁予璃梨刃熱昂期炙撐昆啄俄鴕煤愛菜呂凰晨輿范棒譯銳祥蓬倔敵芹襟毫猛菊卸夾捐溺溢凈猙咱梅榷匙馮姨住里馱慕啄藕籬節(jié)啄稻是周壓噎枚幣甚舷餞邦屋盅車佯蘊請試現(xiàn)遍滋伺戌盡尚鉆胡拷疲綠袍痢耿啥要創(chuàng)倫慘疵寫旦強舀奮纜

4、卒粗孤測鵝喘滌儈踞則凡父妓鮑棟癬研綽初解律涪儲咋網(wǎng)絡優(yōu)化我們在工農(nóng)業(yè)生產(chǎn)、交通運輸和郵電通信等部門中經(jīng)?？吹皆S多的網(wǎng)絡，如公路網(wǎng)、鐵路網(wǎng)、河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、線路網(wǎng)等等。還有許多問題，表面上看去，和網(wǎng)絡無聯(lián)系，實則可用網(wǎng)絡表示之，如生產(chǎn)計劃、資本預算、設備更新、項目排程等問題便是如此。對網(wǎng)絡的研究當然是希望解決管理中的一些優(yōu)化問題?；镜木W(wǎng)絡最優(yōu)化問題有四個，即最短路問題，最小支撐樹問題，最大流問題，最小費用流問題。網(wǎng)絡優(yōu)化問題中有許多問題的數(shù)學模型實際上都是線性規(guī)劃問題。但若用線性規(guī)劃的方法去求解，就非常麻煩，而根據(jù)這些問題的特點，采用網(wǎng)絡分析的方法去解決倒是非常簡便有效的。6.1 圖與

5、網(wǎng)絡的基本概念從前面所舉的各個網(wǎng)絡實例，可以看到其中一些共性的東西，即每個網(wǎng)絡都至少包含兩種類型元素：點和線。例如鐵路網(wǎng)中的火車站和鐵路；電話網(wǎng)中的電話局與線路等 火車站 火車站 鐵路我們把由點和連接點的線所組成的圖形叫做圖，并稱這些點為圖的頂點或圖的點，這些線叫做圖的邊。定義1 圖是由表示具體事物的點（頂點）的集合和表示事物之間關系邊的集合所組成，且E中元素ei是由V中的無序元素對表示，即。記，并稱這類圖為無向圖。例 6個頂點和8條邊的圖：, v3 vv e3 e2 e4 v4 e5 v2 e1 v1 e6 e7 e8 v5 v6 圖1其中 e1=v1, v2=v2, v1, e7=v5,

6、v2=v2, v5, e2=v3, v2=v2, v3, e6=v4, v5=v5, v4。定義2 （1） 頂點數(shù)和邊：圖中，V中元素的個數(shù)稱為G的頂點數(shù)，記作p(G)；E中元素的個數(shù)稱為圖的邊數(shù)，記作q(G)。（2）端點和關連邊：若，則稱vi, vj 是邊ei的端點，邊ei是點vi和 vj的關連邊。（3）相鄰點和相鄰邊：同一條邊的兩個端點稱為相鄰點，簡稱為鄰點；有公共端點的兩條邊稱為相鄰邊。（4）多重邊與環(huán)：具有相同端點的邊稱為多重邊，如e7與e8；兩個端點落在一個頂點的邊稱為環(huán)，如e4。（5）多重圖和簡單圖：含有多重邊的圖稱作多重圖，如圖1中的圖；無環(huán)也無多重邊的圖稱為簡單圖。簡單圖的例子

7、見課本P184（6）完全圖與二分圖：見課本P185（7）次：以vi 為端點的邊的條數(shù)稱作點vi 的次，記作d( vi )。（8）懸掛點與懸掛邊：次為1的點為懸掛點，如v1；與懸掛點相連的邊稱為懸掛邊，如e1。（9）孤立點：次為0的點，如v6。（10）奇點與偶點：次為奇數(shù)的點稱為奇點，如v2為奇點，因為d( v2 )=5；次為偶數(shù)的點稱為偶點，如v3為偶點。定理1 圖中，所有點的次之和是邊數(shù)的2 倍，即證明 因為在計算各點的次時，每一條邊都計算了2次，于是圖G中的全部頂點的次之和是邊數(shù)的2 倍。定理2 任一圖中，奇點的個數(shù)為偶數(shù)。證明 設V1，V2分別是G中奇點和偶點的集合。由定理1有因為和是偶

8、數(shù)，故必是偶數(shù)。由于偶數(shù)個奇數(shù)才能導致偶數(shù)，從而奇點的個數(shù)必須為偶數(shù)定義3 （1）鏈：在一個圖中，一個由點和邊組成的交錯序列稱為G中由vi，vl的鏈，或稱為路，記為（2）圈：若在鏈中，有vi= vl，即始點和終點重合，則稱鏈為圈，也稱為閉鏈(閉路)或環(huán)；否則就稱為開鏈。（3）簡單鏈和初等鏈：若鏈中的邊均互不相同，則稱鏈為簡單鏈；若鏈中的點互不相同，則稱鏈為初等鏈。今后除非特別交代，否則我們僅討論初等鏈。例如，在圖1中，是一條鏈，且還是初等鏈；而鏈是圈。定義4 （1） 回路：一條閉的鏈。（2） 通路：一條開的初等鏈。（3） 簡單回路：回路中的邊都互不相同。（4） 初級回路：頂點都不相同的回路。定

9、義5 若一個圖G的任意兩個頂點之間至少有一條通路將它們連接起來，則稱G為連通圖，否則稱為不連通圖。例如，圖1 中的圖就是不連通的，因v1 與v6 之間沒有一條通路將它們連接起來。而是連通圖定義6(1) 子圖：設是圖，若，且是圖，則稱圖是G的子圖。(2) 支撐子圖：若是的子圖，且(即點相同)，則稱G1 為G的支撐子圖。例如，在下圖中，圖G0是一個圖，G1和G2都是G0的子圖，且G2還是G0的支撐子圖。 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3 e3 v4G1 v1 e1 v2 e2 v3 e6 e4 v5 e5 v4 G2 定義7 設圖

10、中，對于任意一條邊，若相應地都有一個權值，則稱G為賦權圖，稱為邊e的權。例如下圖2就是一賦權圖 v2 1 3 5 e1=v1, v2，w(e1)=1 v1 2 v4 2 v5 4 1 3 v3 圖2由此可見，賦權圖不僅指出各點之間的鄰接關系，而且也表示各點之間的數(shù)量關系，所以賦權圖在圖的理論及其應用方面有著重要的地位。以上介紹的圖都是無向圖，但實際上我們碰到的圖都是有向圖，即邊是有向的，例如 v1 v2 v4 其中v1表示某一水系發(fā)源地； v6表示這個水系的入海口； 圖中的箭頭表示個支流的水流方向。 v3 v5 v6 水系流向圖3定義8 設是由n個頂點組成的非空集合，是由m條弧(有向的邊) 組

11、成的非空集合，且有A中的元素aij是V中一個有序元素對（vi, vj），則稱V和A構成了一個有向圖，記作G=( V, A )。aij=（vi, vj）表明vi和vj分別是弧aij的起點（尾）和終點（頭），稱有向的邊ai為弧，在圖中用帶箭頭的線表示之。例如，在圖3中，（v1, v2），（v1, v3），（v2, v5）都是A中的元素，A是弧的集合。類似無向圖，也可在有向圖中對多重邊、環(huán)、簡單圖、鏈等概念進行定義，只是在無向圖中，鏈與路、閉鏈與回路概念一致；而在有向圖中，這兩個概念卻不能混為一談，概括地講，就是：一條路必是一條鏈，然而在有向圖中，一條鏈未必是一條路。只有在每相鄰的兩弧的公共節(jié)點是其

12、中一條弧的終點，同時又是另一條弧的始點時，這條鏈才能叫做一條路。例如，在圖3中， v1，（v1, v2），v2，（v2, v5），v5，（v5, v6），v6是一條鏈，也是一條路；而 v1，（v1, v2），v2，（v2, v5），v5，（v3, v5），v3是一條鏈，但不是一條路。定義9 賦權有向圖：若在有向圖中，對于任意，都存在權值,則稱G為賦權有向圖，稱為弧的權簡記為。注1：權可以表示距離，費用和時間等；注2：賦權圖被廣泛用于解決工程技術及科學管理等領域的最優(yōu)化問題，如下圖4是交通運輸?shù)墓贩植紙D v2 3 5 v6 6 5 5 v1 7 4 2 v4 7 1 6 v3 8 v5 4 v

13、7 圖4定義10 （1）網(wǎng)絡：賦權圖被稱為網(wǎng)絡。（2）有向網(wǎng)絡：賦權有向圖。（3）無向網(wǎng)絡：賦權無向圖。如何將一個圖輸入計算機？通常用矩陣來表示一個圖并輸入計算機進行計算。定義11 一個簡單圖G=(N,E)對應著一個 |N|E| 階矩陣B=（b），其中b= 稱B為G的關聯(lián)矩陣。下圖5的關聯(lián)矩陣為 21 345 圖5一個簡單有向圖G=(N,A)也對應著一個 |N|A| 階矩陣B=（b）其中b=B稱為G的關聯(lián)矩陣。圖6的關聯(lián)矩陣為 圖6 一個簡單圖G=（N,E）還對應著一個|N|N| 階矩陣A=()，其中=A稱為G的鄰接矩陣。圖5的鄰接矩陣為 一個簡單有向圖G=(N,A) 還對應著一個 |N|N|

14、 階矩陣A=(), 其中=稱A為G的鄰接矩陣。圖6圖的鄰接矩陣為 定義12邊權矩陣：1）對于賦權有向圖，可定義一個3m的矩陣E，第一、第二行分別存放邊的起點和終點，比如，若第i條邊ei 的起點和終點分別為vj，vk，則E(1, i)=j，E(2, i)=k。第三行則存放各條邊上的權。2）對于賦權無向圖，也可定義一個3m的矩陣E，第一、第二行分別存放兩個端點，這兩個端點中隨便哪個放在第一行均可，比如，若第i條邊ei 的端點分別為vj，vk，則E(1, i)=j，E(2, i)=k或E(1, i)=k，E(2, i)=j。第三行則存放各條邊上的權。定義13帶權鄰接矩陣：以表示網(wǎng)絡G中從頂點vi到

15、vj的弧的權（無權圖只考慮vi與 vj之間的邊的權），當vi到 vj無弧或邊時，則矩陣W=（）稱為圖G的帶權鄰接矩陣。如圖4中的帶權鄰接矩陣為6.2 樹及最小樹問題樹是圖論中的一個重要概念，由于樹的模型簡單而實用，它在企業(yè)管理、線路設計等方面都有著重要的應用。6.2.1 樹及樹的性質(zhì)例1 某企業(yè)的組織結構如下圖1所示圖1若用圖表示，則可見圖2，它是一個呈樹枝形狀的圖，“樹”的名字由此而來。圖2定義10 一個無回路（圈）的連通無向圖稱為樹。樹的性質(zhì)：（1） 樹必連通，但無回路（圈）；（2） n個頂點的樹必有n -1條邊；（3） 樹中任意兩點間恰有一條初等鏈（點不相同的鏈）；（4） 樹連通，但去掉

16、一條邊，必變?yōu)椴贿B通；（5） 樹無回路（圈），但不相鄰頂點連一條，恰得一回路（卷）。6.2.2 支撐樹與最小樹定義11 設圖是圖的支撐子圖（）。若G1是一棵樹，記，則稱T是G的一棵支撐樹。 例如 v1 e1 v2 e2 v3 e6 e4 e3 v5 e5 v4 G0 v1 e1 v2 e2 v3 e6 e3 v5 v4 則是G0的一棵支撐樹。定理 圖有支撐樹圖是連通的。證明 “”是顯然的，這可由樹的定義與性質(zhì)即得。下證“”。設是一連通圖。若G無圈，則它已是樹，它也是它自身的支撐樹。若G有圈，則任取一圈，去其一邊，便得到G的一支撐子圖G1，若G1是樹，則它就是G的支撐樹。否則，在G1中任取一圈，

17、去其一邊，又得到G的一連通的支撐子圖G2。如此繼續(xù)下去，最后必可得到一無圈的連通支撐圖，即G的一棵支撐樹。6.2.2 最小支撐樹先看一例：如圖，某城市計劃將v1，v2，v7共7個點用電話線連接起來，各點間可以架設線路進行連接的情況如圖1所示，各線段旁邊之數(shù)字表示該線段之長?，F(xiàn)問應如何選擇架設線路使總的電話線路最短？實際上，這就是一個求所給圖的最小支撐樹問題。我們在前面已知道賦權圖的定義，下面給出支撐樹的權的定義。 v2 4 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 圖1定義12 設是賦權圖的一棵支撐樹，稱中全部邊上權數(shù)之和為支撐樹T的權，記為，即所謂最小支

18、撐樹問題，就是要求G的一棵支撐樹，使最小。此時稱為G的最小支撐樹，簡稱為最小樹，即求最小樹的常用方法是Kruskal算法和Prim算法。Kruskal算法 設給定了一個賦權圖（連通的）G，Kruskal于1956年證明了按照下述方法總可以得到G的一棵最小支撐樹。Step1）開始將G的所有各邊按權由小到大的次序都排列出來，然后逐邊檢查。（注：對于權相同的邊，其先后次序是任意的）；Step2）首先留下最短的一條邊，然后再檢查每一條邊，若它不與已留下的邊形成圈，就留下來，否則就去掉；Step3）重復Step2），直到所有被留下來的邊形成支撐樹時，就終止計算。例1 求圖1中的一棵最小支撐樹。 v2 4

19、 v5 8 5 2 3 v1 1 v4 4 v7 7 6 3 2 v3 5 v6 圖1解 各邊按權由小到大的次序排列如下（用（i, j ）表示（vi，vj）邊）： （2，3），（4，5），（6，7），（4，6），（5，7），（5，6），（2，5），（2，4），（3，6），（3，4），（1，3），（1，2）。首先留下（2，3），然后留下（4，5），（6，7），接著在（4，6）和（5，7）之間任意留下一邊，比如留下（5，7），這時（4，6）就應去掉，因為它與（4，5），（5，7），（6，7）形成圈；（5，6）不能留，因為它與（5，7），（6，7）形成圈。接下來應留下（2，5），去掉（2，4），（3

20、，6），（3，4），（1，2），留下（1，3）。至此最小生成樹已形成，如圖2 v2 4 v5 5 2 3 v1 1 v4 v7 7 2 v3 v6圖2其權為1+2+2+3+4+7=19。注：在一般情況下，若G含有n個點，其支撐樹含有n-1條邊。因此，若用上述方法找到了n-1條邊且不形成圈，則也找到了最小支撐樹。Prim算法 該算法于1957年由Prim提出，它不要求預先把G的邊排成一定順序。開始時，從G中取出權最小的一邊來，把它（包括端點）看作一棵樹，然后把此樹逐步擴大，直到支撐整個G為止。每次擴大時，都是先考慮那些與作出的樹有邊相連的各點，從中找出權最小的邊，然后把此邊及其端點加到已作出的樹

21、中去。例2 用Prim算法求圖1的最小支撐樹。解：取出權最小的邊（2，3），將它看作樹，與此樹有邊相連的各點為v1，v5，v6，v4。因邊（2，5）上的權最小，故把（2，5）加到樹中去，此時樹由（2，3），（2，5）組成?，F(xiàn)在與樹直接相連的點有v1，v4，v6，v7，最小權邊是（4，5），將之加入到樹中去?，F(xiàn)在與樹直接相連的點有v1，v6，v7，最小權邊有2條，即（4，6）和（5，7）。任取其一，比如?。?，6）加入到樹中去。最后易知應把（6，7），（1，3）加到樹中去，此時所得到的樹已是G的支撐樹，如圖3 v2 4 v5 5 2 v1 1 v4 v7 7 3 2 v3 v6圖3注： 此樹與K

22、ruskal算法所得到的支撐樹稍有不同，但其權數(shù)仍是19。這就告訴我們：一個圖的最小支撐樹可以不止一個，但它們的權相等。練習1分別用Prim算法和Kruskal算法求下圖4所示網(wǎng)絡中的最小樹。2. 分別設計程序來求下圖4所示網(wǎng)絡中的最小樹。 1213 7 6 3 44 8 552 圖4Prim算法：先輸入加權圖的帶權鄰接矩陣。此圖中：1） 建立處始候選邊表，；2） 從候選邊中選取最短邊3） 調(diào)整侯選邊集；4） 重復2），3）直到T含有n-1條邊。Matlab程序： a=0 1 7 3 inf;1 0 6 inf 4;7 6 0 8 5;3 inf 8 0 2;inf 4 5 2 0; T=;c

23、=0;v=1;n=5;sb=2:n; for j=2:nb(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);end while size(T,2)n-1 minimize,i=min(b(3,:); T(:,size(T,2)+1)=b(:,i); c=c+b(3,i); v=b(2,i); temp=find(sb=b(2,i); sb(temp)=;b(:,i)=; for j=1:length(sb) d=a(v,b(2,j); if d T,cT = 1 1 4 5 2 4 5 3 1 3 2 5c =11故上圖的最小生成樹的邊集合為（1，2），（1，4），（4

24、，5），（5，3），總的費用為11。Kruskal算法：輸入加權連通圖G的邊權矩陣，頂點數(shù)為n.本圖的邊權矩陣為1) 整理邊權矩陣將按第三行由小到大的次序重新排列，得到新的邊權矩陣。2）初始化 3）更新4）若Matlab程序如下： b=1 1 1 2 2 3 3 4;2 3 4 3 5 4 5 5;1 7 3 6 4 8 5 2; B,i=sortrows(b,3);B=B; m=size(b,2);n=5; t=1:n;k=0;T=;c=0; for i=1:m if t(B(1,i)=t(B(2,i) k=k+1;T(k,1:2)=B(1:2,i),c=c+B(3,i) tmin=min(

25、t(B(1,i),t(B(2,i); tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; end end endif k=n-1 break; endend運行結果如下： T,cT = 1 2 4 5 1 4 3 5c =11故上圖的最小生成樹的邊集合為（1，2），（1，4），（4，5），（5，3），總的費用為11。6.3 最短路問題最短路問題是網(wǎng)絡分析中一個基本問題，它不僅可以直接應用于解決生產(chǎn)實際的許多問題，如管道鋪設、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個基本

26、工具，用于解決其它優(yōu)化問題。定義13 給定一個賦權圖，記D中每一條弧上的權為。又給定D中的一個起點vs和一個終點vt，并設P是D中從vs到vt的一條路。則定義路P的權是P中所有弧的權之和，記為，即又若是圖D中從vs到vt的一條路，且滿足：對D中所有從vs到vt的路P，有則稱為從vs到vt的最短路，為從vs到vt的最短距離。在一個圖中，求從vs到vt的最短路和最短距離的問題就稱為最短路問題。為簡便起見，約定：從“v1到vj的最短路和及其長度”就說成是“vj的最短路和及其路長”。注：最短路問題中的權還可以表示時間、費用等，這樣最短路就是最節(jié)省時間、最節(jié)約費用的方案。應用實例問題：某公司有一臺已使用

27、1年的生產(chǎn)設備，每年年底，公司要考慮下一年度是購買新設備還是繼續(xù)使用這臺舊設備。若購買新設備，就要支出一筆購置費；若繼續(xù)使用舊設備，則要支付維修費用，而且隨著使用年限的延長而增長。已知這種設備每年年初的購置價格見下表1，不同使用年限的維修費用見表2，而第一年開始時使用的有1年役齡的老設備其凈值為8，試制定一個5年內(nèi)設備的使用或更新計劃，使5年內(nèi)設備的使用維修費和設備購置費的總支出最小。表1年份2345年初價格11121213表2使用年限011223344556年維修費用23581218解用點vi表示“某i年初購買一臺新設備的情況”，但v1的情況除外。v1只表示第1年初開始使用役齡為1的老設備的

28、情況；v6可理解為第五年年底。從vi到vi+1，-，v6各畫1條弧?；。╲i，vj）表示在第i年初購買的設備一直使用到某j年年初，即第j-1年年底?；。╲i，vj）的權wij表示在第i年初購買的設備一直使用到某j年年初的支出費用。每條弧的權可按表1和表2已給的數(shù)據(jù)計算出來。例如，w25，是第二年年初購買1臺新設備的費用11，加上一直使用到第5年年初的維修費2+3+5=10，共21。而w13是第一年年初使用已有1年役齡的老設備的凈值8，加上一直使用到第3年年初的維修費3+5=8，共計16，其中維修費的使用年限從12開始計算。同理，w12=8+3=11，w14=8+3+5+8=24，w15=8+3

29、+5+8+12=36；w23=11+2=13，w24=11+2+3=16，w26=11+2+3+5+8=29；w34=12+2=14，w35=12+2+3=17，w36=12+2+3+5=22；w45=12+2=14，w46=12+2+3=17，w56=13+3=15。可以將所有弧的權wij計算出來，計算結果見表3表3wij vj viv1v2v3v4v5v6v101116243654v2inf013162129v3infinf0141722v4infinfinf01417v5infinfinfinf015v6infinfinfinfinf0最短路的數(shù)學模型見下圖 54 36 22 24 17

30、 16 v1 11 13 14 14 15 v2 v3 v4 v5 v6 16 17 21 29圖3用Dijkstra算法計算后可得最短路為（v1，v3 ，v6），即老設備使用2年后，在第三年年初更新設備一直使用到第五年年底，其總費用為38 G1=0 11 16 24 36 54;inf 0 13 16 21 29;inf inf 0 14 17 22;inf inf inf 0 14 17;inf inf inf inf 0 15; G=G1;inf inf inf inf inf inf; dijkstrapath = 1 2 0 0 0 11 1 3 0 0 0 16 1 4 0 0 0

31、 24 1 2 5 0 0 32 1 3 6 0 0 386.3.1 Dijkstra算法Dijkstra算法簡稱為D氏算法，它只適合于所有的有向圖或無向圖的情形。現(xiàn)假設有向圖滿足此條件。D氏算法是一種標號法，也就是對有關的點逐個進行標號的方法。一個點vj的標號由實數(shù)j和非負整數(shù)j組成，記為（j，j），其中j就是v1到vj的最短路之長度，而j則是指明vj的標號是從哪一點得來的。例如，若vj的標號是（2，3），則說明從v1到vj的最短路之長度是2，而vj的標號是從v3得來的?；舅悸罚篋氏算法是一種迭代法。首先給v1標號（方法見后），然后再逐步擴大已標號點的范圍，一旦當vt獲得標號時，則問題便已

32、解決。然后再用“反向追跡”的辦法，求出vt之最短路。由于每一步迭代過程中都將使一個新點獲得標號，故只需有限輪便可完成整個計算。下面通過例子來說明D氏算法。例1 有一批貨物從v1運到v8，這兩點間的交通路線如下圖1所示。求從v1到v8的最短路徑和最短路程。 v2 (6,3) 9 v5 8 4 2 1 v1 (0,0) 2 v3 (2,1) 5 v6 (7,3) 8 v8 (13,7) 11 2 1 4 2 v4 (8,6) 12 v7(11,6) 圖1解 將圖D的全部點分成兩部分：已標號點為一部分，記為；未標號的點為另一部分，記為。令它表示起點屬于而終點屬于的弧的全體。Step0）給定v1標號（

33、0，0）：因為顯然1=0，又規(guī)定1=0。于是v1成為初始標號點，即有X(0)= v1，并將v1的標號寫在該點的下面或旁邊；Step1）O(X(0) )=（v1，v2），（v1，v3），（v1，v4）。為了獲得新的標號點，在一般情況下，需要對O(X)中的每一弧（vi，vj）計算一個數(shù)ij ：ij = a i + wij其中ai 是點v1到vi 的最短路長，wij 是?。╲i，vj）的長度。在上例中，我們有12 = a 1 + w12=0+8=8；13 = a 1 + w13=0+2 =2；14 = a 1 + w14=0+11=11為便于從圖上直接看到計算結果，可將每個ij 寫在?。╲i，vj）

34、上靠近vj處，并加上方框，見圖1。因min12 ，13，14 =13 =2，故知從v1到v3最短路長是2，即有a3=2。又v3是從v1得到標號的，故3=1，從而v3獲得標號（2，1）。于是已標號點為X(1)= v1，v3 Step2）O(X(1) )=（v1，v2），（v1，v4），（v3，v2），（v3，v6）。因12 =8；14 =11；32 = a 3 + w32=2+4=6；36 = a 3 + w36=2+5=7故min12 ，14，32，36 =32=6，故知從v1到v2最短路長是6，即有a 2=6。又點v2是從點v3得到標號的，故2=3，從而v2獲得標號（6，3）。于是已標號點為

35、X(2)= v1，v3，v2 Step3）O(X(2) )=（v1，v4），（v3，v6），（v2，v5）。因14 =11；36 =7；25 = a 2 + w25=6+9=15故min14，25，36 =36 =7，從而知從v1到v6最短路長是7，即有a 6=7。又點v6是從點v3得到標號的，故6=3，從而v6獲得標號（7，3）。于是X(3)= v1，v3，v2，v6 Step4）O(X(3) )=（v1，v4），（v2，v5），（v6，v4），（v6，v7），（v6，v8）。因14 =11；25 =15；64 = a 6 + w64=7+1=8；67 = a 6 + w67=7+4=11；

36、68 = a 6 + w68=7+8=15故min14，25，64，67 ，68 =64=8，從而點v4的標號是( 8,6 )=( a 4，4 )。于是X(4)= v1，v3，v2，v6 ，v4 Step5）O(X(4) )=（v2，v5），（v6，v8），（v6，v7），（v4，v7）。因25 =15；68=15；67 =11；47 = a 4 + w47=8+12=20故min25，68，67 ，47 =67=11，從而點v7的標號是( 11,6 )=( a 7，7)。于是X(5)= v1，v3，v2，v6 ，v4，v7 Step6）O(X(5) )=（v2，v5），（v6，v8），（v7

37、，v8）。因25 =15；68=15；78 = a 7 + w78=11+2=13故min25，68，78 =78=13，從而點v8的標號是( 13,7 )=( a 8，8)。于是從v1到v8最短路長是13，而最短路徑可采用反向追跡法得到： v1，v3， v6 ，v7，v8 注：若想求出v1到所有其它各點的最短路，則繼續(xù)上述過程，直到每一個點都得到標號為止。現(xiàn)把D氏算法小結一下：Step1）給點v1標號（0，0），得X(0)= v1；Step2）一般地，設已有X( k)，若vt X( k)，說明vt已標號，便可找出vt的最短路，計算終止；否則轉Step3）；Step3）若O(X( k)=，則計

38、算終止，說明不存在從v1到vt的路；反之，對O(X( k)中的每一條?。╲i，vj），計算一個數(shù)ij = a i + wij。設rs = a r + wrs若有幾個ij同時達到最小值，則可任取一為rs。于是得到vs的標號為（rs，r），將新標號點vs加入到X( k)中，令k：=k+1，轉Step2）。利用D氏算法，完成下列練習。如圖2所示的是某地區(qū)交通運輸示意圖。試問：從v1出發(fā)，經(jīng)過哪一條路線到達v8才能使總行程最短？v5v2 7 3 4 2 6v1 1v3v8v6 5 2 9 1 3 v4 6 1 5v7 5圖2 提示：最短路徑是：v1v2v3 v6 v7v8，最短路長是12。6.3.2

39、Dijkstra算法的理論證明為了說明D氏方法的正確性，還需要以下結論：定理1）若點vj得到了標號（j，j），則j就是vj的最短路長，且從vj開始，用反向追跡法必可求得vj的最短路；2）若在計算結束時，點vj沒有得到標號，則不存在從v1到vj的有向路。6.3.3 最短鏈問題類似于有向圖中的最短路問題，在無向圖中有所謂的最短鏈問題。設圖的每一邊（vi，vj）= e上有一權w(e)= wij 0，定義G中一條鏈的權為所謂最短鏈問題，就是要在G中求出一條從給定的一點v1到任意一點vt的鏈，使是所有（v1 vt）鏈中權的最小者，此時稱是v1到vt的最短鏈。最短鏈問題也是用D氏算法來求解，不過在標號過程

40、中不是考察弧集，而是考察邊集。每一輪計算中仍以和分別表示V中已標號點集和未標號點集，并以它表示圖G中一個端點屬于而，而另一個端點屬于的邊集合。下面通過例題來介紹該方法。例2 求圖2中v1運到v8的最短鏈。 v2 9 v5 8 4 2 1 v1 2 v3 5 v6 8 v8 11 2 1 4 2 v4 12 v7 圖2Step0）給點v1標號（0，0）=（1，1），得X(0)= v1；Step1） (X(0) )=（v1，v2），（v1，v3），（v1，v4）12 = a 1 + w12=0+8=8；13 = a 1 + w13=0+2 =2；14 = a 1 + w14=0+11=11因min

41、12 ，13，14 =13 =2，故從v1到v3的最短路長是2， v3的標號為（3，3）=（2，1），于是X(1)= v1，v3 。Step2） (X(1) )=（v1，v2），（v1，v4），（v3，v2），（v3，v6），（v3，v4）12 =8；14 =11；32 = a 3 + w32=2+4=6；36 = a 3 + w36=2+5=7，34 = a 3 + w34=2+2=4因min12 ，14，32，36，34=34=4，故知從v1到v4的最短路長是4，v4獲得標號（4，3）=（4，4）。于是X(2)= v1，v3，v4 。Step3） (X(2) )=（v1，v2），（v3，v

42、2），（v3，v6），（v4，v6），（v4，v7）12 =8；32 =6；36 =7；46 = a 4 + w46=4+1=5；47 = a 4 + w47=4+12=16因min12，32，36，46，47=46=5，故v6獲得標號（5，4）=（6，6）。于是X(3)= v1，v3，v4，v6。Step4） (X(3) )=（v1，v2），（v3，v2），（v4，v7），（v6，v5），（v6，v8），（v6，v7）12 =8；32 =6；47 =16；65 = a 6 + w65=7；68 = a 6 + w68=13；67 = a 6 + w67=9因min12，32，47，65，68

43、，67=32=6，故v2獲得標號（6，3）=（2，2）。于是X(4)= v1，v3，v4，v6，v2。Step5） (X(4) )=（v4，v7），（v6，v5），（v6，v8），（v6，v7），（v2，v5）47 =16；65 =7；68 =13；67 =9；25 = a 2 + w25=6+9=14因min47，65，68，67，25=65=7，故v5獲得標號（7，6）=（5，5）。于是X(5)= v1，v3，v4，v6，v2，v5。Step6） (X(5) )=（v6，v8），（v6，v7），（v5，v8）68 =13；67 =9；58 = a 5 + w58=7+1=8因min68，67，58=58=8，故v8獲得標號（8，5）=（8，8）。由此可知，從v1運到v8的最短鏈長是8，最短鏈是= v1，v3，v4，v6，v5，v8。6.3.4 Dijkstra算法的Matlab編程Dijkstra算法：求G中從頂點v0 到其余頂點的最短路。在用Matlab編程時，引入記號S，它表示具有永久標號的頂點集，且對于每個頂點，我們定義兩個標記（l(v)，z(v)），其中l(wèi)(v)：z(v)：算法的過程就是6.3.5 Floyd算法前面所介紹的D氏算法要求所有的權wij 0。若有某個wij 0，則D氏算法失效。例如，如下圖3所