Floyd算法在最優路徑中應用

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

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

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

1 Floyd算法核心思想

Floyd算法又稱為插點法，是一種用于尋找給定的加權圖中頂點間最短路徑的算法。通過一個圖的權值矩陣求出任意兩點間的最短路徑矩陣。從圖的帶權鄰接矩陣A=[aij]n×n 開始，遞歸地進行n次更新：由矩陣D=[0]=A ，按公式，構造出矩陣D=[1] ；又用同樣地公式由D=[1] 構造出D=[2] ；……；最后又用同樣的公式由D=[n-1] 構造出矩陣D=[n] 。矩陣D=[n] 的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D=[n] 為圖的距離矩陣。

圖的鄰接矩陣存儲結構形式說明：

#define MaxVertexNum 50 //最大頂點數

typedef char VertexType； //頂點類型

typedef int EdgeType； //邊上的權值類型

typedef struct{

VextexType vexs[MaxVertexNum] //頂點表

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

int n，e； //圖中當前的頂點數和邊數

}MGragh；

建立無向網絡的算法

void CreateMGraph（MGraph *G）

{//建立無向網的鄰接矩陣表示

int i，j，k，w；

scanf（"%d%d"，&G->n，&G->e）； //輸入頂點數和邊數

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

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 ）上的權w

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

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

}

}//CreateMGraph

2 應用舉例

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

我們能夠求出路徑

3.結論

采用floy算法能夠及時準確地獲取動態的耗時特征，對時間鄰接矩陣進行智能搜索，尋找到時間最少和路徑最短的最優路徑做出準確合理的應急決策。適合復雜和多點圖，可以通過程序重復使用，只需輸入相應的仞始數據即可，極大的提高在實際問題應用效率.

參考文獻：

[1] 李蔚萱.圖論[M].長沙：湖南科學技術出版社，1980.91-11.5

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

作者簡介：袁威威，（ 1982—），女，黑龍江黑河市人，黑河學院理學院數學系講師，從事數學與應用數學

基金項目：黑河學院科學技術研究項目《基于黑河中俄自由貿易園區背景下消防布控最優化問題的研究》，項目編號：KJQ201601