最短路的Floyd算法（課堂運(yùn)用）

1、運(yùn)籌學(xué)講課教師：熊德國(guó)河南理工大學(xué)能源科學(xué)與工程學(xué)院1厚積薄發(fā)4.3.3最短路的Floyd算法FLOYD 算法算法 以上介紹的算法用來求源點(diǎn)至各點(diǎn)的最短路。在有些問題中，我們需要知道節(jié)點(diǎn)兩兩之間的最短路，比如選址問題。這類問題可以用DIJKSTRA算法，依次改變?cè)袋c(diǎn)來求解，但計(jì)算比較繁瑣。現(xiàn)在介紹一種直接計(jì)算任意兩節(jié)點(diǎn)之間最短路的方法Floyd算法，該算法由Floyd于1962年提出。 2厚積薄發(fā)4.3.3最短路的Floyd算法nnijdDAjiAjiwdijij),(,),(,Floyd算法是權(quán)矩陣迭代算法，記網(wǎng)絡(luò)的權(quán)矩陣為其中3厚積薄發(fā)4.3.3最短路的Floyd算法DD0nnkijkdD

2、),min(111kkjkikkijkijddddnk nnnijndDnijd算法基本步驟為：（2）計(jì)算其中，（3）重復(fù)（2），直到此時(shí)即為節(jié)點(diǎn)i到點(diǎn)j的最短路的距離。（1）令4厚積薄發(fā)4.3.3最短路的Floyd算法例例4.3.4 用Floyd算法計(jì)算圖421中任意兩節(jié)點(diǎn)間的最短路。 5厚積薄發(fā)4.3.3最短路的Floyd算法解：解：寫出圖421的權(quán)矩陣D，并令DD 0 0737012131022026122046400DD6厚積薄發(fā)4.3.3最短路的Floyd算法1010101),min(Dddddjiijij計(jì)算按 0737012131022026122046401D073701213

3、1022026122046400D7厚積薄發(fā)4.3.3最短路的Floyd算法D1的元素d1ij的意義為i直接到達(dá)j及經(jīng)節(jié)點(diǎn)1到達(dá)j的兩種方式中，最短路線的距離；0737012131022026122046401D8厚積薄發(fā)4.3.3最短路的Floyd算法2121212),min(Dddddjiijij計(jì)算按0737012153104262402612204566405214234213241251242D0737012131022026122046401D9厚積薄發(fā)4.3.3最短路的Floyd算法D2的元素d2ij的意義為i直接到達(dá)j及最多經(jīng)節(jié)點(diǎn)1、2到達(dá)j的所有方式中，最短路線的距離，這些可

4、能的方式有：i-j，i-1-j，i-2-j，i-1-2-j，i-2-1-j。例如d2434423表示節(jié)點(diǎn)4到節(jié)點(diǎn)3在這些方式中取423為最短路，距離為4。下標(biāo)423便于在算法結(jié)束時(shí)確定最短路之用。 0737012153104262402612204566405214234213241251242D10厚積薄發(fā)4.3.3最短路的Floyd算法0737012153104262402612204566405214234213241251243D0437594012153104267240265122049566406456423642642154652142342132463242461246125

5、1244D11厚積薄發(fā)4.3.3最短路的Floyd算法04365940121531032662302651220495664064564536426421546521453421354635424612461251245D04365940121531032662302651220495664064564536426421546521453421354635424612461251246D12厚積薄發(fā)4.3.3最短路的Floyd算法任意兩節(jié)點(diǎn)之間的最短路，最多可經(jīng)過節(jié)點(diǎn)1、2n到達(dá)，因此當(dāng)計(jì)算到Dn時(shí)，算法已結(jié)束，至此，得到任意兩點(diǎn)間的最短路及其距離。如本例題中，節(jié)點(diǎn)1、6之間的最短路為1246

6、，距離為9；節(jié)點(diǎn)3、4之間的最短路為354，距離為3；節(jié)點(diǎn)6、4之間的最短路為64，距離為3，等等。04365940121531032662302651220495664064564536426421546521453421354635424612461251246D13厚積薄發(fā)4.3.3最短路的Floyd算法例例4.3.5 選址問題選址問題最短路問題的應(yīng)用最短路問題的應(yīng)用II 圖422為某地區(qū)的居民區(qū)分布圖，各邊旁的數(shù)據(jù)為居民區(qū)間的距離，擬在其中一個(gè)居民區(qū)建一個(gè)大型超市，問超市建在那里，才能使距離超市最遠(yuǎn)的居民到超市的距離最近？ 14厚積薄發(fā)4.3.3最短路的Floyd算法解：解：如果超市建在i點(diǎn)，則需計(jì)算出i至各點(diǎn)的最短路的距離，其中最大者即離超市最遠(yuǎn)，于是問題變成求這些最大最短路中的最小者。 15厚積薄發(fā)4.3.3最短路的Floyd算法imd為這些最大值中最小者486md為此需計(jì)算任意兩點(diǎn)間的最短路。表示節(jié)點(diǎn)i到各節(jié)點(diǎn)的最短路中的最大值。超市應(yīng)建在第6居民區(qū)，到超市最遠(yuǎn)的居民區(qū)為節(jié)點(diǎn)5所示的小區(qū)，距離為48。 015633340306015048182515456