袁威威

摘要：對消防車的路徑進行研究，確定最佳路線以提高滅火速度，縮短消防車抵達起火處時間，采用鄰接矩陣算法作為求解該問題的核心算法，尋找到時間最少和路徑最短的最優(yōu)路徑。

關鍵詞：鄰接矩陣；路徑優(yōu)化；有向圖

目前我國絕大多線路優(yōu)化，是憑借經(jīng)驗，也有少部分開始借助于信息技術實現(xiàn)線路的優(yōu)化工作。本文求解最佳路徑的過程即尋找最短時間和最短路徑，我們將路徑抽象為有向圖，利用有向圖的鄰接矩陣。尋找到時間最少和路徑最短的最優(yōu)路徑。

一、應用舉例

下面以某小區(qū)為例

假設將小區(qū)的十字路口設為v₁，v₂，v₃，v₄，v₅為有向圖的五個定點，小區(qū)的主干線為有向圖的邊，通過每條路的時間為有向圖邊的權。下面我們可以得到鄰接矩陣如下：

在小區(qū)中任意選取兩點v₃到v₂從加權值為根據(jù)圖二和距離矩陣D可知，當v₅發(fā)生災情時，消防站點v₃可到達v₅的路徑有：v₃-v₄-v₅，v₃-v₂-v₅，v₃-v₂-v₁-v₅，v₃-₂-v₄-v₅，-v₅，v₃-v₄-v₂-v₁-v₅等若干條路線，所以從v₂可到達v₄兩處之間的加權值最小的路線為v₃-v₄-v₅加權值為15，其他的兩兩任意兩頂點之間也可根據(jù)這樣的算法得出兩頂點之間的最短距離。

二、結論

采用鄰接矩陣算法能夠方便求出火災救援所需的最短路徑，如突發(fā)交通事故或是車輛擁擠引起的交通堵塞。這需受密切注意掌握最新交通動態(tài)信息，及時準確地獲取動態(tài)的路段耗時特征，并及時計算最佳行車路徑，做出準確合理的應急決策。如果路徑復雜本算法可以通過程序重復使用，只需輸入相應的仞始數(shù)據(jù)即可，極大的減少了人力資源的浪費。endprint