圖與網(wǎng)絡分析到最短路問題學習教案

1、圖與網(wǎng)絡分析到最短路圖與網(wǎng)絡分析到最短路(dunl)問題問題第一頁，共68頁。第八章第八章圖與網(wǎng)絡分析圖與網(wǎng)絡分析 圖的基本概念與模型 樹圖和圖的最小部分樹 最短路問題(wnt) 網(wǎng)絡最大流問題(wnt) 最小費用最大流問題(wnt) 第1頁/共68頁第二頁，共68頁。者公路交通網(wǎng)絡的合理布局等問題，都可以應用圖論的方法，簡便、快捷地加以解決。引引 言言第2頁/共68頁第三頁，共68頁。引例引例(yn l)1(yn l)1歐拉將這個問題抽象成一筆畫問題。即能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可

2、能將它一筆畫出，這就是歐拉將這個問題抽象成一筆畫問題。即能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是(jish)(jish)古典圖論中的第一個著名問題。古典圖論中的第一個著名問題。第3頁/共68頁第四頁，共68頁。引例引例(yn l)2(yn l)2左圖是我國北京左圖是我國北京(bijn)、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。、上海、重慶等十四個城市之間的鐵路交通圖，這

3、里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。連云港連云港武漢武漢南京南京徐州徐州上海上海北京北京塘沽塘沽青島青島濟南濟南天津天津鄭州鄭州第4頁/共68頁第五頁，共68頁。引例引例(yn l)3(yn l)3v3v1v2v4v6v5第5頁/共68頁第六頁，共68頁。點：研究點：研究(ynji)對象（車站、國家、球隊）；對象（車站、國家、球隊）；點間連線：對象之間的特定關(guān)系（陸地間有橋、鐵路線、點間連線：對象之間的特定關(guān)系（陸地間有橋、鐵路線、兩球隊兩球隊(qi du)(qi du)比賽及結(jié)果比賽及結(jié)果) )。對稱關(guān)系：對稱關(guān)系：橋、道路

4、、邊界；用不帶箭頭的連線表橋、道路、邊界；用不帶箭頭的連線表示，示，稱為邊。稱為邊。非對稱關(guān)系：非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示，甲隊勝乙隊，用帶箭頭的連線表示，稱為弧。稱為弧。圖：圖：點及邊（或?。┙M成。點及邊（或弧）組成。注意：注意：一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上不同。一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上不同。第6頁/共68頁第七頁，共68頁。對對稱稱關(guān)關(guān)系系非非對對稱稱關(guān)

5、關(guān)系系網(wǎng)絡圖：給圖中的點和邊賦予具體的含義網(wǎng)絡圖：給圖中的點和邊賦予具體的含義(hny)和權(quán)數(shù)，如距離，和權(quán)數(shù)，如距離，費用，容量等，記作費用，容量等，記作N.第7頁/共68頁第八頁，共68頁。圖的相關(guān)圖的相關(guān)(xinggun)概念概念若邊若邊eij=vi,vjEeij=vi,vjE，稱，稱vivi，vjvj是是eijeij的端點的端點(dun (dun din)din)，也稱，也稱vivi，vjvj是相鄰的。稱是相鄰的。稱eijeij是點是點vivi（及點（及點vjvj）的關(guān)聯(lián)邊。的關(guān)聯(lián)邊。若兩條邊有一個公共的端點若兩條邊有一個公共的端點(dun din)(dun din)，則稱這兩條邊，則

6、稱這兩條邊相鄰。相鄰。v viv vjev vi，v vj相鄰相鄰 e與與v vi，v vj關(guān)聯(lián)關(guān)聯(lián)v vie1v vjv vke2點與邊關(guān)聯(lián)點與邊關(guān)聯(lián)點與點相鄰點與點相鄰邊與邊相鄰邊與邊相鄰第8頁/共68頁第九頁，共68頁。若某條邊兩個端點若某條邊兩個端點(dundin)相同，稱這條邊為環(huán)。相同，稱這條邊為環(huán)。若兩點之間有多于一條的邊，稱這些邊為多重邊。若兩點之間有多于一條的邊，稱這些邊為多重邊。無環(huán)、無多重邊的無環(huán)、無多重邊的圖稱為圖稱為(chnwi)簡單圖。簡單圖。無環(huán)、但允許無環(huán)、但允許(ynx)(ynx)有多重邊有多重邊的圖稱為多重圖。的圖稱為多重圖。v1e1e2e3v2v3e5e4

7、v4v5注：注：無特別聲明我們今后討論的圖都是簡單圖無特別聲明我們今后討論的圖都是簡單圖圖的相關(guān)概念圖的相關(guān)概念第9頁/共68頁第十頁，共68頁。圖圖G中以點中以點v為端點的邊的數(shù)目為端點的邊的數(shù)目(shm)，稱為，稱為v在在G中中的次的次(度），度），記為記為d（v）。）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次為1 的點為懸掛(xungu)點，懸掛(xungu)點的關(guān)聯(lián)邊稱為懸掛(xungu)邊，次為零的點稱為孤立點。v1e1e2e3v2v3e5e4v4v5次為奇數(shù)次為奇數(shù)(jsh)的點稱為奇點，否則稱為偶點。的點稱為奇點，否則稱為偶點。圖的相關(guān)概念圖的相關(guān)概念第

8、10頁/共68頁第十一頁，共68頁。給定給定( (i dni dn) )圖圖G=G=（V V，E E），若圖），若圖G=G=（VV，EE），其中），其中VVV V，EE E E ，則稱，則稱GG是是G G的子圖。的子圖。給定圖給定圖G=G=（V V，E E），若圖），若圖G=G=（V V，EE），其中），其中EEE E，則稱則稱GG是是G G的一個支撐的一個支撐(zh chng)(zh chng)子圖（部分圖）。子圖（部分圖）。點全部點全部(qunb)保留保留（a）（b）子圖子圖（c）部分圖部分圖子圖與部分圖（支撐子圖）子圖與部分圖（支撐子圖）第11頁/共68頁第十二頁，共68頁。圖的連通性圖

9、的連通性鏈：設(shè)圖鏈：設(shè)圖G=G=（V V，E E）中有一個點、邊交替）中有一個點、邊交替(jiot)(jiot)序列序列 v1 ,e1,v2,vn- v1 ,e1,v2,vn-1,en-1 ,vn1,en-1 ,vn，若，若ei=(vi,vi+1)ei=(vi,vi+1)，即這，即這(n-1)(n-1)條邊把條邊把n n個頂點串連起來，我們稱個頂點串連起來，我們稱這個交替這個交替(jiot)(jiot)序列為圖序列為圖G G中的一中的一條鏈，而稱點條鏈，而稱點v1,vnv1,vn為該鏈的兩個端點。為該鏈的兩個端點。對于簡單圖鏈也可以僅用點的序列來表示。對于簡單圖鏈也可以僅用點的序列來表示。如果

10、如果(rgu)一條鏈的兩個端點是同一個點，則稱它為閉鏈或圈；一條鏈的兩個端點是同一個點，則稱它為閉鏈或圈；如果如果(rgu)一條鏈的各邊均不相同，則稱此鏈為簡單鏈；一條鏈的各邊均不相同，則稱此鏈為簡單鏈；更若一條鏈的各點、各邊均不相同，則稱該鏈為初等鏈。更若一條鏈的各點、各邊均不相同，則稱該鏈為初等鏈。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9簡單鏈簡單鏈： 1=（v2，v1，v3，v6，v4，v3，v5）初等鏈初等鏈： 2=（v2，v1，v3，v5）第12頁/共68頁第十三頁，共68頁。圖的連通性圖的連通性最短鏈最短鏈: :網(wǎng)絡中鏈上權(quán)值的和稱為鏈的長度，以點網(wǎng)絡中

11、鏈上權(quán)值的和稱為鏈的長度，以點v1,vnv1,vn為端點的諸鏈中長度最短的鏈稱為這兩為端點的諸鏈中長度最短的鏈稱為這兩點的最短鏈。點的最短鏈。連通連通(lintng)(lintng)圖：如果圖圖：如果圖G=G=（V V，E E）中的任）中的任意兩點都是其某一條鏈的兩個端點，則稱圖意兩點都是其某一條鏈的兩個端點，則稱圖G G是連通是連通(lintng)(lintng)圖，否則，稱圖圖，否則，稱圖G G是不連是不連通通(lintng)(lintng)的。的。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9為不連通圖，有兩個為不連通圖，有兩個(lin)連通分圖組成連通分圖組成第1

12、3頁/共68頁第十四頁，共68頁。圖的矩陣圖的矩陣(jzhn)表示表示圖的矩陣圖的矩陣(jzhn)表示主要方法有：權(quán)矩陣表示主要方法有：權(quán)矩陣(jzhn)、鄰接矩陣鄰接矩陣(jzhn)。權(quán)矩陣權(quán)矩陣(j zhn)(j zhn)網(wǎng)絡圖網(wǎng)絡圖N=N=（V V，E E），邊），邊vivi，vjvj的權(quán)為的權(quán)為wij wij ，構(gòu)造矩陣，構(gòu)造矩陣(j zhn)(j zhn)其它其中Ev,va,)(aAjiijijijnnw稱矩陣稱矩陣A A為網(wǎng)絡為網(wǎng)絡N N的權(quán)矩陣。的權(quán)矩陣。第14頁/共68頁第十五頁，共68頁。v4v5v2v1v3234567894其權(quán)矩陣其權(quán)矩陣(jzhn)為：為：12345v0

13、9247v90340vA 23085v44806v7056012345vvvvv注：當注：當G G為無向圖時，權(quán)矩陣為無向圖時，權(quán)矩陣(j zhn)(j zhn)為對稱矩陣為對稱矩陣(j (j zhn)zhn)。第15頁/共68頁第十六頁，共68頁。圖圖G=G=（V V，E E），），p=np=n，構(gòu)造，構(gòu)造(guzo)(guzo)矩陣矩陣其它其中0Ev,v1a,)(aAjiijijnn稱矩陣稱矩陣(j zhn)A(j zhn)A為為G G的鄰接矩陣的鄰接矩陣(j (j zhn)zhn)。鄰接矩陣鄰接矩陣？vi與與vj不相鄰不相鄰(xin ln)圖的矩陣表示圖的矩陣表示第16頁/共68頁第十七

14、頁，共68頁。其鄰接矩陣為：其鄰接矩陣為： 0100000100100010110011010Av4v5v2v1v3注：當注：當G G為無向圖時，鄰接矩陣為對稱為無向圖時，鄰接矩陣為對稱(duchn)(duchn)矩陣。矩陣。第17頁/共68頁第十八頁，共68頁。 思考：有甲、乙、丙、丁、戊、己六名運動員報名參加思考：有甲、乙、丙、丁、戊、己六名運動員報名參加(cnji)A(cnji)A、B B、C C、D D、E E、F F六個項目的比賽，下表中打的六個項目的比賽，下表中打的是個運動員報名參加是個運動員報名參加(cnji)(cnji)比賽的項目，問六個項目的比賽的項目，問六個項目的比賽順序應

15、如何安排？做到每名運動員都不連續(xù)地參加比賽順序應如何安排？做到每名運動員都不連續(xù)地參加(cnji)(cnji)兩項比賽。兩項比賽。ABCDEF分析：點表示項目，邊表示兩個分析：點表示項目，邊表示兩個(lin)項目有同一名運動員參加項目有同一名運動員參加目的：在圖中找出點序列，目的：在圖中找出點序列，使得依次排列的兩個點不使得依次排列的兩個點不相鄰，就找到了每名運動相鄰，就找到了每名運動員不連續(xù)員不連續(xù)(linx)參加兩參加兩項比賽的安排方案項比賽的安排方案A、C、B、F、E、D( (不唯一不唯一) )第18頁/共68頁第十九頁，共68頁。第八章第八章圖與網(wǎng)絡分析圖與網(wǎng)絡分析 圖的基本概念與模型

16、圖的基本概念與模型(mxng)(mxng) 樹圖和圖的最小部分樹樹圖和圖的最小部分樹 最短路問題最短路問題 網(wǎng)絡最大流問題網(wǎng)絡最大流問題 最小費用最大流問題最小費用最大流問題 第19頁/共68頁第二十頁，共68頁。第六章第六章圖與網(wǎng)絡分析圖與網(wǎng)絡分析 圖的基本概念與模型圖的基本概念與模型(mxng)(mxng) 樹圖和圖的最小部分樹樹圖和圖的最小部分樹 最短路問題最短路問題 網(wǎng)絡最大流問題網(wǎng)絡最大流問題 最小費用最大流問題最小費用最大流問題 第20頁/共68頁第二十一頁，共68頁。7 7個村莊要在他們之間架設(shè)電話線，要求個村莊要在他們之間架設(shè)電話線，要求(yoqi)(yoqi)任何兩個村莊都可

17、以互相通電話任何兩個村莊都可以互相通電話( (允許中轉(zhuǎn)允許中轉(zhuǎn)) )，并且電話線根數(shù)最少？，并且電話線根數(shù)最少？引例引例(yn l)(yn l)村莊村莊(cnzhung)1村莊村莊4村莊村莊3村莊村莊6村莊村莊2村莊村莊5村莊村莊7分析分析：用七個點代表村莊，如果在某兩個村莊之間架設(shè)電話線，則相：用七個點代表村莊，如果在某兩個村莊之間架設(shè)電話線，則相應的在兩點之間連一條邊，這樣電話線網(wǎng)就可以用一個圖來表示，并應的在兩點之間連一條邊，這樣電話線網(wǎng)就可以用一個圖來表示，并且滿足如下要求：且滿足如下要求：連通圖連通圖圖中有圈的話，從圈中任去掉一條邊，余下的圖仍連通圖中有圈的話，從圈中任去掉一條邊，余

18、下的圖仍連通第21頁/共68頁第二十二頁，共68頁。樹樹村莊村莊(cnzhung)1村莊村莊(cnzhung)4村莊村莊(cnzhung)3村莊村莊6村莊村莊2村莊村莊5村莊村莊7如果如果G=G=（V V，E E）是一個無圈的連通圖，則稱）是一個無圈的連通圖，則稱G G為為樹樹。 樹中必存在次為樹中必存在次為1 1的點（懸掛點）的點（懸掛點）樹中任兩點必有一條鏈且僅有一條鏈；樹中任兩點必有一條鏈且僅有一條鏈；在樹的兩個不相鄰的點之間添加一條邊，就得到一個圈；在樹的兩個不相鄰的點之間添加一條邊，就得到一個圈； 反之，去掉樹的任一條邊，樹就成為不連通圖；反之，去掉樹的任一條邊，樹就成為不連通圖；n

19、 n個頂點的樹有（個頂點的樹有（n-1n-1）條邊。）條邊。樹是最脆弱的連通圖！樹是最脆弱的連通圖！第22頁/共68頁第二十三頁，共68頁。145241575237圖的部分圖的部分(b fen)(b fen)樹樹（支撐樹）（支撐樹）如果如果(rgu)(rgu)圖圖G=G=（V V，E E）的部分圖）的部分圖G=G=（V V，EE）是樹，）是樹， 則稱則稱GG是是G G的部分樹（或支撐樹）。的部分樹（或支撐樹）。村莊村莊(cnzhung)1村莊村莊4村莊村莊3村莊村莊6村莊村莊2村莊村莊5村莊村莊7部分樹上各樹枝上權(quán)值的和稱為它的長度，其中長部分樹上各樹枝上權(quán)值的和稱為它的長度，其中長度最短的部

20、分樹，稱其為該圖的度最短的部分樹，稱其為該圖的最小部分樹最小部分樹（最小支撐（最小支撐樹）。樹）。點保留點保留邊可去邊可去仍是樹仍是樹不唯一不唯一思考：如何鋪設(shè)電話線，使得思考：如何鋪設(shè)電話線，使得電話線長度最少？電話線長度最少？第23頁/共68頁第二十四頁，共68頁。ijkml最小部分最小部分(b fen)(b fen)樹的求樹的求法法定理定理(dngl)(dngl)：圖中任一個點：圖中任一個點i i，若，若j j是與相鄰點中距離最近的，是與相鄰點中距離最近的， 則邊則邊i,ji,j一定必含在該圖的最小部分樹內(nèi)。一定必含在該圖的最小部分樹內(nèi)。推論：推論：把圖的所有點分成把圖的所有點分成 和和

21、 兩個集合，則兩集合之兩個集合，則兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。間連線的最短邊一定包含在最小部分樹內(nèi)。VVVV避圈法破圈法第24頁/共68頁第二十五頁，共68頁。227541435175ABCDESTVV算法的步驟：算法的步驟： 1 1、在給定的賦權(quán)的連通圖上任選一點、在給定的賦權(quán)的連通圖上任選一點vi,其余點在其余點在中中。 2 2、從、從 與與 的連線中找出權(quán)數(shù)最小的邊的連線中找出權(quán)數(shù)最小的邊 vi, vj ，這條邊一定包含在最小部分樹內(nèi)，做以標記。，這條邊一定包含在最小部分樹內(nèi)，做以標記。 3 3、令、令 vj ， ； 4 4、重復、重復2 2、3 3兩步，直至所有點都包

22、含在兩步，直至所有點都包含在中為止。中為止。VVVVVVVvjVV避圈算法避圈算法(sunf)S第25頁/共68頁第二十六頁，共68頁。77ABCDEST2254143515破圈算法破圈算法(sunf)第26頁/共68頁第二十七頁，共68頁。第六章第六章圖與網(wǎng)絡分析圖與網(wǎng)絡分析 圖的基本概念與模型圖的基本概念與模型(mxng)(mxng) 樹圖和圖的最小部分樹樹圖和圖的最小部分樹 最短路問題最短路問題 網(wǎng)絡最大流問題網(wǎng)絡最大流問題 最小費用最大流問題最小費用最大流問題 第27頁/共68頁第二十八頁，共68頁。第八章第八章圖與網(wǎng)絡分析圖與網(wǎng)絡分析 圖的基本概念與模型圖的基本概念與模型 樹圖和圖的

23、最小部分樹圖和圖的最小部分(b fen)(b fen)樹樹 最短路問題最短路問題 網(wǎng)絡最大流問題網(wǎng)絡最大流問題 最小費用最大流問題最小費用最大流問題 第28頁/共68頁第二十九頁，共68頁。第29頁/共68頁第三十頁，共68頁。第30頁/共68頁第三十一頁，共68頁。),(jiijvvaAivV 第31頁/共68頁第三十二頁，共68頁。12534372第32頁/共68頁第三十三頁，共68頁。最短路問題最短路問題(wnt)引例引例下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線所需的費用?，F(xiàn)在某人要從所需的費用?，F(xiàn)在某人要從v1v1出發(fā)，通過這個出發(fā)，

24、通過這個(zh (zh ge)ge)交通網(wǎng)到交通網(wǎng)到v8v8去，求使總費用最小的旅行路線。去，求使總費用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363第33頁/共68頁第三十四頁，共68頁。從從v1v1到到v8v8：P1=P1=（v1v1，v2v2，v5v5，v8v8） 費用費用(fi yong) 6+1+6=13(fi yong) 6+1+6=13P2=P2=（v1v1，v3v3，v4v4， v6 v6， v7 v7， v8 v8） 費用費用(fi yong) 3+2+10+2+4=21(fi yong) 3+2+10+2+4=21P3= P3= 從

25、從v1到到v8的旅行路線的旅行路線 從從v1到到v8的路。的路。旅行路線總費用旅行路線總費用 路上所有弧權(quán)之和路上所有弧權(quán)之和。最短路問題中，不考慮最短路問題中，不考慮(kol)有向環(huán)、并行弧。有向環(huán)、并行弧。v2v523464v3v1v4v6121061210v8v9v72363第34頁/共68頁第三十五頁，共68頁。設(shè)圖設(shè)圖D=D=（V V，A A）是一有向網(wǎng)絡）是一有向網(wǎng)絡(wnglu)(wnglu)paijijawpw)()( v2v523464v3v1V4v6121061210v8v9v72363第35頁/共68頁第三十六頁，共68頁。Pp 0)()(0pwMinpwPp)(),(0

26、pwvvdts注意：注意：在有向網(wǎng)絡中在有向網(wǎng)絡中, ,一般一般),(),(sttsvvdvvd最短路最短路(dunl)及一點到另一點及一點到另一點的距離的距離最短路問題最短路問題是重要的最優(yōu)化問題之一，可以直接應用于解是重要的最優(yōu)化問題之一，可以直接應用于解決生產(chǎn)實際的許多問題決生產(chǎn)實際的許多問題:管道鋪設(shè)、線路安排、廠區(qū)布局等。管道鋪設(shè)、線路安排、廠區(qū)布局等。而且經(jīng)常被作為一個基本工具來解決其他的優(yōu)化問題。而且經(jīng)常被作為一個基本工具來解決其他的優(yōu)化問題。第36頁/共68頁第三十七頁，共68頁。第37頁/共68頁第三十八頁，共68頁。第38頁/共68頁第三十九頁，共68頁。求解最短路問題求解

27、最短路問題(wnt)的的Dijkstra算算法法條件條件(tiojin)：當所有：當所有wij0時，用來求給定點時，用來求給定點vs到任一到任一個點個點vj最短路的公認的最好方法。最短路的公認的最好方法。事實事實(shsh)：如果：如果P是是D中從中從vs到到vj的最短路，的最短路，vi是是P中的一中的一基解基解個點，那么，從個點，那么，從vs沿沿P到到vi的路的路是從是從vs到到vi的最基解的最基解短路。短路。 Dijkstra算法是算法是Dijkstra在在19591959年提出的，可用于求解年提出的，可用于求解指定兩點間的最短路問題指定兩點間的最短路問題，或從指定點到其余各點的最短路問題

28、。由于其以標號為主要特征，又稱為，或從指定點到其余各點的最短路問題。由于其以標號為主要特征，又稱為標號法標號法。v1v2v3v4v5最短路的子路是最短路最短路的子路是最短路第39頁/共68頁第四十頁，共68頁。 從始點從始點vsvs出發(fā)，逐步順序地向外探尋出發(fā)，逐步順序地向外探尋(tn (tn xn)xn)，每向外延伸一步都要求是最短的。執(zhí)行過，每向外延伸一步都要求是最短的。執(zhí)行過程中，與每個點對應，記錄下兩個數(shù)程中，與每個點對應，記錄下兩個數(shù)( (稱為這個點稱為這個點的標號的標號) ) 1. 1.標號標號 P P（固定（固定(gdng)(gdng)標號或永久性標號）標號或永久性標號）從始點從

29、始點vsvs到該標號點到該標號點vjvj的最短路權(quán)的最短路權(quán)P P (vj) (vj) 。 2. 2.標號標號 T T（臨時性標號）（臨時性標號）從始點從始點vsvs到該標號點到該標號點vjvj的最短路權(quán)上界的最短路權(quán)上界T T (vj) (vj) 。 j ,P (vj) j,T (vj)該方法的每一步就是去修改該方法的每一步就是去修改T T標號，并且把某一個具標號，并且把某一個具T T標號的點標號的點改變?yōu)榫哂懈淖優(yōu)榫哂蠵標號的點，從而使標號的點，從而使D D中具中具P標號的頂點數(shù)多一個，標號的頂點數(shù)多一個，至多經(jīng)過至多經(jīng)過n-1步，就可以求出始點步，就可以求出始點vs到各點的最短路。到各點

30、的最短路。前點標號前點標號 j 表示始點表示始點vs到到vj的最短路上的最短路上vj的的前一點前一點。第40頁/共68頁第四十一頁，共68頁。 第二步：第二步：考慮滿足條件考慮滿足條件 的所有點；的所有點； vi具有具有P P 標號標號; ;vj j具有具有T T 標號標號; ; 修改修改vj的的T T標號為標號為 ，并將結(jié)果仍記為并將結(jié)果仍記為T T( (v vj j) )ijijjwvPvTvT)(),(min)( ,)ijv vA第一步：第一步：始點標上固定標號始點標上固定標號 , ,其余各其余各點標臨時性標號點標臨時性標號T T( (vj j)=)= , j, j 1; 1; ()0s

31、P v第三步：第三步：若網(wǎng)絡圖中已無若網(wǎng)絡圖中已無T T標號點，停止計算。標號點，停止計算。否則否則, , 令令 ，s s為為T T標號點集標號點集, , 然后然后將將 的的T T 標號改成標號改成P P 標號標號 ，轉(zhuǎn)入第二步。，轉(zhuǎn)入第二步。0jv第41頁/共68頁第四十二頁，共68頁。v1,6圖上標號圖上標號(bioho)(bioho)法法v5v223464v3v1v4121061210v8v9v72363v60,0M,M, v1,3M,M,M,v1,1v1,1永久永久(yngji)標號標號永久永久(yngji)標號標號臨時標號臨時標號v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總

32、費用最小的旅行路線第42頁/共68頁第四十三頁，共68頁。v1,6圖上標號圖上標號(bioho)(bioho)法法v5v223464v3v1v4121061210v8v9v72363v60,0M,M,v1,3M,M,M,0,0v1,1v4,11v1,3永久永久(yngji)標號標號臨時臨時(lnsh)標號標號v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總費用最小的旅行路線第43頁/共68頁第四十四頁，共68頁。v5v223464v3v1v4121061210v8v9v72363v60,0M,v1,1M,M,M,1,3圖上標號圖上標號(bioho)(bioho)法法v4,11v1,3v1

33、,6v3,5v3,5永久永久(yngji)標號標號臨時臨時(lnsh)標號標號v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總費用最小的旅行路線第44頁/共68頁第四十五頁，共68頁。v5v223464v3v1v4121061210v8v9v72363v60,0M,v4,11v1,1M,M,M,v1,3圖上標號圖上標號(bioho)(bioho)法法v3,5v2,6v2,6永久永久(yngji)標號標號臨時臨時(lnsh)標號標號v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總費用最小的旅行路線第45頁/共68頁第四十六頁，共68頁。v5v223464v3v1v4121061210

34、v8v9v72363v60,0M,v4,11v1,1M,M,v1,3v5,12v5,9v5,9圖上標號圖上標號(bioho)(bioho)法法v3,5v2,6永久永久(yngji)標號標號臨時臨時(lnsh)標號標號v5,10v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總費用最小的旅行路線第46頁/共68頁第四十七頁，共68頁。v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,v5,12v1,3v5,9v5,12v3,5v2,6圖上標號圖上標號(bioho)(bioho)法法永久永久(yngji)標號標號臨時臨時(lnsh)標號標號v5

35、,10v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總費用最小的旅行路線第47頁/共68頁第四十八頁，共68頁。v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,v1,3v5,12v3,5v2,6圖上標號圖上標號(bioho)(bioho)法法v5,9永久永久(yngji)標號標號臨時臨時(lnsh)標號標號標號結(jié)束標號結(jié)束反向追反向追蹤蹤v1出發(fā)到出發(fā)到v8去，使總費用最小的旅行路線去，使總費用最小的旅行路線第48頁/共68頁第四十九頁，共68頁。 第二步：第二步：考慮滿足條件考慮滿足條件 的所有點；的所有點； vi具有具有P P 標號

36、標號; ;vj j具有具有T T 標號標號; ; 修改修改vj的的T T標號為標號為 ，并將結(jié)果仍記為并將結(jié)果仍記為T T( (v vj j) )ijijjwvPvTvT)(),(min)( ,)ijv vA第一步：第一步：始點標上固定標號始點標上固定標號 , ,其余各其余各點標臨時性標號點標臨時性標號T T( (vj j)=)= , j, j 1; 1; ()0sP v第三步：第三步：若網(wǎng)絡圖中已無若網(wǎng)絡圖中已無T T標號點，停止計算。標號點，停止計算。否則否則, , 令令 ，s s為為T T標號點集標號點集, , 然后然后將將 的的T T 標號改成標號改成P P 標號標號 ，轉(zhuǎn)入第二步。，

37、轉(zhuǎn)入第二步。0jv第49頁/共68頁第五十頁，共68頁。例例 求如下求如下(rxi)(rxi)交通網(wǎng)絡中交通網(wǎng)絡中v1 v1 到各點間最短路路到各點間最短路路長。長。DijkstraDijkstra算法算法(sun f)(sun f)（標（標號法）算例號法）算例31025v4v1v2v5v312262448混合混合(hnh)圖圖第50頁/共68頁第五十一頁，共68頁。5727461263202657710v3v1v2v4v5v6v7練習練習(linx)(linx)：求如下無向網(wǎng)絡中：求如下無向網(wǎng)絡中v1v1到到v7v7的最的最短鏈短鏈Dijkstra算法算法(sunf)求最短鏈求最短鏈第51頁

38、/共68頁第五十二頁，共68頁。無向無向(w xin(w xin) )網(wǎng)絡網(wǎng)絡: :負權(quán)弧時負權(quán)弧時。wijvivjwijwijvjvi無向無向(wxin)網(wǎng)絡中，最短路網(wǎng)絡中，最短路最短鏈。最短鏈。多個多個(du)點對之間最短路？點對之間最短路？v1v2v312-3Dijkstra算法失效算法失效Dijkstra算法注意的問題算法注意的問題逐步逼近算法逐步逼近算法路矩陣算法路矩陣算法第52頁/共68頁第五十三頁，共68頁。第53頁/共68頁第五十四頁，共68頁。)1(11)(1ijkinikjwPMinP表示點表示點v1與與vj之間最多插入之間最多插入k個轉(zhuǎn)接個轉(zhuǎn)接(zhunji)點的最短路

39、點的最短路第54頁/共68頁第五十五頁，共68頁。用于計算用于計算(j sun)(j sun)指定點指定點v1v1到其余各點到其余各點的最短路的最短路)1(11)(1ijkinikjwPMinPj=1,2,n. k=1,2,tn.2.2.計算計算jjwP1)0(1 j=1,2,n.1.1.令令(k)(1)11kjjPP其元素既是其元素既是v1 1到到vj j的最短路長。的最短路長。3.3.當出現(xiàn)當出現(xiàn)時，時，基本基本(jb(jbn)n)表表第55頁/共68頁第五十六頁，共68頁。例例 計算從點計算從點v1v1到所有其它到所有其它(qt)(qt)頂點的最短路頂點的最短路解：初始條件為解：初始條件

40、為 0000111213140,2,5,3PPPP 以后以后(yhu)(yhu)按照公式按照公式 進行迭代進行迭代。 直到得到直到得到(d do) (d do) ，迭代停止。，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP) 1(1)(1tjtjPP第56頁/共68頁第五十七頁，共68頁。v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1Wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-2

41、0420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用下標利用下標(xibio)追蹤路徑追蹤路徑到到從從)1(11)(1ijkinikjwPMinP例例2：求：求v1到各點最短路到各點最短路(dunl)第57頁/共68頁第五十八頁，共68頁。)1(11)(1ijkinikjwPMinP表示點表示點v1與與vj之間最多插入之間最多插入k個轉(zhuǎn)接個轉(zhuǎn)接(zh

42、unji)點的最短路點的最短路第58頁/共68頁第五十九頁，共68頁。第59頁/共68頁第六十頁，共68頁。已知有已知有7 7個村子，相互間道路的距離如下圖示。擬合建一所小學，已知個村子，相互間道路的距離如下圖示。擬合建一所小學，已知A A處有小學生處有小學生3030人，人，B B處處4040人，人，C C處處2525人，人，D D處處2020人，人，E E處處5050人，人，F(xiàn) F處處6060人，人， G G處處6060人人, ,問小學應建在哪一個問小學應建在哪一個(y (y )村子，使學生上學最方便（原則所有人走的總路程最短；盡可能公平。）。村子，使學生上學最方便（原則所有人走的總路程最短

43、；盡可能公平。）。最短路最短路(dunl)(dunl)問題算例問題算例1(1(選址問題選址問題) )AGFECB522747163D26第60頁/共68頁第六十一頁，共68頁。(0)052502 72074D270 6 276 0 1 342 1 0 63 6 0 AGFECB522747163D26得到(d do)權(quán)矩陣為(1)052 7 12 65072 7 4 102706 5 4 10D7260 3 2 812 753 0 1 36442 1 0 410 108 3 4 0(1)(0)(0)irjminijrddd(1)(0)DDij中的d 為中的第i行第j列對應相加，取最小的第61頁

44、/共68頁第六十二頁，共68頁。(2)(1)DDij中的a 為中的第i行第j列對應相加，取最小的得到(d do)權(quán)矩陣為(2)05 2 7 7 6 1050 72 5 4 82 7 06 5 4 8D72 60 3 2 675 53 0 1 364 42 1 0 410 8 86 3 4 0(2)(1)(1)irjminijrddd(1)052 7 12 65072 7 4 102706 5 4 10D7260 3 2 812 753 0 1 36442 1 0 410 108 3 4 0(1)(0)DDij中的d 為中的第i行第j列對應相加，取最小的第62頁/共68頁第六十三頁，共68頁。得

45、到(d do)權(quán)矩陣為(2)05 2 7 7 6 1050 72 5 4 82 7 06 5 4 8D72 60 3 2 675 53 0 1 364 42 1 0 410 8 86 3 4 0(3)(2)(2)irjminijrddd(3)05 2 7 7 6 1050 72 5 4 82 7 06 5 4 8D72 60 3 2 675 53 0 1 364 42 1 0 410 8 86 3 4 0(k)(k-1)DDij中的a 為中的第i行第j列對應相加，取最小的(k)(k-1)(k-1)irjmin1221ijrkddd 一般地，表示經(jīng)過個， 個，個中間點得到的最短距離第63頁/共68頁第六十四頁，共68頁。 12413651361365721324652462465731236436536573421463465465756315462563564631632657756317564275637564756052776105072 548270654 8D72602367553103644201410886430A A處處3030人，人，B B處處4040人，人，C C處處2525人，人，D D處處2020人，人，E E處處5050人，人，