摘 要：采用Floyd算法作為求解該問題的核心算法，對時間鄰接矩陣進行智能搜索，尋找到時間最少和路徑最短的最優(yōu)路徑.及時確定最佳路線，以提高在實際問題應(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

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

1 Floyd算法核心思想

Floyd算法又稱為插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。通過一個圖的權(quán)值矩陣求出任意兩點間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[aij]n×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é)構(gòu)形式說明：

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

typedef char VertexType； //頂點類型

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

typedef struct{

VextexType vexs[MaxVertexNum] //頂點表

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

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

}MGragh；

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

void CreateMGraph（MGraph *G）

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

int i，j，k，w；

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

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

參考文獻：

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

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

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

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