運籌學課件 51圖論

《運籌學課件 51圖論》由會員分享，可在線閱讀，更多相關《運籌學課件 51圖論（78頁珍藏版）》請在裝配圖網上搜索。

1、第五章第五章圖與網絡分析圖與網絡分析圖是最直觀圖是最直觀的模型的模型引言引言圖論的起源和發(fā)展圖論的起源和發(fā)展加里寧格勒加里寧格勒普雷格河普雷格河？這個問題看起來似乎不難，但人們始終沒有能找到答案，最這個問題看起來似乎不難，但人們始終沒有能找到答案，最后問題提到了瑞士大數學家歐拉那里。歐拉以深邃的洞察力后問題提到了瑞士大數學家歐拉那里。歐拉以深邃的洞察力很快證明了很快證明了郵冊郵冊LeonhardEuler(1707-1783)“圖論之父圖論之父”From a German stampSwissFrom a Russian stampGermanGerman陸地看作陸地看作4個節(jié)個節(jié)點，橋看作點

2、，橋看作7條條邊作邊作圖圖是否可以是否可以一筆畫？一筆畫？35332421331u一次走完所有的橋，不重復，除起點與終點外，其余一次走完所有的橋，不重復，除起點與終點外，其余點必須有偶數條邊，所以七橋問題無解。點必須有偶數條邊，所以七橋問題無解。u 18751875年年,B,B與與C C 之間新建了一條橋解決了該問題！之間新建了一條橋解決了該問題！歐拉歐拉把七橋問題概括為數學模型，開啟了數學圖論把七橋問題概括為數學模型，開啟了數學圖論,將圖將圖抽象為頂點與邊的集合。抽象為頂點與邊的集合。u圖論是網絡研究的基礎圖論是網絡研究的基礎18561856年，英國數學家年，英國數學家哈密爾頓哈密爾頓Ham

3、iltonianHamiltonian 由于運籌學、計算機科學和編碼理論中的很多問題都由于運籌學、計算機科學和編碼理論中的很多問題都可以化為哈密頓問題，從而引起廣泛的注意和研究?？梢曰癁楣茴D問題，從而引起廣泛的注意和研究。發(fā)明發(fā)明“環(huán)球旅行環(huán)球旅行”游戲游戲 十二面體的十二面體的2020個頂點代表世界上個頂點代表世界上2020個城市，個城市，能否從某個城市出發(fā)在十二面體上依次經過每個能否從某個城市出發(fā)在十二面體上依次經過每個城市恰好一次最后回到出發(fā)點？城市恰好一次最后回到出發(fā)點？即即“環(huán)球旅行環(huán)球旅行”?！八纳孪胨纳孪搿眴栴}（問題（18521852年年）:圖論的歷史上最具有傳圖論的歷史上

4、最具有傳奇色彩的問題奇色彩的問題歷史上許許多多數學猜想之一。歷史上許許多多數學猜想之一。人們在長期為地圖人們在長期為地圖(平面圖平面圖)上色時發(fā)現(xiàn)，對任何一上色時發(fā)現(xiàn)，對任何一張地圖進行著色，兩個共同邊界的國家染不同的顏色，張地圖進行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了則只需要四種顏色就夠了.四色猜想的證明一直沒有解決，直到一百多年后，四色猜想的證明一直沒有解決，直到一百多年后，在計算機出現(xiàn)以后，于在計算機出現(xiàn)以后，于19761976年用計算機算了年用計算機算了12001200多小多小時，才證明了四色猜想問題。時，才證明了四色猜想問題。02013118471847年，德

5、國物理學家年，德國物理學家kirchhoffkirchhoff，發(fā)表了關于發(fā)表了關于“樹樹”的第一篇論文，電網絡的第一篇論文，電網絡中的求解聯(lián)立方程的問題中的求解聯(lián)立方程的問題18571857年，英國數學家年，英國數學家A.GayleyA.Gayley，“樹樹”，有機化合物的分子結構中的同分異，有機化合物的分子結構中的同分異構問題構問題凱萊凱萊1964年，華羅庚，年，華羅庚，統(tǒng)籌方法平話統(tǒng)籌方法平話。1956年，杜邦公司，年，杜邦公司，CPM，關鍵路線法；關鍵路線法；1958年，美國海軍部，年，美國海軍部，PERT，計劃評審技術；計劃評審技術；1962年，管梅谷，年，管梅谷，中國郵路問題中國郵

6、路問題；1936年，匈牙利數學家哥尼格發(fā)表了第一本圖論專著年，匈牙利數學家哥尼格發(fā)表了第一本圖論專著有限圖有限圖與無限圖的理論與無限圖的理論20世紀世紀50年代年代圖論形成了兩個本質上不同的發(fā)展方向圖論形成了兩個本質上不同的發(fā)展方向圖論的代數方向圖論的代數方向圖論的最優(yōu)化方向圖論的最優(yōu)化方向圖的用處圖的用處n 圖則是一種直觀的模型，如公路、鐵路交通圖，通訊網圖則是一種直觀的模型，如公路、鐵路交通圖，通訊網絡圖等。絡圖等。n圖論與網絡分析理論所研究的問題十分廣泛，內容極圖論與網絡分析理論所研究的問題十分廣泛，內容極其豐富。正如一位數學家所說：其豐富。正如一位數學家所說：“可以說，圖論為任何可以說

7、，圖論為任何一個一個包含了某種二元關系包含了某種二元關系的系統(tǒng)提供了一種分析和描述的系統(tǒng)提供了一種分析和描述的模型。的模型?！睂ο蠹捌渎?lián)系對象及其聯(lián)系n在實際的生產和生活中，人們?yōu)榱朔从逞芯繉ο笾g在實際的生產和生活中，人們?yōu)榱朔从逞芯繉ο笾g的特定關系，常常在紙上用點和線來畫出各式各樣的的特定關系，常常在紙上用點和線來畫出各式各樣的示示意圖意圖。這就是圖論中的。這就是圖論中的“圖圖”，圖中的相對位置如何，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關點與點之間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要。因此，圖論中的圖與幾何圖，工程系，顯的并不重要。因此，圖

8、論中的圖與幾何圖，工程圖等本質上是不同的。圖等本質上是不同的。例例是北京、上海等十個城市間的鐵路交通圖。與此類似的還是北京、上海等十個城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。有電話線分布圖、煤氣管道圖、航空路線圖等。北京北京天津天津濟南濟南青島青島武漢武漢南京南京上海上海鄭州鄭州連云港連云港徐州徐州網絡結構InternetDNS、內網內網WWW服務器服務器外網外網WWW服務器服務器樓層交換機樓層交換機防火墻防火墻網管工作站網管工作站OA骨干交換機骨干交換機樓層交換機樓層交換機用戶工作站用戶工作站CISCO路由器路由器骨干交換機骨干交換機PSTN移動辦公移動辦公

9、DCN其它部門OA、EMAIL主機主機例例3“染色問題染色問題”儲存化學藥品可能因放太近易發(fā)生反應而爆炸，其中某儲存化學藥品可能因放太近易發(fā)生反應而爆炸，其中某些藥品不能存放在同一個庫房里。若我們想知道，最多有多些藥品不能存放在同一個庫房里。若我們想知道，最多有多少種化學品能存放在同一個庫房里。少種化學品能存放在同一個庫房里。碰!內容框架內容框架 一、一、圖的基本概念圖的基本概念（討論思路（討論思路）G=G=（V V，E E）子圖子圖含含元素的個數元素的個數點的次點的次邊邊特殊的圖特殊的圖點邊關系點邊關系簡簡單單圖圖多多重重圖圖連通圖連通圖樹樹部分樹部分樹ji4312 圖：圖：由點及點之間的連

10、線所組成。由點及點之間的連線所組成。點：表示所研究的對象，點的集合點：表示所研究的對象，點的集合V表示，表示，V=vi連線：表示對象間的特定關系，用兩點連線：表示對象間的特定關系，用兩點vi，vj表示表示E-邊集合，邊集合，E=ekek=vi,vjjiA弧集合，弧集合，A=akak=vi,vj4312無向圖無向圖G=（V，E）有向圖有向圖D=（V，A）Vv1、v2、v3、v4Ee1、e2、e3、e4、e5、e6、e7并且：并且：e1（v1、v2）e2（v1、v3）e3（v1、v4）e4（v2、v3）e5（v2、v3）e6（v2、v4）e7（v3、v4）V v1、v2、v3、v4 A a1、a2

11、、a3、a4、a5、a6、a7并且：并且：a 1（v1、v2）a2（v1、v3）a3（v1、v4）a4（v2、v3）a 5（v2、v3）a6（v2、v4）a7（v3、v4）端點端點例：球隊比賽圖例：球隊比賽圖ABCDE 有有A、B、C、D、E 五個球隊舉行比賽，已知五個球隊舉行比賽，已知A隊與其它各隊與其它各隊都比賽過一次；隊都比賽過一次；B隊和隊和A、C 隊比賽過；隊比賽過；C隊和隊和A、B、D 隊賽隊賽過；過；D隊和隊和A、C、E比賽過；比賽過；E隊和隊和A、D 隊比賽過。隊比賽過。點：表示球隊點：表示球隊連線：表示兩球隊間比賽過連線：表示兩球隊間比賽過 比賽結果是：比賽結果是：A隊勝了隊

12、勝了B、D、E隊；隊；B隊勝了隊勝了C隊；隊；C隊勝了隊勝了A、D隊；隊；D隊沒有勝過；隊沒有勝過；E隊勝了隊勝了D隊；隊；箭連線：箭尾表示獲勝球隊箭連線：箭尾表示獲勝球隊A隊三勝一負隊三勝一負B隊一勝一負隊一勝一負C隊兩勝一負隊兩勝一負D隊三戰(zhàn)三負隊三戰(zhàn)三負E隊一勝一負隊一勝一負G=G=（V V，E E）子圖子圖含含元素的個數元素的個數點的次點的次點邊關系點邊關系連通圖連通圖樹樹邊邊特殊的圖特殊的圖簡簡單單圖圖多多重重圖圖部分樹部分樹邊邊l l關聯(lián)邊關聯(lián)邊關聯(lián)邊關聯(lián)邊：和同一個端點相連和同一個端點相連的邊的邊,稱為該點的關聯(lián)邊稱為該點的關聯(lián)邊l l環(huán)環(huán)環(huán)環(huán)：兩個端點相同的兩個端點相同的邊邊l

13、 l多重邊：多重邊：多重邊：多重邊：兩個端點之間的邊兩個端點之間的邊數數2l l多重圖：多重圖：多重圖：多重圖：一個無環(huán)、但允許一個無環(huán)、但允許有多重邊的圖有多重邊的圖l l簡單圖：簡單圖：簡單圖：簡單圖：一個無環(huán)，無多重一個無環(huán)，無多重邊的圖邊的圖v1v2v3v4e1e2e3e4e5e6e7 G=G=（V V，E E）子圖子圖含含元素的個數元素的個數點邊關系點邊關系連通圖連通圖樹樹點的次點的次邊邊特殊的圖特殊的圖簡簡單單圖圖多多重重圖圖部分樹部分樹點點l l次次次次：一個端點一個端點v具有具有關聯(lián)邊的總數，記作關聯(lián)邊的總數，記作d(v)（每個環(huán)視作兩條邊）（每個環(huán)視作兩條邊）l l懸掛點：懸

14、掛點：懸掛點：懸掛點：次為次為1的點的點l l懸掛邊：懸掛邊：懸掛邊：懸掛邊：懸掛點的關聯(lián)邊懸掛點的關聯(lián)邊l l孤立點：孤立點：孤立點：孤立點：次為次為0的點的點l l偶偶偶偶點：點：點：點：次為偶數的點次為偶數的點l l奇奇奇奇點：點：點：點：次為奇數的點次為奇數的點v1v2v3v4e1e2e3e4e5e6e7v5e8d(v4)=d(v2)=54v6兩個主要定理兩個主要定理定理定理定理定理1 1圖圖G中，所有頂點的次的和等于所有中，所有頂點的次的和等于所有邊數的邊數的2倍。即倍。即定理定理定理定理2 2在任一圖中，奇點的個數必為偶數。在任一圖中，奇點的個數必為偶數。證明要點：證明要點：（V1

15、、V2分別是圖分別是圖G中次為奇數和偶數的頂點集合）中次為奇數和偶數的頂點集合）G=G=（V V，E E）子圖子圖含含元素的個數元素的個數點邊關系點邊關系連通圖連通圖樹樹點的次點的次邊邊特殊的圖特殊的圖簡簡單單圖圖多多重重圖圖部分樹部分樹 母圖和子圖母圖和子圖l l子子子子圖：圖：圖：圖：設設G1=（V1,E1），），G2=（V2,E2）如果如果V2 V1,E2 E1稱稱G2是是G1的子圖的子圖l l支撐子圖：支撐子圖：支撐子圖：支撐子圖：如果如果V2=V1,E2 E1稱稱G2是是G1的部分圖或支的部分圖或支撐子圖撐子圖l l導出子圖（導出子圖（導出子圖（導出子圖（G-vG-v）：圖圖G去掉點

16、去掉點v及及v的關聯(lián)邊的圖的關聯(lián)邊的圖.注意部分圖部分圖子圖子圖V4母圖母圖G1V1V2V3V5V6子圖子圖G2導出子圖導出子圖G-V6支撐子圖支撐子圖G2V2V1例：子圖例：子圖基礎圖基礎圖(母圖母圖)部分圖部分圖導出子圖導出子圖子圖子圖G=(V,E)邊邊e=u,v 關聯(lián)邊關聯(lián)邊 端點端點 重重重重合合合合環(huán)環(huán)自自自自回回回回路路路路多重邊多重邊平行邊平行邊平行邊平行邊多于多于1條邊條邊簡單圖簡單圖不含不含不含不含多重圖多重圖含含含含點的次點的次點的次點的次 01奇數奇數偶數偶數子圖子圖孤孤立立點點懸懸掛掛點點奇奇點點偶偶點點懸掛邊懸掛邊頂點數頂點數p邊數邊數q點邊關系點邊關系各種鏈的概念各

17、種鏈的概念子子圖圖支支撐撐子子圖圖導導出出子子圖圖二、二、圖的連通性圖的連通性（討論思路（討論思路）點邊關系點邊關系各種鏈、路的概念各種鏈、路的概念通路通路樹樹(6個等價定義個等價定義)連通圖連通圖 鏈鏈一個點、邊交替的連續(xù)序列一個點、邊交替的連續(xù)序列=vi1,ei1,vi2,ei2,vikl l簡單鏈：簡單鏈：簡單鏈：簡單鏈：若鏈中各邊均不同若鏈中各邊均不同l l初等鏈：初等鏈：初等鏈：初等鏈：若鏈中各點均不同若鏈中各點均不同l l圈圈圈圈:起點和終點重合的鏈，起點和終點重合的鏈，即閉合的鏈即閉合的鏈l l初等圈：初等圈：初等圈：初等圈：若圈中各點均不同若圈中各點均不同l l簡單圈：簡單圈：

18、簡單圈：簡單圈：若圈中各邊均不同若圈中各邊均不同 注意圈圈鏈鏈簡單鏈簡單鏈初等鏈初等鏈初等圈初等圈路：路：若鏈若鏈中每條弧的方向一致，則稱中每條弧的方向一致，則稱為路為路l l初等路：初等路：初等路：初等路：若路中各點均不同若路中各點均不同l l簡單路：簡單路：簡單路：簡單路：若路中各邊均不同若路中各邊均不同l l回路回路回路回路:起點和終點重合即閉合的路起點和終點重合即閉合的路l l初等回路：初等回路：初等回路：初等回路：若回路中各點均不同若回路中各點均不同l l簡單回路：簡單回路：簡單回路：簡單回路：若回路中各邊均不同若回路中各邊均不同v1v2v3v4e1e2e3e4e5e6注意v1,e1

19、,v2,e3,v3v1,e2,v2,e3,v3v1,e2,v2,e1,v1 鏈鏈路路 路（通路）路（通路）初等路初等路簡單路簡單路各邊不同各邊不同各點不同各點不同起點起點 終點終點=回路回路初等回路初等回路簡單回路簡單回路各邊不同各邊不同各點不同各點不同連通：連通：在圖中，若頂點在圖中，若頂點vi與與vj之間存在鏈，則稱之間存在鏈，則稱vi與與vj是是連通的連通的。l l規(guī)規(guī)規(guī)規(guī)定：定：定：定：v vi i與自身是連通的與自身是連通的l l連通圖：連通圖：連通圖：連通圖：在圖中，任意兩點間至少存在著一條鏈；在圖中，任意兩點間至少存在著一條鏈；否則，為不連通圖。否則，為不連通圖。點邊關系點邊關系

20、子子圖圖支支撐撐子子圖圖導導出出子子圖圖各種鏈的概念各種鏈的概念通路通路樹樹(6個等價定義個等價定義)連通圖連通圖 支撐樹支撐樹例例1 1：電話線網：電話線網已已知知有有六六個個城城市市，它它們們之之間間要要架架設設電電話話線線，要要求求任任意意兩兩個個城城市市均均可可以以互互相相通通話話，并并且且電電話話線的總長度最短。線的總長度最短。v1v2v3v4v5v6三、三、樹樹例例2 2：通訊網絡：通訊網絡例例3 3：紅樓夢紅樓夢中賈府人物之間的血統(tǒng)關系樹中賈府人物之間的血統(tǒng)關系樹賈演賈演賈源賈源賈代化賈代化賈代善賈代善賈放賈放賈敷賈敷賈珍賈珍賈蓉賈蓉賈赦賈赦賈政賈政賈璉賈璉賈寶玉賈寶玉賈環(huán)賈環(huán)賈

21、珠賈珠賈蘭賈蘭（寧國府）（寧國府）（榮國府）（榮國府）例例4 4 某工廠的組織機構如下圖所示某工廠的組織機構如下圖所示廠廠長長行行政政辦辦公公室室生生產產辦辦公公室室生產計劃科生產計劃科技術科技術科設計組設計組工藝組工藝組供銷科供銷科財務科財務科行政科行政科車間車間鑄造工段鑄造工段鍛壓工段鍛壓工段二二車間車間三車間三車間四車間四車間該廠的該廠的組織機構圖就是一個樹。組織機構圖就是一個樹。樹：樹：無圈的連通圖，記作無圈的連通圖，記作Tl l性質性質性質性質l樹是邊數最多的樹是邊數最多的無圈無圈連通圖。連通圖。在樹中任加一條邊，就會形成在樹中任加一條邊，就會形成圈。圈。l樹是邊數最少的連通圖。樹是

22、邊數最少的連通圖。n n 個個頂點的樹必有頂點的樹必有n-1 n-1 條邊條邊l在樹中任減一條邊，則不連通。在樹中任減一條邊，則不連通。d=1d=1葉子葉子葉子葉子d1d1分支點分支點分支點分支點l l 生成樹（支撐樹）：生成樹（支撐樹）：生成樹（支撐樹）：生成樹（支撐樹）：當連通圖當連通圖G=(V,E)的部分子圖為樹的部分子圖為樹T，則稱，則稱T為為G的的支撐樹，記作支撐樹，記作T=(V,E),其中其中E包含于包含于El 一個圖一個圖G 有生成樹的充要條件是有生成樹的充要條件是G 是連通圖。是連通圖。4231如何尋找如何尋找“支撐樹支撐樹”呢呢？網絡：網絡：規(guī)定了起點、終點和中間點的賦權圖規(guī)

23、定了起點、終點和中間點的賦權圖l l權：權：權：權：邊邊e或弧或弧a上賦有的實數上賦有的實數wlw-根據實際背景可賦予不同含義，如距離、時間、費用、根據實際背景可賦予不同含義，如距離、時間、費用、容量等。容量等。l l賦權圖：賦權圖：賦權圖：賦權圖：圖圖G連同邊或弧上的權總體。連同邊或弧上的權總體。l l有向網絡、有向網絡、有向網絡、有向網絡、四、四、網絡網絡4231221543權權wij(dij)無向網絡、無向網絡、無向網絡、無向網絡、混合網絡混合網絡混合網絡混合網絡所謂所謂網絡分析網絡分析:對網絡進行定性和定量分析，以對網絡進行定性和定量分析，以便為實現(xiàn)某種優(yōu)化目標而尋求最優(yōu)方案便為實現(xiàn)某

24、種優(yōu)化目標而尋求最優(yōu)方案v 最短路問題最短路問題v 最大流問題最大流問題v 最小費用最大流問題最小費用最大流問題v 最短樹問題最短樹問題v 中心與重心問題中心與重心問題v 網絡計劃問題網絡計劃問題 5-2.最最短短路路問問題題圖中兩個頂點之間有圖中兩個頂點之間有 條路徑條路徑最短路徑：最短路徑：最短路徑：最短路徑：是路徑中邊（弧）的權值總和最小的路徑是路徑中邊（?。┑臋嘀悼偤妥钚〉穆窂揭弧栴}的提法及應用背景一、問題的提法及應用背景多多多多一般提法為：設一般提法為：設 為連通圖，圖中各邊為連通圖，圖中各邊 有權有權 （表示表示 之間沒有邊），之間沒有邊），為圖中任意兩點，求一條路為圖中任意兩點

25、，求一條路 ，使它為從，使它為從 到到 的所有路中總權最小。即：的所有路中總權最小。即：應用背景：應用背景：應用背景：應用背景：某些整數規(guī)劃和動態(tài)規(guī)劃問題可以歸結為某些整數規(guī)劃和動態(tài)規(guī)劃問題可以歸結為求最短路的問題。求最短路的問題。l管道鋪設、線路安排、廠區(qū)布局、設備更新等。管道鋪設、線路安排、廠區(qū)布局、設備更新等。一、什么是最短路問題？在連通圖中，尋找一條從始點到終點的路，該路的權之和最小。二、最短路算法：狄克斯屈拉算法二、最短路算法：狄克斯屈拉算法D D氏標號法（氏標號法（氏標號法（氏標號法（DijkstraDijkstra，荷蘭人，荷蘭人，荷蘭人，荷蘭人）-雙標號法雙標號法雙標號法雙標號

26、法,1959,1959,1959,1959年年年年l基本思路：基本思路：基本思路：基本思路：如果如果v1v2v3v4是是v1v4的最短路的最短路徑，則徑，則v1v2v3一定是一定是v1v3的最短路徑。的最短路徑。v2v3v4一定是一定是v2v4的最短路徑。的最短路徑。從始點出發(fā)，從始點出發(fā)，逐步逐步順序地順序地向外探尋向外探尋，每向外延伸一步每向外延伸一步都要求是最短的。都要求是最短的。使用線性規(guī)劃的解法，但不能利用最短路問題的特點，使解法更有效。利用動態(tài)規(guī)劃的思路，即對于在始點到終點的總體最短路徑上的任意一點，從始點到該點的最短路在總體最短路徑上。根據上述第二點，可以用標號法求解。S247l

27、 選用標號的意義選用標號的意義：從始點到該節(jié)點的距離從始點到該節(jié)點的距離 標號標號 P P（固定標號或永久性標號）：固定標號或永久性標號）：從始從始點到該標號點的最短路權點到該標號點的最短路權。標號標號 T T（臨時性標號）：臨時性標號）：從始點到該標號從始點到該標號點的路權點的路權。l l 使用條件使用條件 網絡中網絡中所有的弧權所有的弧權均均 非負非負，即，即 。算法的每一步：算法的每一步：標號標號 T T 標號標號 P P計算步驟及例計算步驟及例：1234567252315317557（1 1）標號：）標號：首先給首先給1以以P標號，標號，P(P(1)0 0，給給其余所有點其余所有點T標

28、號，標號，T(vj)（j=2=2，3 3，7)7)(0)+（2）計算）計算T標號：標號：找與找與P標號標號的點相鄰的的點相鄰的T標號標號點，點，T(vj)=minT(vj)，P(vi)+wij（3）修改）修改T為為P：比較所有比較所有T標號標號點，點，T(vk)=minT(vj)，T(vk)T(vk)（4）重復）重復23步：步：全部點為全部點為P標號，標號，結束結束(2)2 25 53 39 94 4(3)8 8(4)7 7(7)+8 81414(8)(13)在在在在得得得得到到到到從從從從起起起起點點點點到到到到終終終終點點點點的的的的最最最最短短短短路路路路長長長長的的的的同同同同時時時時

29、，還還還還能得到什麼附加信息能得到什麼附加信息能得到什麼附加信息能得到什麼附加信息？能能得得到到從從（起起點點）到到各各點點的的最最短短路線和最短路長。路線和最短路長。521658289972212102527 5111212105756 679 910106 3 3大家知道，法求最短路只適應于權 0的情況，當網絡中出現(xiàn)負權時，此法失效，如：一。帶負權的最短路問題：求 到 的最短路。下面通過例子來說明帶負權的網絡的最短路求法：逐次逼近法：1給標號 （0）。畫弧。給 劃成彩線。劃第二個弧。給 標號（-3）。給 劃成彩線。劃第三個弧。給 標號（1）。給 劃成彩線。劃第四個弧。給 標號（2）。給 劃

30、成彩線。劃第五個弧。給 再次標號（0）。去掉 彩線。分別給 劃成彩線。劃第六個弧。分別給 標號（6）。給 劃成彩線。劃第七個弧。給 標號（10）。給 劃成彩線。到達 已經無負權，路程不可能再減少。給 標號（9）。最短路徑為：距離：10。Ford算法Dijkstra算法不適用于負權網絡具有負權的網絡，應當用Ford（福特，美國人）算法，逐次逼近算法逐次逼近算法又叫修正標號法修正標號法的特點是：不但最小T標號應當改為P標號，P標號也可以修改，修改后的P標號再次改為T表好。算法的基本思路是：算法的基本思路是：v1到到vj的最短路總是沿著該路的最短路總是沿著該路從從v1先到達某一點先到達某一點vi，然

31、后再沿邊（，然后再沿邊（vi，vj）達到達到vi，則，則v1到到vi的這條路必然也是的這條路必然也是v1到到vi的的最短路。若令最短路。若令P1j表示從表示從v1到到vj的最短路長，則的最短路長，則必有如下方程：必有如下方程：P1j=min（P1i+lij）采用迭代方法解上述方程。采用迭代方法解上述方程。（1）開始時令開始時令 P（1）1j=l1j（j=1，2，n），即以），即以v1 到到 vj 的直接距離的直接距離（經過一步）做初始解，若（經過一步）做初始解，若v1 與與 vj 間無邊，間無邊，則記則記 l1j=+。（2）從第二步起，使用從第二步起，使用迭代公式迭代公式 P（k）1j=min

32、（P（k-1）1i+lij）（k=2，3，）當進行到第當進行到第 t 步時，若出現(xiàn)步時，若出現(xiàn) P（t）1j=P（t-1）1j，則算法停止，則算法停止，P（t）1j（對一切（對一切 j）即為）即為v1 到各到各點的最短路長點的最短路長當進行到第當進行到第 n 步時，若仍有步時，若仍有 P（n）1j P（n-1）1j，（對一切，（對一切 j），則算法停止，），則算法停止，此時可知網絡中含有負回路。此時可知網絡中含有負回路。Ford算法算例情形二：賦權有向圖中存在具有負權的弧情形二：賦權有向圖中存在具有負權的弧v1v2v3v4v5v6v7v8例例:求求v1到圖中其他各點的最短路。到圖中其他各點的最

33、短路。6-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v4,1)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(

34、v2,-3)(v6,0)(v4,-5)(v6,0)(v6,6)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v1,-5)(v1,-7)(v1,-1)(v2,-3)(v4,-5)(v6,6)(v5,-4)(v7,-6)(v8,3)(v8,1)三、應用舉例三、應用舉例例例設備更新問題。某企業(yè)使用一臺設備，在每年年初都要決設備更新問題。某企業(yè)使用一臺設備，在每年年初都要決定是購置新設備還是繼續(xù)使用舊的。購置新設備要支付一定的定是購置新設備還是繼續(xù)使用舊的。購置新設備要支付一

35、定的購置費，使用舊設備則要支付維修費。制定一個五年內的設備購置費，使用舊設備則要支付維修費。制定一個五年內的設備更新計劃，使得總支付費用最少。更新計劃，使得總支付費用最少。已知該設備在各年年初的價格為：已知該設備在各年年初的價格為：第一年第二年第三年第四年第五年1111121213已知使用不同時間的設備維修費用為：已知使用不同時間的設備維修費用為：使用年數0112233445維修費用5681118設以設以vi(i=1,2,3,4,5)表示表示“第第i年初購進年初購進一臺新設備一臺新設備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這種狀態(tài)；以弧這種狀態(tài)；以弧(vi,vj)表示表示“第

36、第i年初購置年初購置的一臺設備一直使用到第的一臺設備一直使用到第j年初年初”這一方案，這一方案，以以wij表示這一方案所需購置費和維修費之和。表示這一方案所需購置費和維修費之和。這樣，可建立本例的網絡模型。于是，該問題就可這樣，可建立本例的網絡模型。于是，該問題就可歸結為從圖中找出一條從歸結為從圖中找出一條從v1到到v6的最短路問題。的最短路問題。從圖中可以得出兩條最短路：從圖中可以得出兩條最短路：v1v3v6;v1v4v6v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)v1v2v3v5v6v416302216594122413017

37、3123172318(0,0)(v1,16)(v1,22)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)(v1,41)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)(v1,41)(v3,53)(v4,53)例12/P264 設備更新問題某工廠使用一臺設備，每年年初工廠要作出決定：繼續(xù)

38、使用，購買新的？如果繼續(xù)使用舊的，要負維修費；若要購買一套新的，要負購買費。試確定一個5年計劃，使總支出最小若已知設備在各年的購買費，及不同機器役齡時的殘值與維修費，如表所示.項目第1年第2年第3年第4年第5年購買費1112131414機器役齡0-11-22-33-44-5維修費5681118殘值43210解：把這個問題化為最短路問題。用點 表示第i年初購進一臺新設備，虛設一個點 ，表示第5年底。邊 表示第i年購進的設備一直使用到第j年初（即第j-1年底）。邊 上的數字表示第i年初購進設備，一直使用到第j年初所需支付的購買費、維修的全部費用（可由表8-2計算得到）。這樣設備更新問題就變?yōu)椋呵髲?到 的最短路問題.給 劃成彩線。給 劃成彩線。給 劃成彩線。給 劃成彩線。給 劃成彩線。計算結果：最短路最短路路長為49。即：在第一年、第三年初各購買一臺新設備為最優(yōu)決策。這時5年的總費用為49。