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

1、第八章圖與網(wǎng)絡(luò)分析 圖的基本概念與模型 樹圖和圖的最小部分樹 最短路問題 網(wǎng)絡(luò)最大流問題 最小費用最大流問題 第八章圖與網(wǎng)絡(luò)分析 圖的基本概念與模型 樹圖和圖的最小部分樹 最短路問題 網(wǎng)絡(luò)最大流問題 最小費用最大流問題 圖論是應(yīng)用非常廣泛的運籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運輸，經(jīng)濟管理，電子計算機等各項領(lǐng)域。對于科學(xué)研究，市場和社會生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題，都可以應(yīng)用圖論的方法，簡便、快捷地加以解決。引 言 1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一

2、篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問題。即一個漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。如圖1所示。引例1歐拉將這個問題抽象成一筆畫問題。即能否從某一點開始不重復(fù)地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個著名問題。 在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點和線來畫出各式各樣的示意圖。引例2左圖是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管

3、道圖，民用航空線圖等等。連云港武漢南京徐州上海北京塘沽青島濟南天津鄭州 有六支球隊進行足球比賽，我們分別用點v1v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊?wèi)?zhàn)勝v2隊，v2隊?wèi)?zhàn)勝v3隊，v3隊?wèi)?zhàn)勝v5隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出來。引例3v3v1v2v4v6v5圖的基本概念與模型點：研究對象（車站、國家、球隊）；點間連線：對象之間的特定關(guān)系（陸地間有橋、鐵路線、兩球隊比賽及結(jié)果)。對稱關(guān)系：橋、道路、邊界；用不帶箭頭的連線表 示，稱為邊。非對稱關(guān)系：甲隊勝乙隊，用帶箭頭的連線表示，稱為弧。圖：點及邊（或弧）組成。注意：一般情況下，圖中的相對

4、位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上不同。對稱關(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.圖的相關(guān)概念若邊eij=vi,vjE，稱vi，vj是eij的端點，也稱vi，vj是相鄰的。稱e

5、ij是點vi（及點vj）的關(guān)聯(lián)邊。若兩條邊有一個公共的端點，則稱這兩條邊相鄰。vivjevi，vj相鄰 e 與vi，vj關(guān)聯(lián)vie1vjvke2點與邊關(guān)聯(lián)點與點相鄰邊與邊相鄰若某條邊兩個端點相同，稱這條邊為環(huán)。若兩點之間有多于一條的邊，稱這些邊為多重邊。 無環(huán)、無多重邊的圖稱為簡單圖。無環(huán)、但允許有多重邊的圖稱為多重圖。v1e1e2e3v2v3e5e4v4v5注：無特別聲明我們今后討論的圖都是簡單圖圖的相關(guān)概念 圖G中以點v為端點的邊的數(shù)目，稱為v在G中的次(度）， 記為d（v）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次為1 的點為懸掛點，懸掛點的關(guān)聯(lián)邊稱為懸掛邊，次

6、為零的點稱為孤立點。v1e1e2e3v2v3e5e4v4v5次為奇數(shù)的點稱為奇點，否則稱為偶點。圖的相關(guān)概念給定圖G=（V，E），若圖G=（V，E），其中VV，E E ，則稱G是G的子圖。給定圖G=（V，E），若圖G=（V，E），其中EE，則稱G是G的一個支撐子圖（部分圖）。點全部保留（a）（b）子圖（c）部分圖子圖與部分圖（支撐子圖）圖的連通性鏈：設(shè)圖G=（V，E）中有一個點、邊交替序列 v1 ,e1,v2,vn-1,en-1 ,vn，若ei=(vi,vi+1)，即這(n-1)條邊把n個頂點串連起來，我們稱這個交替序列為圖G中的一條鏈，而稱點v1,vn為該鏈的兩個端點。對于簡單圖鏈也可以僅用

7、點的序列來表示。如果一條鏈的兩個端點是同一個點，則稱它為閉鏈或圈；如果一條鏈的各邊均不相同，則稱此鏈為簡單鏈；更若一條鏈的各點、各邊均不相同，則稱該鏈為初等鏈。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9簡單鏈：1=（v2，v1，v3，v6，v4，v3，v5）初等鏈：2=（v2，v1，v3，v5）圖的連通性最短鏈:網(wǎng)絡(luò)中鏈上權(quán)值的和稱為鏈的長度，以點v1,vn為端點的諸鏈中長度最短的鏈稱為這兩點的最短鏈。連通圖：如果圖G=（V，E）中的任意兩點都是其某一條鏈的兩個端點，則稱圖G是連通圖，否則，稱圖G是不連通的。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6

8、e8e9為不連通圖，有兩個連通分圖組成圖的矩陣表示圖的矩陣表示主要方法有：權(quán)矩陣、鄰接矩陣。權(quán)矩陣網(wǎng)絡(luò)圖N=（V，E），邊vi，vj的權(quán)為wij ，構(gòu)造矩陣稱矩陣A為網(wǎng)絡(luò)N的權(quán)矩陣。v4v5v2v1v3234567894其權(quán)矩陣為： 注：當(dāng)G為無向圖時，權(quán)矩陣為對稱矩陣。圖G=（V，E），p=n，構(gòu)造矩陣稱矩陣A為G的鄰接矩陣。鄰接矩陣？vi與vj不相鄰圖的矩陣表示其鄰接矩陣為： v4v5v2v1v3注：當(dāng)G為無向圖時，鄰接矩陣為對稱矩陣。 思考：有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽，下表中打的是個運動員報名參加比賽的項目，問六個項目的比賽順序應(yīng)如何安

9、排？做到每名運動員都不連續(xù)地參加兩項比賽。ABCDEF分析：點表示項目，邊表示兩個項目有同一名運動員參加目的：在圖中找出點序列，使得依次排列的兩個點不相鄰，就找到了每名運動員不連續(xù)參加兩項比賽的安排方案A、C、B、F、E、D(不唯一)第八章圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題 第八章圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題 7個村莊要在他們之間架設(shè)電話線，要求任何兩個村莊都可以互相通電話(允許中轉(zhuǎn))，并且電話線根數(shù)最少？引例村莊1村莊4村莊3村莊6村莊2村莊5村莊7分析：用七個點代表村莊

10、，如果在某兩個村莊之間架設(shè)電話線，則相應(yīng)的在兩點之間連一條邊，這樣電話線網(wǎng)就可以用一個圖來表示，并且滿足如下要求：連通圖圖中有圈的話，從圈中任去掉一條邊，余下的圖仍連通為什么？樹村莊1村莊4村莊3村莊6村莊2村莊5村莊7如果G=（V，E）是一個無圈的連通圖，則稱G為樹。 樹中必存在次為1的點（懸掛點）樹中任兩點必有一條鏈且僅有一條鏈；在樹的兩個不相鄰的點之間添加一條邊，就得到一個圈； 反之，去掉樹的任一條邊，樹就成為不連通圖；n個頂點的樹有（n-1）條邊。樹是無圈連通圖中邊數(shù)最多的，也是最脆弱的連通圖！145241575237圖的部分樹（支撐樹）如果圖G=（V，E）的部分圖G=（V，E）是樹，

11、 則稱G是G的部分樹（或支撐樹）。村莊1村莊4村莊3村莊6村莊2村莊5村莊7部分樹上各樹枝上權(quán)值的和稱為它的長度，其中長度最短的部分樹，稱其為該圖的最小部分樹（最小支撐樹）。點保留邊可去仍是樹不唯一思考：如何鋪設(shè)電話線，使得電話線長度最少？ijkml最小部分樹的求法定理：圖中任一個點i，若j是與相鄰點中距離最近的， 則邊i,j一定必含在該圖的最小部分樹內(nèi)。推論：把圖的所有點分成 和 兩個集合，則兩集合之間連線的最短邊一定包含在最小部分樹內(nèi)。避圈法破圈法227541435175ABCDEST算法的步驟： 1、在給定的賦權(quán)的連通圖上任選一點vi ,其余點在 中。 2、從 與 的連線中找出權(quán)數(shù)最小的

12、邊vi, vj，這條邊一定包含在最小部分樹內(nèi)，做以標(biāo)記。 3、令 vi ， ； 4、重復(fù)2、3兩步，直至所有點都包含在 中為止。vi求解最小生成樹的避圈算法S77ABCDEST2254143515求解最小生成樹的破圈算法算法的步驟： 1、在給定的賦權(quán)的連通圖上任找一個圈。 2、在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。 3、如果所余下的圖已不包含圈，則計算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。第八章圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題 第八章圖與網(wǎng)絡(luò)分析圖的基本概念與模型樹

13、圖和圖的最小部分樹最短路問題網(wǎng)絡(luò)最大流問題最小費用最大流問題 什么是最短路問題？固定起點的最短路 Dijkstra(狄克斯拉) (荷蘭)算法：標(biāo)號法 逐次逼近算法(Ford(美國)算法)：修正標(biāo)號法每 對 頂 點 之 間 的 最 短 路 路矩陣算法(Floyd(佛洛伊德)算法)最短路問題最短路問題提出 在現(xiàn)實生活中，除公路運輸網(wǎng)絡(luò)、電訊網(wǎng)絡(luò)等網(wǎng)絡(luò)圖以外，還有輸油管線這樣的圖。在輸油管線圖中，為反映油的輸送情況，兩點間不僅有連線，線上往往還標(biāo)有箭頭，以表示油的流動方向。又如，指揮系統(tǒng)圖、控制系統(tǒng)圖等圖中都標(biāo)有指向。從這樣的一類圖中就可以概括為有向圖的概念。有向圖由點集 和V 中元素的有序?qū)Φ囊粋€

14、集合 所組成的二元組稱為有向圖，記為D=（V，A）。 其中 V中的元素 vi叫做頂點， A中元素aij叫做以vi為始點（尾），vj為終點（首）的弧。 aij與aji作為具有不同指向的弧是不同的。有向網(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ò)。混合圖如果一個圖中既有邊，也有弧，那么稱這種圖為混合圖。它往往出現(xiàn)在既有單行線，又有雙行線的交通圖中。12534372最短路問題引例下圖為單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條線所需的費用?，F(xiàn)在某人要從v1出

15、發(fā)，通過這個交通網(wǎng)到v8去，求使總費用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363從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幾個概念路：設(shè)p是D中一個首尾相連的弧的集合，如果vs是它的第一條弧的始點，vt是它的最后一條弧的終點，則稱它是以點vs為始點，

16、以點vt為終點的一條路。路長：路p中所有弧的權(quán)值的和稱為路p的長，記為設(shè)圖D=（V，A）是一有向網(wǎng)絡(luò) v2v523464v3v1V4 v6121061210v8v9v72363設(shè)P是以點vs為始點，以點vt為終點的所有路的集合， 如果 ,且 ，則稱p0是以點vs 為始點，以點vt為終點的最短路。而稱其路長為點 vi到點vj的距離，記為 。幾個概念注意：在有向網(wǎng)絡(luò)中,一般最短路及一點到另一點的距離 最短路問題是重要的最優(yōu)化問題之一，可以直接應(yīng)用于解決生產(chǎn)實際的許多問題:管道鋪設(shè)、線路安排、廠區(qū)布局等。而且經(jīng)常被作為一個基本工具來解決其他的優(yōu)化問題。最短路問題求解方法Dijkstra算法逐步逼近算

17、法路矩陣算法最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法求解最短路問題的Dijkstra算法條件：當(dāng)所有 wij 0 時，用來求給定點vs到任一 個點vj 最短路的公認的最好方法。事實：如果P是D中從vs到vj的最短路，vi是P中的一 基解 個點，那么，從vs沿P到vi的路是從vs到vi的最基解 短路。 Dijkstra算法是Dijkstra在1959年提出的，可用于求解指定兩點間的最短路問題，或從指定點到其余各點的最短路問題。由于其以標(biāo)號為主要特征，又稱為標(biāo)號法。v1v2v3v4v5最短路的子路是最短路Dijkstra算法基本思想 從始點vs出發(fā)，逐步順序地向外探尋，每向外延

18、伸一步都要求是最短的。執(zhí)行過程中，與每個點對應(yīng)，記錄下一個數(shù)(稱為這個點的標(biāo)號) 1.標(biāo)號 P（固定標(biāo)號或永久性標(biāo)號）從始點vs到該標(biāo)號點vj的最短路權(quán)P (vj) 。 2.標(biāo)號 T（臨時性標(biāo)號）從始點vs到該標(biāo)號點vj的最短路權(quán)上界T (vj) 。j ,P (vj)j, T (vj) 該方法的每一步就是去修改T標(biāo)號，并且把某一個具T標(biāo)號的點改變?yōu)榫哂蠵標(biāo)號的點，從而使D中具P標(biāo)號的頂點數(shù)多一個，至多經(jīng)過n-1步，就可以求出始點vs到各點的最短路。前點標(biāo)號j 表示始點vs到vj的最短路上vj的前一點。Dijkstra算法步驟： 第二步：考慮滿足條件 的所有點； vi具有P 標(biāo)號;vj具有T 標(biāo)

19、號; 修改vj的T標(biāo)號為 ，并將結(jié)果仍記為T(vj)第一步：始點標(biāo)上固定標(biāo)號 ,其余各點標(biāo)臨時性標(biāo)號 T(vj)=, j1; 第三步：若網(wǎng)絡(luò)圖中已無T標(biāo)號點，停止計算。否則, 令 ，s為T標(biāo)號點集, 然后將 的T 標(biāo)號改成P 標(biāo)號 ，轉(zhuǎn)入第二步。v1,6圖上標(biāo)號法v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, v1,3M, M, M, v1,1v1,1永久標(biāo)號永久標(biāo)號臨時標(biāo)號v1出發(fā)到v8去，使總費用最小的旅行路線v1,6圖上標(biāo)號法v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, v1,3M, M, M,

20、 0,0v1,1v4,11v1,3永久標(biāo)號臨時標(biāo)號v1出發(fā)到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, v1,1M, M,M, 1,3圖上標(biāo)號法v4,11v1,3v1,6v3,5v3,5永久標(biāo)號臨時標(biāo)號v1出發(fā)到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, v4,11v1,1M, M, M, v1,3圖上標(biāo)號法v3,5v2, 6v2, 6永久標(biāo)號臨時標(biāo)號v1出發(fā)到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v

21、9v72363v60,0M, v4,11v1,1M, M, v1,3v5,12v5,9v5,9圖上標(biāo)號法v3,5v2, 6永久標(biāo)號臨時標(biāo)號v5,10v1出發(fā)到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0v5,10v1,1M, v5, 12 v1,3v5,9v5, 12 v3,5v2, 6圖上標(biāo)號法永久標(biāo)號臨時標(biāo)號v5,10v1出發(fā)到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0v5,10v1,1M, v1,3v5, 12 v3,5v2, 6圖上標(biāo)號法v5,9永久

22、標(biāo)號臨時標(biāo)號標(biāo)號結(jié)束 反向追蹤v1出發(fā)到v8去，使總費用最小的旅行路線Dijkstra算法步驟： 第二步：考慮滿足條件 的所有點； vi具有P 標(biāo)號;vj具有T 標(biāo)號; 修改vj的T標(biāo)號為 ，并將結(jié)果仍記為T(vj)第一步：始點標(biāo)上固定標(biāo)號 ,其余各點標(biāo)臨時性標(biāo)號 T(vj)=, j1; 第三步：若網(wǎng)絡(luò)圖中已無T標(biāo)號點，停止計算。否則, 令 ，s為T標(biāo)號點集, 然后將 的T 標(biāo)號改成P 標(biāo)號 ，轉(zhuǎn)入第二步。例 求如下交通網(wǎng)絡(luò)中v1 到各點間最短路路長。Dijkstra算法（標(biāo)號法）算例31025v4v1v2v5v312262448混合圖無向網(wǎng)絡(luò):負權(quán)弧時。wijvivjwijwijvjvi無向

23、網(wǎng)絡(luò)中，最短路最短鏈。 多個點對之間最短路？v1v2v312-3Dijkstra算法失效Dijkstra算法注意的問題逐步逼近算法路矩陣算法5727461263202657710v3v1v2v4v5v6v7練習(xí)：求如下無向網(wǎng)絡(luò)中v1到v7的最短鏈Dijkstra算法求最短鏈最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法逐次逼近算法思想 該公式表明， P(1)1j中的第j個分量等于P(0)1j的分量與基本表(權(quán)矩陣)中的第j列相應(yīng)元素路長的最小值，它相當(dāng)于在v1與vj之間插入一個轉(zhuǎn)接點(v1,v2,vn中的任一個，含點v1

24、與vj)后所有可能路中的最短路的路長；每迭代一次，就相當(dāng)與增加一個轉(zhuǎn)接點，而P(k)1j中的每一個分量則隨著k的增加而呈不增的趨勢！v1v2v312-3用于計算帶有負權(quán)弧指定點v1到其余各點的最短路j=1,2,n. k=1,2,tn.2.計算逐次逼近算法基本步驟 j=1,2,n.1.令其元素即是v1到vj的最短路長。3.當(dāng)出現(xiàn)時，v1v2v312-3例 計算從點v1到所有其它頂點的最短路解：初始條件為 以后按照公式 進行迭代。 直到得到 ，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v

25、3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下標(biāo)追蹤路徑基本表空格為無窮大v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下標(biāo)追蹤路徑基本表空格為無窮大最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法 某些問題需要求網(wǎng)絡(luò)上任意兩點間的最短路。當(dāng)然，它也可以用標(biāo)號算法依次改變始點的辦法來計算，但是比較麻煩。 這里介紹Fl

26、oyd在1962年提出的路矩陣法，它可直接求出網(wǎng)絡(luò)中任意兩點間的最短路。Floyd算法(路矩陣法)思想 考慮D中任意兩點vi，vj，如將D中vi，vj以外的點都刪掉，得只剩vi，vj的一個子網(wǎng)絡(luò)D0，記wij為?。?vi，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 再在D1中加入v2及D中與vi，vj，v1， v2相關(guān)聯(lián)的弧，得D2，D2中vi到vj的最短路長記為 ，則有Floyd算法(

27、路矩陣法)思想Floyd算法(路矩陣法)步驟設(shè)有有向網(wǎng)絡(luò)D=（V，A），其權(quán)矩陣為A=(aij)nn，如下構(gòu)造路矩陣序列：則n階路矩陣D(n)中的元素d(n)ij就是vi到vj的最短路的路長。 令權(quán)矩陣A為初始路矩陣D（0），即令D（0）=A2. 依次計算K階路矩陣D（K）=（d(k)ij）nn, k=1,2,n，這里路矩陣序列的含義 K階路矩陣D（K） 其中的元素表示相應(yīng)兩點間可能以點v1、v2、vk為 轉(zhuǎn)接點的所有路中路長最短的路的路長。 D（0） 其中的任一元素表示相應(yīng)兩點間無轉(zhuǎn)接點時最短路路長。一階路矩陣D（1） 其中的元素表示相應(yīng)兩點間可能以點v1為轉(zhuǎn)接點的所有路中路長最短的路的路長

28、；為使計算程序化，轉(zhuǎn)接點按頂點下標(biāo)的順序依次加入n階路矩陣D(n) 其中的元素d(n)ij就是vi到vj的可能以點v1、v2、vn為轉(zhuǎn)接點的所有路中路長最短的路的路長。既是vi到vj的最短路的路長。例 求如下交通網(wǎng)絡(luò)中各對點間最短路路長。該圖的權(quán)矩陣為：Floyd算法(路矩陣法)算例31025v4v1v2v5v312262448例 求如下交通網(wǎng)絡(luò)中各對點間最短路路長。Floyd算法(路矩陣法)算例31025v4v1v2v5v312262448利用公式發(fā)現(xiàn)第一行，第一列元素不變31025v4v1v2v5v312262448利用公式發(fā)現(xiàn)第二行，第二列元素不變31025v4v1v2v5v312262448利用公式發(fā)現(xiàn)第三行，第三列元素不變31025v4v1v2v5v312262448利用公式發(fā)現(xiàn)第四行，第四列元素不變31025v4v1v2v5v31226244831025v4v1v2v5v312262448D(5)中的元素給出相應(yīng)兩點間的最短路，其下標(biāo)給出最短路個頂點下標(biāo),比如：6254已知有7個村子，相互間道路的距離如下圖示。擬合建一所小學(xué)，已知A處有小學(xué)生30人，B處40人，C處25人，D處20人，E處50人，F(xiàn)處60人， G處60人,問小學(xué)應(yīng)建在哪一個村子，使學(xué)生上學(xué)最方便（原則所有人走的總路程最短；盡可能公平。）。