Floyd算法在最優(yōu)路徑中應(yīng)用

摘 要：采用Floyd算法作為求解該問題的核心算法，對(duì)時(shí)間鄰接矩陣進(jìn)行智能搜索，尋找到時(shí)間最少和路徑最短的最優(yōu)路徑.及時(shí)確定最佳路線，以提高在實(shí)際問題應(yīng)用效率.

YUAN Wei-Wei

（College of science， Heihe college， Heihe 164300， HeiLongJiang China）

Abstract To study the path of fire engines， to determine the best route to improve the fire speed， shorten the time the fire engine arrived at the fire. Use Floyd algorithm as the core algorithm to solve the problem of time adjacency matrix intelligent search， to find the shortest path and minimum time optimal path.

Key words： Floyd algorithm； Path optimization； Directed graph

求解最佳路徑的過程即尋找最短時(shí)間和最短路徑，我們將路徑抽象為有向圖，利用有向圖的鄰接矩陣。使用Floyd算法對(duì)時(shí)間鄰接矩陣進(jìn)行智能搜索，尋找到時(shí)間最少和路徑最短的最優(yōu)路徑。

1 Floyd算法核心思想

Floyd算法又稱為插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。通過一個(gè)圖的權(quán)值矩陣求出任意兩點(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[aij]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號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱D=[n] 為圖的距離矩陣。

圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)形式說明：

#define MaxVertexNum 50 //最大頂點(diǎn)數(shù)

typedef char VertexType； //頂點(diǎn)類型

typedef int EdgeType； //邊上的權(quán)值類型

typedef struct{

VextexType vexs[MaxVertexNum] //頂點(diǎn)表

EdeType edges[MaxVertexNum][MaxVertexNum]；//鄰接矩陣，可看作邊表

int n，e； //圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)

}MGragh；

建立無向網(wǎng)絡(luò)的算法

void CreateMGraph（MGraph *G）

{//建立無向網(wǎng)的鄰接矩陣表示

int i，j，k，w；

scanf（"%d%d"，&G->n，&G->e）； //輸入頂點(diǎn)數(shù)和邊數(shù)

for（i=0；in；i++） //讀人頂點(diǎn)信息，建立頂點(diǎn)表

G->vexs[i]=getchar（）；

for（i=0；in；i++）

for（j=0；jn；j++）

G->edges[i][j]=0； //鄰接矩陣初始化

for（k=0；ke；k++）{//讀入e條邊，建立鄰接矩陣

scanf（"%d%d%d"，&i，&j，&w）；//輸入邊（v i ，v j ）上的權(quán)w

G->edges[i][j]=w；

G->edges[j][i]=w；

}

}//CreateMGraph

2 應(yīng)用舉例

求解圖一的最優(yōu)路徑，我們可以得到鄰接矩陣A，通過matlab 軟件程序，借助Floyd 算法可以輕松求出距離矩陣D

我們能夠求出路徑

3.結(jié)論

采用floy算法能夠及時(shí)準(zhǔn)確地獲取動(dòng)態(tài)的耗時(shí)特征，對(duì)時(shí)間鄰接矩陣進(jìn)行智能搜索，尋找到時(shí)間最少和路徑最短的最優(yōu)路徑做出準(zhǔn)確合理的應(yīng)急決策。適合復(fù)雜和多點(diǎn)圖，可以通過程序重復(fù)使用，只需輸入相應(yīng)的仞始數(shù)據(jù)即可，極大的提高在實(shí)際問題應(yīng)用效率.

參考文獻(xiàn)：

[1] 李蔚萱.圖論[M].長(zhǎng)沙：湖南科學(xué)技術(shù)出版社，1980.91-11.5

[2] 李剛.離散數(shù)學(xué)[M].上海，復(fù)旦大學(xué)出版社，2006：225-230. [3] 耿素云，屈婉玲.離散數(shù)學(xué)[M].北京：北京大學(xué)出版社，2002.

作者簡(jiǎn)介：袁威威，（ 1982—），女，黑龍江黑河市人，黑河學(xué)院理學(xué)院數(shù)學(xué)系講師，從事數(shù)學(xué)與應(yīng)用數(shù)學(xué)

基金項(xiàng)目：黑河學(xué)院科學(xué)技術(shù)研究項(xiàng)目《基于黑河中俄自由貿(mào)易園區(qū)背景下消防布控最優(yōu)化問題的研究》，項(xiàng)目編號(hào)：KJQ201601