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

簡介

最短路問題是網(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