圖與網(wǎng)絡(luò)分析到最短路問題

圖與網(wǎng)絡(luò)分析到最短路問題第1頁，共87頁，2023年，2月20日，星期四第八章

圖與網(wǎng)絡(luò)分析

圖的基本概念與模型

樹圖和圖的最小部分樹

最短路問題

網(wǎng)絡(luò)最大流問題

最小費用最大流問題

第2頁，共87頁，2023年，2月20日，星期四

圖論是應(yīng)用非常廣泛的運籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運輸，經(jīng)濟管理，電子計算機等各項領(lǐng)域。對于科學(xué)研究，市場和社會生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題，都可以應(yīng)用圖論的方法，簡便、快捷地加以解決。引言第3頁，共87頁，2023年，2月20日，星期四

1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問題。即一個漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。如圖1所示。引例1歐拉將這個問題抽象成一筆畫問題。即能否從某一點開始不重復(fù)地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個著名問題。第4頁，共87頁，2023年，2月20日，星期四

在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點和線來畫出各式各樣的示意圖。引例2左圖是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。連云港武漢南京徐州上海北京塘沽青島濟南天津鄭州第5頁，共87頁，2023年，2月20日，星期四

有六支球隊進行足球比賽，我們分別用點v1…v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊戰(zhàn)勝v2隊，v2隊戰(zhàn)勝v3隊，v3隊戰(zhàn)勝v5隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出來。引例3v3v1v2v4v6v5第6頁，共87頁，2023年，2月20日，星期四圖的基本概念與模型點：研究對象（車站、國家、球隊）；點間連線：對象之間的特定關(guān)系（陸地間有橋、鐵路線、兩球隊比賽及結(jié)果)。對稱關(guān)系：橋、道路、邊界；用不帶箭頭的連線表示，稱為邊。非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示，稱為弧。圖：點及邊（或?。┙M成。注意：一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上不同。第7頁，共87頁，2023年，2月20日，星期四對稱關(guān)系非對稱關(guān)系無向圖：圖由點和邊所構(gòu)成的，記作G={V,E}(V是點的集合，E是邊的集合)

連接點vi,vjV的邊記作eij={vi,vj}，或者[vj,vi]。有向圖：圖是由點和弧所構(gòu)成的，記作D={V,A}(V是點的集合，A是弧的集合)

，一條方向從vi指向vj的弧，記作(vi,vj)。圖的相關(guān)概念網(wǎng)絡(luò)圖：給圖中的點和邊賦予具體的含義和權(quán)數(shù)，如距離，費用，容量等，記作N.第8頁，共87頁，2023年，2月20日，星期四圖的相關(guān)概念若邊eij=[vi,vj]∈E，稱vi，vj是eij的端點，也稱vi，vj是相鄰的。稱eij是點vi（及點vj）的關(guān)聯(lián)邊。若兩條邊有一個公共的端點，則稱這兩條邊相鄰。vivjevi，vj相鄰

e與vi，vj關(guān)聯(lián)vie1vjvke2點與邊關(guān)聯(lián)點與點相鄰邊與邊相鄰第9頁，共87頁，2023年，2月20日，星期四若某條邊兩個端點相同，稱這條邊為環(huán)。若兩點之間有多于一條的邊，稱這些邊為多重邊。無環(huán)、無多重邊的圖稱為簡單圖。無環(huán)、但允許有多重邊的圖稱為多重圖。v1e1e2e3v2v3e5e4v4v5注：無特別聲明我們今后討論的圖都是簡單圖圖的相關(guān)概念第10頁，共87頁，2023年，2月20日，星期四

圖G中以點v為端點的邊的數(shù)目，稱為v在G中的次(度），記為d（v）。d(v1)=2d(v2)=3d(v3)=4d(v4)=1

次為1的點為懸掛點，懸掛點的關(guān)聯(lián)邊稱為懸掛邊，次為零的點稱為孤立點。v1e1e2e3v2v3e5e4v4v5次為奇數(shù)的點稱為奇點，否則稱為偶點。圖的相關(guān)概念第11頁，共87頁，2023年，2月20日，星期四給定圖G=（V，E），若圖G’=（V’，E’），其中V’V，E’E

，則稱G’是G的子圖。給定圖G=（V，E），若圖G’=（V，E’），其中E’E，則稱G’是G的一個支撐子圖（部分圖）。點全部保留（a）（b）子圖（c）部分圖子圖與部分圖（支撐子圖）第12頁，共87頁，2023年，2月20日，星期四圖的連通性鏈：設(shè)圖G=（V，E）中有一個點、邊交替序列{v1,e1,v2,…vn-1,en-1,vn}，若ei=(vi,vi+1)，即這(n-1)條邊把n個頂點串連起來，我們稱這個交替序列為圖G中的一條鏈，而稱點v1,vn為該鏈的兩個端點。對于簡單圖鏈也可以僅用點的序列來表示。如果一條鏈的兩個端點是同一個點，則稱它為閉鏈或圈；如果一條鏈的各邊均不相同，則稱此鏈為簡單鏈；更若一條鏈的各點、各邊均不相同，則稱該鏈為初等鏈。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9簡單鏈：1=（v2，v1，v3，v6，v4，v3，v5）初等鏈：2=（v2，v1，v3，v5）第13頁，共87頁，2023年，2月20日，星期四圖的連通性最短鏈:網(wǎng)絡(luò)中鏈上權(quán)值的和稱為鏈的長度，以點v1,vn為端點的諸鏈中長度最短的鏈稱為這兩點的最短鏈。連通圖：如果圖G=（V，E）中的任意兩點都是其某一條鏈的兩個端點，則稱圖G是連通圖，否則，稱圖G是不連通的。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9為不連通圖，有兩個連通分圖組成第14頁，共87頁，2023年，2月20日，星期四圖的矩陣表示圖的矩陣表示主要方法有：權(quán)矩陣、鄰接矩陣。權(quán)矩陣網(wǎng)絡(luò)圖N=（V，E），邊[vi，vj]的權(quán)為wij，構(gòu)造矩陣稱矩陣A為網(wǎng)絡(luò)N的權(quán)矩陣。第15頁，共87頁，2023年，2月20日，星期四v4v5v2v1v3234567894其權(quán)矩陣為：注：當G為無向圖時，權(quán)矩陣為對稱矩陣。第16頁，共87頁，2023年，2月20日，星期四圖G=（V，E），p=n，構(gòu)造矩陣稱矩陣A為G的鄰接矩陣。鄰接矩陣？vi與vj不相鄰圖的矩陣表示第17頁，共87頁，2023年，2月20日，星期四其鄰接矩陣為：

v4v5v2v1v3注：當G為無向圖時，鄰接矩陣為對稱矩陣。第18頁，共87頁，2023年，2月20日，星期四思考：有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽，下表中打的是個運動員報名參加比賽的項目，問六個項目的比賽順序應(yīng)如何安排？做到每名運動員都不連續(xù)地參加兩項比賽。ABCDEF分析：點表示項目，邊表示兩個項目有同一名運動員參加目的：在圖中找出點序列，使得依次排列的兩個點不相鄰，就找到了每名運動員不連續(xù)參加兩項比賽的安排方案A、C、B、F、E、D(不唯一)第19頁，共87頁，2023年，2月20日，星期四第八章

圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題

第20頁，共87頁，2023年，2月20日，星期四第八章

圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題

第21頁，共87頁，2023年，2月20日，星期四7個村莊要在他們之間架設(shè)電話線，要求任何兩個村莊都可以互相通電話(允許中轉(zhuǎn))，并且電話線根數(shù)最少？引例村莊1村莊4村莊3村莊6村莊2村莊5村莊7分析：用七個點代表村莊，如果在某兩個村莊之間架設(shè)電話線，則相應(yīng)的在兩點之間連一條邊，這樣電話線網(wǎng)就可以用一個圖來表示，并且滿足如下要求：連通圖圖中有圈的話，從圈中任去掉一條邊，余下的圖仍連通為什么？第22頁，共87頁，2023年，2月20日，星期四樹村莊1村莊4村莊3村莊6村莊2村莊5村莊7如果G=（V，E）是一個無圈的連通圖，則稱G為樹。

樹中必存在次為1的點（懸掛點）樹中任兩點必有一條鏈且僅有一條鏈；在樹的兩個不相鄰的點之間添加一條邊，就得到一個圈；反之，去掉樹的任一條邊，樹就成為不連通圖；n個頂點的樹有（n-1）條邊。樹是無圈連通圖中邊數(shù)最多的，也是最脆弱的連通圖！第23頁，共87頁，2023年，2月20日，星期四145241575237圖的部分樹（支撐樹）如果圖G=（V，E）的部分圖G’=（V，E’）是樹，則稱G’是G的部分樹（或支撐樹）。村莊1村莊4村莊3村莊6村莊2村莊5村莊7部分樹上各樹枝上權(quán)值的和稱為它的長度，其中長度最短的部分樹，稱其為該圖的最小部分樹（最小支撐樹）。點保留邊可去仍是樹不唯一思考：如何鋪設(shè)電話線，使得電話線長度最少？第24頁，共87頁，2023年，2月20日，星期四ijkml最小部分樹的求法定理：圖中任一個點i，若j是與相鄰點中距離最近的，則邊[i,j]一定必含在該圖的最小部分樹內(nèi)。推論：把圖的所有點分成和兩個集合，則兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。避圈法破圈法第25頁，共87頁，2023年，2月20日，星期四227541435175ABCDEST算法的步驟：1、在給定的賦權(quán)的連通圖上任選一點vi∈,其余點在中。2、從與的連線中找出權(quán)數(shù)最小的邊[vi,vj]，這條邊一定包含在最小部分樹內(nèi)，做以標記。3、令vi，；

4、重復(fù)2、3兩步，直至所有點都包含在中為止?！取卾i→求解最小生成樹的避圈算法S第26頁，共87頁，2023年，2月20日，星期四77ABCDEST2254143515求解最小生成樹的破圈算法算法的步驟：

1、在給定的賦權(quán)的連通圖上任找一個圈。

2、在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。

3、如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。第27頁，共87頁，2023年，2月20日，星期四第八章

圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題

第28頁，共87頁，2023年，2月20日，星期四第八章

圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題

第29頁，共87頁，2023年，2月20日，星期四什么是最短路問題？固定起點的最短路

Dijkstra(狄克斯拉)(荷蘭)算法：標號法逐次逼近算法(Ford(美國)算法)：修正標號法每對頂點之間的最短路路矩陣算法(Floyd(佛洛伊德)算法)最短路問題第30頁，共87頁，2023年，2月20日，星期四最短路問題提出

在現(xiàn)實生活中，除公路運輸網(wǎng)絡(luò)、電訊網(wǎng)絡(luò)等網(wǎng)絡(luò)圖以外，還有輸油管線這樣的圖。在輸油管線圖中，為反映油的輸送情況，兩點間不僅有連線，線上往往還標有箭頭，以表示油的流動方向。又如，指揮系統(tǒng)圖、控制系統(tǒng)圖等圖中都標有指向。從這樣的一類圖中就可以概括為有向圖的概念。第31頁，共87頁，2023年，2月20日，星期四有向圖由點集和V

中元素的有序?qū)Φ囊粋€集合所組成的二元組稱為有向圖，記為D=（V，A）。其中

V中的元素

vi叫做頂點，

A中元素aij叫做以vi為始點（尾），vj為終點（首）的弧。

aij與aji作為具有不同指向的弧是不同的。第32頁，共87頁，2023年，2月20日，星期四有向網(wǎng)絡(luò)與混合圖如果在圖D=（V，A）中，給每一弧賦予權(quán)值，如將弧aij=(vi,vj)有權(quán)值

wij，記為w(aij)=wij則賦權(quán)有向圖D=（V，A）稱為有向網(wǎng)絡(luò)，在不至于混淆時，也簡稱網(wǎng)絡(luò)?；旌蠄D如果一個圖中既有邊，也有弧，那么稱這種圖為混合圖。它往往出現(xiàn)在既有單行線，又有雙行線的交通圖中。12534372第33頁，共87頁，2023年，2月20日，星期四最短路問題引例下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線所需的費用?，F(xiàn)在某人要從v1出發(fā)，通過這個交通網(wǎng)到v8去，求使總費用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363第34頁，共87頁，2023年，2月20日，星期四從v1到v8：P1=（v1，v2，v5，v8）費用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）費用3+2+10+2+4=21P3=……從v1到v8的旅行路線從v1到v8的路。旅行路線總費用路上所有弧權(quán)之和。最短路問題中，不考慮有向環(huán)、并行弧。v2v523464v3v1v4v6121061210v8v9v72363第35頁，共87頁，2023年，2月20日，星期四幾個概念路：設(shè)p是D中一個首尾相連的弧的集合，如果vs是它的第一條弧的始點，vt是它的最后一條弧的終點，則稱它是以點vs為始點，以點vt為終點的一條路。路長：路p中所有弧的權(quán)值的和稱為路p的長，記為設(shè)圖D=（V，A）是一有向網(wǎng)絡(luò)

v2v523464v3v1V4v6121061210v8v9v72363第36頁，共87頁，2023年，2月20日，星期四設(shè)P是以點vs為始點，以點vt為終點的所有路的集合，如果,且，則稱p0是以點vs

為始點，以點vt為終點的最短路。而稱其路長為點

vi到點vj的距離，記為。幾個概念注意：在有向網(wǎng)絡(luò)中,一般最短路及一點到另一點的距離最短路問題是重要的最優(yōu)化問題之一，可以直接應(yīng)用于解決生產(chǎn)實際的許多問題:管道鋪設(shè)、線路安排、廠區(qū)布局等。而且經(jīng)常被作為一個基本工具來解決其他的優(yōu)化問題。第37頁，共87頁，2023年，2月20日，星期四最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法第38頁，共87頁，2023年，2月20日，星期四最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法第39頁，共87頁，2023年，2月20日，星期四求解最短路問題的Dijkstra算法條件：當所有

wij

≥0時，用來求給定點vs到任一個點vj最短路的公認的最好方法。事實：如果P是D中從vs到vj的最短路，vi是P中的一基解個點，那么，從vs沿P到vi的路是從vs到vi的最基解短路。Dijkstra算法是Dijkstra在1959年提出的，可用于求解指定兩點間的最短路問題，或從指定點到其余各點的最短路問題。由于其以標號為主要特征，又稱為標號法。v1v2v3v4v5最短路的子路是最短路第40頁，共87頁，2023年，2月20日，星期四Dijkstra算法基本思想

從始點vs出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。執(zhí)行過程中，與每個點對應(yīng)，記錄下一個數(shù)(稱為這個點的標號)

1.標號P（固定標號或永久性標號）——從始點vs到該標號點vj的最短路權(quán)P(vj)

。2.標號T（臨時性標號）——從始點vs到該標號點vj的最短路權(quán)上界T(vj)

。j

,P(vj)j,T(vj)該方法的每一步就是去修改T標號，并且把某一個具T標號的點改變?yōu)榫哂蠵標號的點，從而使D中具P標號的頂點數(shù)多一個，至多經(jīng)過n-1步，就可以求出始點vs到各點的最短路。前點標號j

——表示始點vs到vj的最短路上vj的前一點。第41頁，共87頁，2023年，2月20日，星期四Dijkstra算法步驟：

第二步：考慮滿足條件①的所有點；②vi具有P標號;vj具有T標號;修改vj的T標號為，并將結(jié)果仍記為T(vj)第一步：始點標上固定標號,其余各點標臨時性標號

T(vj)=,j1;第三步：若網(wǎng)絡(luò)圖中已無T標號點，停止計算。否則,令，s為T標號點集,然后將的T標號改成P標號，轉(zhuǎn)入第二步。第42頁，共87頁，2023年，2月20日，星期四v1,6圖上標號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

∞v1,3M,∞M,∞M,∞v1,1v1,1永久標號永久標號臨時標號v1出發(fā)到v8去，使總費用最小的旅行路線第43頁，共87頁，2023年，2月20日，星期四v1,6圖上標號法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,∞v1,3M,∞M,∞M,∞0,0v1,1v4,11v1,3永久標號臨時標號v1出發(fā)到v8去，使總費用最小的旅行路線第44頁，共87頁，2023年，2月20日，星期四v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v1,1M,∞M,∞M,∞1,3圖上標號法v4,11v1,3v1,6v3,5v3,5永久標號臨時標號v1出發(fā)到v8去，使總費用最小的旅行路線第45頁，共87頁，2023年，2月20日，星期四v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞M,∞v1,3圖上標號法v3,5v2,6v2,6永久標號臨時標號v1出發(fā)到v8去，使總費用最小的旅行路線第46頁，共87頁，2023年，2月20日，星期四v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞v1,3v5,12v5,9v5,9圖上標號法v3,5v2,6永久標號臨時標號v5,10v1出發(fā)到v8去，使總費用最小的旅行路線第47頁，共87頁，2023年，2月20日，星期四v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v5,12v1,3v5,9v5,12v3,5v2,6圖上標號法永久標號臨時標號v5,10v1出發(fā)到v8去，使總費用最小的旅行路線第48頁，共87頁，2023年，2月20日，星期四v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v1,3v5,12v3,5v2,6圖上標號法v5,9永久標號臨時標號標號結(jié)束反向追蹤v1出發(fā)到v8去，使總費用最小的旅行路線第49頁，共87頁，2023年，2月20日，星期四Dijkstra算法步驟：

第二步：考慮滿足條件①的所有點；②vi具有P標號;vj具有T標號;修改vj的T標號為，并將結(jié)果仍記為T(vj)第一步：始點標上固定標號,其余各點標臨時性標號

T(vj)=,j1;第三步：若網(wǎng)絡(luò)圖中已無T標號點，停止計算。否則,令，s為T標號點集,然后將的T標號改成P標號，轉(zhuǎn)入第二步。第50頁，共87頁，2023年，2月20日，星期四例求如下交通網(wǎng)絡(luò)中v1

到各點間最短路路長。Dijkstra算法（標號法）算例31025v4v1v2v5v312262448混合圖第51頁，共87頁，2023年，2月20日，星期四無向網(wǎng)絡(luò):負權(quán)弧時。wijvivjwijwijvjvi無向網(wǎng)絡(luò)中，最短路→最短鏈。

多個點對之間最短路？v1v2v312-3Dijkstra算法失效Dijkstra算法注意的問題逐步逼近算法路矩陣算法第52頁，共87頁，2023年，2月20日，星期四5727461263202657710v3v1v2v4v5v6v7練習(xí)：求如下無向網(wǎng)絡(luò)中v1到v7的最短鏈Dijkstra算法求最短鏈第53頁，共87頁，2023年，2月20日，星期四最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法第54頁，共87頁，2023年，2月20日，星期四最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法第55頁，共87頁，2023年，2月20日，星期四逐次逼近算法思想

該公式表明，P(1)1j中的第j個分量等于P(0)1j的分量與基本表(權(quán)矩陣)中的第j列相應(yīng)元素路長的最小值，它相當于在v1與vj之間插入一個轉(zhuǎn)接點(v1,v2,…,vn中的任一個，含點v1與vj)后所有可能路中的最短路的路長；每迭代一次，就相當與增加一個轉(zhuǎn)接點，而P(k)1j中的每一個分量則隨著k的增加而呈不增的趨勢！v1v2v312-3第56頁，共87頁，2023年，2月20日，星期四用于計算帶有負權(quán)弧指定點v1到其余各點的最短路j=1,2,…,n.k=1,2,…,t≤n.2.計算逐次逼近算法基本步驟

j=1,2,…,n.1.令其元素即是v1到vj的最短路長。3.當出現(xiàn)時，v1v2v312-3第57頁，共87頁，2023年，2月20日，星期四例計算從點v1到所有其它頂點的最短路解：初始條件為以后按照公式進行迭代。

直到得到，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1第58頁，共87頁，2023年，2月20日，星期四v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下標追蹤路徑基本表空格為無窮大第59頁，共87頁，2023年，2月20日，星期四v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下標追蹤路徑基本表空格為無窮大第60頁，共87頁，2023年，2月20日，星期四最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法第61頁，共87頁，2023年，2月20日，星期四最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法第62頁，共87頁，2023年，2月20日，星期四某些問題需要求網(wǎng)絡(luò)上任意兩點間的最短路。當然，它也可以用標號算法依次改變始點的辦法來計算，但是比較麻煩。這里介紹Floyd在1962年提出的路矩陣法，它可直接求出網(wǎng)絡(luò)中任意兩點間的最短路。Floyd算法(路矩陣法)思想第63頁，共87頁，2023年，2月20日，星期四

考慮D中任意兩點vi，vj，如將D中vi，vj以外的點都刪掉，得只剩vi，vj的一個子網(wǎng)絡(luò)D0，記wij為?。╲i，vj）的權(quán)。

在D0中加入v1及D中與vi，vj，v1相關(guān)聯(lián)的弧，得D1，D1中vi到vj的最短路記為,則一定有vivjv1wijFloyd算法(路矩陣法)思想

網(wǎng)絡(luò)D=（V，A，W），令U=(dij)nn，表示D中vi到vj的最短路的長度。dij第64頁，共87頁，2023年，2月20日，星期四

再在D1中加入v2及D中與vi，vj，v1，

v2相關(guān)聯(lián)的弧，得D2，D2中vi到vj的最短路長記為，則有Floyd算法(路矩陣法)思想第65頁，共87頁，2023年，2月20日，星期四Floyd算法(路矩陣法)步驟設(shè)有有向網(wǎng)絡(luò)D=（V，A），其權(quán)矩陣為A=(aij)n╳n，如下構(gòu)造路矩陣序列：則n階路矩陣D(n)中的元素d(n)ij就是vi到vj的最短路的路長。

令權(quán)矩陣A為初始路矩陣D（0），即令D（0）=A2.依次計算K階路矩陣D（K）=（d(k)ij）n╳n,k=1,2,…,n，這里第66頁，共87頁，2023年，2月20日，星期四路矩陣序列的含義K階路矩陣D（K）其中的元素表示相應(yīng)兩點間可能以點v1、v2、…、vk為轉(zhuǎn)接點的所有路中路長最短的路的路長。D（0）其中的任一元素表示相應(yīng)兩點間無轉(zhuǎn)接點時最短路路長。一階路矩陣D（1）其中的元素表示相應(yīng)兩點間可能以點v1為轉(zhuǎn)接點的所有路中路長最短的路的路長；……；為使計算程序化，轉(zhuǎn)接點按頂點下標的順序依次加入n階路矩陣D(n)其中的元素d(n)ij就是vi到vj的可能以點v1、v2、…、vn為轉(zhuǎn)接點的所有路中路長最短的路的路長。既是vi到vj的最短路的路長。第67頁，共87頁，2023年，2月20日，星期四例求如下交通網(wǎng)絡(luò)中各對點間最短路路長。該圖的權(quán)矩陣為：Floyd算法(路矩陣法)算例31025v4v1v2v5v312262448第68頁，共87頁，2023年，2月20日，星期四例求如下交通網(wǎng)絡(luò)中各對點間最短路路長。Floyd算法(路矩陣法)算例31025v4v1v2v5v312262448第69頁，共87頁，2023年，2月20日，星期四利用公式發(fā)現(xiàn)第一行，第一列元素不變31025v4v1v2v5v312262448第70頁，共87頁，2023年，2月20日，星期四利用公式發(fā)現(xiàn)第二行，第二列元素不變31025v4v1v2v5v312262448第71頁，共87頁，2023年，2月20日，星期四利用公式發(fā)現(xiàn)第三行，第三列元素不變31025v4v1v2v5v312262448第72頁，共87頁，2023年，2月20日，星期四利用公式發(fā)現(xiàn)第四行，第四列元素不變31025v4v1v2v5v312262448第73頁，共87頁，2023年，2月20日，星期四31025v4v1v2v5v312262448D(5)中的元素給出相應(yīng)兩點間的最短路，其下標給出最短路個頂點下標,比如：6254第74頁，共87頁，2023年，2月20日，星期四已知有7個村子，相互間道路的距離如下圖示。擬合建一所小學(xué)，已知A處有小學(xué)生30人，B處40人，C處25人，D處20人，E處50人，F(xiàn)處60人，G處60人,問小學(xué)應(yīng)建在哪一個村子，使學(xué)生上學(xué)最方便（原則①所有人走的總路程最短；②盡可能公平。）。最短路問題算例1(選址問題)AGFECB522747163D26第75頁，共87頁，2023年，2月20日，星期四最短路問題算例1(選址問題)AGFECB522747163D26第76頁，共87頁，2023年，2月20日，星期四最短路問題算例1(選址問題)第77頁，共87頁，2023年，2月20日，星期四第78頁，共87頁，2023年，2月20日，星期四第