版權(quán)歸原作者所有,如有侵權(quán),請聯(lián)系我們

[科普中國]-弗洛伊德最短距離算法

科學(xué)百科
原創(chuàng)
科學(xué)百科為用戶提供權(quán)威科普內(nèi)容,打造知識科普陣地
收藏

簡介

最短路問題是網(wǎng)絡(luò)最優(yōu)化中一個基本而又非常重要的問題,這一問題相對比較簡單,在實際生產(chǎn)和生活中經(jīng)常遇到,許多的網(wǎng)絡(luò)最優(yōu)化問題可以化為最短路問題,或者用最短路算法作為其子程序.因此,最短路的用途已遠(yuǎn)遠(yuǎn)超出其表面意義迄今為止,所有最短路算法都只對不含負(fù)回路的網(wǎng)絡(luò)有效,實際上對含有負(fù)回路的網(wǎng)絡(luò),其最短路問題是NP困難的,因此本研究所討論的網(wǎng)絡(luò)也不含負(fù)回路.此外,如果將無向圖每條邊用兩條端點相同、方向相反的弧來代替,可以將其化為有向圖,因而不討論無向圖.本研究中未述及的術(shù)語、記號可參見文獻(xiàn)1。

Floyd算法是一種用于尋找給定加權(quán)圖中頂點間最短路徑的算法,以1978年圖靈獎獲得者斯坦福大學(xué)計算機科學(xué)系教授RobertW.Floyd命名。Floyd算法采用動態(tài)規(guī)劃的原理計算兩兩頂點間最短路徑[3],主要解決網(wǎng)絡(luò)路由尋找最優(yōu)路徑的問題2。

算法思想路徑矩陣通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。

從圖的帶權(quán)鄰接矩陣A=[a(i,j)] n×n開始,遞歸地進(jìn)行n次更新,即由矩陣D(0)=A,按一個公式,構(gòu)造出矩陣D(1);又用同樣地公式由D(1)構(gòu)造出D(2);……;最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度,稱D(n)為圖的距離矩陣,同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。

采用松弛技術(shù)(松弛操作),對在i和j之間的所有其他點進(jìn)行一次松弛。所以時間復(fù)雜度為O(n^3);

狀態(tài)轉(zhuǎn)移方程其狀態(tài)轉(zhuǎn)移方程如下:

map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};

map[i,j]表示i到j(luò)的最短距離,K是窮舉i,j的斷點,map[n,n]初值應(yīng)該為0,或者按照題目意思來做。

當(dāng)然,如果這條路沒有通的話,還必須特殊處理,比如沒有map[i,k]這條路。

算法過程1,從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán),如果兩點之間沒有邊相連,則權(quán)為無窮大。

2,對于每一對頂點 u 和 v,看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。

把圖用鄰接矩陣G表示出來,如果從Vi到Vj有路可達(dá),則G[i][j]=d,d表示該路的長度;否則G[i][j]=無窮大。定義一個矩陣D用來記錄所插入點的信息,D[i][j]表示從Vi到Vj需要經(jīng)過的點,初始化D[i][j]=j。把各個頂點插入圖中,比較插點后的距離與原來的距離,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值變小,則D[i][j]=k。在G中包含有兩點之間最短道路的信息,而在D中則包含了最短通路徑的信息。

比如,要尋找從V5到V1的路徑。根據(jù)D,假如D(5,1)=3則說明從V5到V1經(jīng)過V3,路徑為{V5,V3,V1},如果D(5,3)=3,說明V5與V3直接相連,如果D(3,1)=1,說明V3與V1直接相連。

復(fù)雜度時間復(fù)雜度:O(n^3)

空間復(fù)雜度:O(n^2)

算法實現(xiàn)C語言#include#include#define max 1000000000 int d[1000][1000],path[1000][1000];int main(){ int i,j,k,m,n; int x,y,z; scanf("%d%d",&n,&m); for(i=1;i