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

簡(jiǎn)介

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

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

算法思想路徑矩陣通過一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣。

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

采用松弛技術(shù)（松弛操作），對(duì)在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時(shí)間復(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的斷點(diǎn)，map[n,n]初值應(yīng)該為0，或者按照題目意思來做。

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

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

2，對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。

把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達(dá)，則G[i][j]=d，d表示該路的長(zhǎng)度；否則G[i][j]=無窮大。定義一個(gè)矩陣D用來記錄所插入點(diǎn)的信息，D[i][j]表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化D[i][j]=j。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來的距離，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值變小，則D[i][j]=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在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ù)雜度時(shí)間復(fù)雜度：O(n^3)

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

算法實(shí)現(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