1、第三節(jié) 最短路問(wèn)題,最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣的問(wèn)題之一。許多優(yōu)化問(wèn)題可以使這個(gè)模型，如設(shè)備更新、管道鋪設(shè)、線(xiàn)路安排、廠區(qū)布局等。圖論方法比較有效。最短路問(wèn)題的一般提法如下：設(shè)G=（V，E）為連通圖，圖中各邊 為圖中任意兩點(diǎn)，求一條道路 ，使他是從 的所有道路中總權(quán)最小的道路。即： 最小.,,,,,,有些

2、最短問(wèn)題也可以使球網(wǎng)絡(luò)中某指定點(diǎn)到其余所有結(jié)點(diǎn)的最短路，過(guò)求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。下面我們介紹三種算法，可分別用于求解這幾種最短路問(wèn)題。一、Dijkstra算法 本算法由Dijkstra于1959年提出，可用于求解指定兩點(diǎn) 間的最短路，或從指定點(diǎn) 到其余各點(diǎn)的最短路，目前被認(rèn)為是求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路問(wèn)題的最好方法。算法的基本思想基于以下原理：若序列 是從 的最短

3、路，則序列 必為從 的最短路。,,,,,,,基本步驟：,求出從a到z的最短路的長(zhǎng)度是？,,,,,,,,,,,a,c,b,e,d,z,5,4,,2,10,1,8,2,6,3,,,,,,,解：0次迭代（初始化）L(a)=0,L(b)=L(c)=L(d)=L(e)=L(z)= ,S0= ;一次迭代：取u1=a,S1={a} L(a)+w

4、(a,b)=0+4=4<L(b) L(a)+w(a,c)=0+2=2<L(c) L(a)+w(a,d)=0+ = L(a)+w(a,e)=L(a)+w(a,z)=0+ = ; L(b)=4,L(c)=2,L(d)=L(e)=L(z)= 二次迭代：取u2=c,

5、 S2={a,c} L(c)+w(c,b)=2+1=3<L(b) L(c)+w(c,d)=2+8=10<L(d) L(c)+w(c,e)=2+10=12<L(e) L(c)+w(c,z)=2+ = L(b)=3,L(d)=10,L(e)=12,L(z)

6、=,三次迭代：取u3=b, S3={a,c,b} L(b)+w(b,d)=3+5=8<L(d) L(b)+w(b,e)=3+ = L(b)+w(b,z)=3+ = L(d)=8, L(e)=12, L(z)=四次迭代：取u4=d, S4={a,c,b,d} L(d)+w

7、(d,e)=8+2=10<L(e) L(d)+w(d,z)=8+6=14<L(z) L(e)=10, L(z)=14;五次迭代：取u5=e, S5={a,c,b,d,e} L(e)+w(e,z)=10+3=13<L(z) L(z)=13結(jié)束：u6=z, S6={a,c,b,d,e,z}從a到z 的最短路

8、的長(zhǎng)度為13,最短路經(jīng)為{a,c,b,d,e,z},同樣可以利用Dijkstra算法計(jì)算有向網(wǎng)絡(luò)中最短有向路的長(zhǎng)度，基本步驟如下：,求出點(diǎn)1到其余各頂點(diǎn)的最短有向路的長(zhǎng)度？,1,,,,,,,,,5,4,3,2,,5,3,2,8,4,7,3,1,Dijkstra算法:,課堂練習(xí)1：利用Dijkstra算法，算出圖中，v1到v5的最短路的長(zhǎng)度？,,,,,,,,,,,,,,,V1,V3,,V2,V4,V5,4,,3,2,7,5,8,10,1,

9、選址問(wèn)題：已知某地區(qū)的交通網(wǎng)絡(luò)如圖5-39所示，其中點(diǎn)代表居民區(qū)，邊表示公路， 為小區(qū)間公路距離，問(wèn)區(qū)中心醫(yī)院建在哪個(gè)小區(qū)，可使距離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近?,,解：實(shí)際是要求出圖的中心，可以化為一系列求最短路問(wèn)題。先求出 v1 到其他各頂點(diǎn)的最短路長(zhǎng)dj,令D(v1)=max{d1,d2,…,d7},表示若醫(yī)院建在v1, 則離醫(yī)院最遠(yuǎn)的小區(qū)距離為D(v1),再依次計(jì)算v2,v3,…,v7到其余各點(diǎn)的最短路，類(lèi)似求出

10、D(v2),D(v3),…D(v7), D(vi)(i=1,2,…,7)中最小者即為所求，計(jì)算結(jié)果見(jiàn)表5-3。,由于 D(v6)=48最小，所以醫(yī)院健在v6，此時(shí)離醫(yī)院最遠(yuǎn)的小區(qū) v5距離為48。,Floyd算法 某些問(wèn)題中，要求網(wǎng)絡(luò)上任意兩點(diǎn)間的最短路，如例15就是這樣。這類(lèi)問(wèn)題可以用Dijkstra算法一次改變起點(diǎn)的辦法計(jì)算，但比較繁瑣。這里介紹的Floyd

11、方法（1962）可直接求出網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。為計(jì)算方便，令網(wǎng)絡(luò)的權(quán)矩陣為 。 其中 算法基本步驟為：,首先介紹矩陣的兩種運(yùn)算：,求圖中任意兩點(diǎn)間的最短有向路的長(zhǎng)度？,V1,V4,V5,V3,V2,V6,,,,,,,,,,1,2,2,1,7,3,1,3,,6,課堂

12、練習(xí)2：利用Floyd算法，算出圖中任意兩點(diǎn)之間的最短有向路的長(zhǎng)度?,1,4,5,2,3,6,,,,,,,,,,,5,3,5,6,,4,2,3,7,2,1,最大匹配問(wèn)題：考慮工作分配問(wèn)題。有n個(gè)工人，m件工作，每個(gè)工人能力不同，各能勝任其中某幾項(xiàng)工作。假設(shè)每件工作只需要一人做，每人只做一件工作，怎樣分配才能盡量的工作有人做，更多的人有工作？這個(gè)問(wèn)題可以用圖的語(yǔ)言描述，如圖5-47。其中x1,x2,…,xn表示工人,y1,y2,…,

13、ym表示工作，邊（xi,yj)表示第i個(gè)人能勝任第j項(xiàng)工作，這樣就得到了一個(gè)二部圖G，用點(diǎn)集X表示{x1,x2,…xn}，點(diǎn)集Y表示{y1,y2,…,ym} ,二部圖G=(X,Y,E)。上述的工作分配問(wèn)題就是要在圖G中找一個(gè)邊集E的子集，使得集中任何兩條邊沒(méi)有公共端點(diǎn)，最好的方案就是要使此邊集的邊數(shù)盡可能多，這就是匹配問(wèn)題。,定義23 二部圖 G=(X,Y,E) ，M是邊集E的子集，若M中的任意兩條邊都沒(méi)有公共端點(diǎn)，則稱(chēng)M為圖G的一

14、個(gè)匹配（也稱(chēng)對(duì)集）。M中任意一條邊的端點(diǎn)v稱(chēng)為（關(guān)于M的）飽和點(diǎn)，G中其他定點(diǎn)稱(chēng)為非飽和點(diǎn)。若不存在另一條匹配 ，則稱(chēng)M為最大匹配。設(shè)M是G的一個(gè)匹配，P是G的一條道路，若P中的邊是M與E(G)-M中的邊交替出現(xiàn)的，則稱(chēng)P為M交錯(cuò)路；若起點(diǎn)和終點(diǎn)都是M非飽和點(diǎn)，則稱(chēng)P為M可擴(kuò)路。如何尋找二部圖中的最大匹配問(wèn)題？最早是由匈牙利數(shù)學(xué)家Egervary給出的,稱(chēng)為匈牙利算法：基本思想：尋找非飽和