最短路的Floyd算法.ppt

運籌學(xué),講課教師：熊德國,河南理工大學(xué)能源科學(xué)與工程學(xué)院,4.3.3最短路的Floyd算法,FLOYD算法以上介紹的算法用來求源點至各點的最短路。在有些問題中，我們需要知道節(jié)點兩兩之間的最短路，比如選址問題。這類問題可以用DIJKSTRA算法，依次改變源點來求解，但計算比較繁瑣?，F(xiàn)在介紹一種直接計算任意兩節(jié)點之間最短路的方法Floyd算法，該算法由Floyd于1962年提出。,4.3.3最短路的Floyd算法,Floyd算法是權(quán)矩陣迭代算法，記網(wǎng)絡(luò)的權(quán)矩陣為,其中,4.3.3最短路的Floyd算法,算法基本步驟為：,（2）計算,其中，,（3）重復(fù)（2），直到,此時,即為節(jié)點i到點j的最短路的距離。,（1）令,4.3.3最短路的Floyd算法,例4.3.4用Floyd算法計算圖421中任意兩節(jié)點間的最短路。,4.3.3最短路的Floyd算法,解：寫出圖421的權(quán)矩陣D，并令,4.3.3最短路的Floyd算法,4.3.3最短路的Floyd算法,D1的元素d1ij的意義為i直接到達(dá)j及經(jīng)節(jié)點1到達(dá)j的兩種方式中，最短路線的距離；,4.3.3最短路的Floyd算法,4.3.3最短路的Floyd算法,D2的元素d2ij的意義為i直接到達(dá)j及最多經(jīng)節(jié)點1、2到達(dá)j的所有方式中，最短路線的距離，這些可能的方式有：i-j，i-1-j，i-2-j，i-1-2-j，i-2-1-j。例如d2434423表示節(jié)點4到節(jié)點3在這些方式中取423為最短路，距離為4。下標(biāo)423便于在算法結(jié)束時確定最短路之用。,4.3.3最短路的Floyd算法,4.3.3最短路的Floyd算法,4.3.3最短路的Floyd算法,任意兩節(jié)點之間的最短路，最多可經(jīng)過節(jié)點1、2n到達(dá)，因此當(dāng)計算到Dn時，算法已結(jié)束，至此，得到任意兩點間的最短路及其距離。如本例題中，節(jié)點1、6之間的最短路為1246，距離為9；節(jié)點3、4之間的最短路為354，距離為3；節(jié)點6、4之間的最短路為64，距離為3，等等。,4.3.3最短路的Floyd算法,例4.3.5選址問題最短路問題的應(yīng)用II圖422為某地區(qū)的居民區(qū)分布圖，各邊旁的數(shù)據(jù)為居民區(qū)間的距離，擬在其中一個居民區(qū)建一個大型超市，問超市建在那里，才能使距離超市最遠(yuǎn)的居民到超市的距離最近？,4.3.3最短路的Floyd算法,解：如果超市建在i點，則需計算出i至各點的最短路的距離，其中最大者即離超市最遠(yuǎn)，于是問題變成求這些最大最短路中的最小者。,4.3.3最短路的Floyd算法,為此需計算任意兩點間的最短路。,表示節(jié)點i到各節(jié)點的最短路中的最大值。,超