高峰　秦堯　劉穆　嘎瑪次仁

摘? 要：最短路徑原本是圖論中的一個經(jīng)典算法文通，其目的是為了尋找圖中兩個定點間的最短距離。它的特點是以一個起始點為中心點向外擴展到每一個節(jié)點。隨著工程學在各行業(yè)的廣泛應用，最短路徑的應用已經(jīng)不止僅限于路程算法，它還擴展到交通工程、城市建設、計算科學等領域，該文旨在研究最短路徑算法的原理和代表算法——Dijkstra（迪杰斯特拉）算法，并將這種算法應用到警務工作中，希望在未來能將最短路徑算法應用到警力科學分布等工作中。

關鍵詞：最短距離? 算法? 路徑? 應用

中圖分類號：TP301 ? ?文獻標識碼：A 文章編號：1672-3791（2019）07（b）-0013-02

1? 最短路徑

線性規(guī)劃問題是大數(shù)據(jù)智能算法的有監(jiān)督學習范疇，即存在目標變量，需要探索特征變量和目標變量之間的關系，在目標變量的監(jiān)督下學習和優(yōu)化算法。最短路徑算法就是一個典型的線性規(guī)劃問題;令S為一個源點，T為目標點，Cij>0為路徑（i，j）為鏈路距離。于是，需要最小的Z，使

最短路徑算法開始于阻抗矩陣。阻抗矩陣中的數(shù)值表示兩個節(jié)點直接連接的阻抗，表示不直接連接。而后在即將分析的Dijkstra（迪杰斯拉特）算法，就是迭代計算從中心節(jié)點到其他節(jié)點的最短距離。雖然它的計算機效率并不突出，但是它的很多擴展算法或者改進算法仍然具有很強的應用性。

2? 迪杰斯特拉算法分析

Dijkstra算法（迪杰斯特拉）算法主要計算一個節(jié)點到其他節(jié)點的最短路徑，算法的核心是以起點為中心向外層擴散，途徑每一個點，直至擴散到終結點。雖然該算法需要遍歷計算所有節(jié)點，效率略低，但是卻能給出多種相似的解決方案，同時可以輔助其他算法，增加迪杰斯特拉算法效率。迪杰斯特拉算法作為最短經(jīng)典的經(jīng)典算法，應用范圍十分廣泛，如圖論、運籌學、數(shù)據(jù)結構等。

該算法的思想是，設有一個帶權的向圖，將圖中的頂點集合分為兩組，第一組為已求出最短路徑的頂點集合，第二組為其他未確定最短路徑的頂點集合，按最短路徑長度的遞增次序依次把第二組的頂點加入到第一組頂點中。利用遞歸算法一次將所有最短距離的點加入第一組集合，從而求出第一組頂點到第二組頂點的最短路徑頂點之和。如舉例說明，圖1是一個頂點集合圖。

根據(jù)上面算面解釋，設置兩個頂點集合，分別為S集合和U集合（見表1），根據(jù)迪杰斯特拉算法，我們可以使用數(shù)據(jù)結構節(jié)點算法，將一個頂點到其他頂點的所有路徑計算出來，最后比較權的大小，最終取權值最小的為最短路徑，如A到C點，有以下路徑：

A->B->C=7;A->B->D->C=8;A->E->B->C=10;A->E->D->C=13

根據(jù)上面的結果，我們發(fā)現(xiàn)A->E是最長路徑的兩種，迪杰斯特拉算法可以首先放棄經(jīng)過E點的可能性。

3? 最短路徑算法應用及開發(fā)技術

預案處置是一種警務力量安排的方法，依據(jù)多年警務事件實踐的經(jīng)驗和相關法律法規(guī)制度的規(guī)定，總結出針對各種類型案件的行之有效的工作方法和制定的處理案件流程，使得干警在各類不同案件的處理流程具有更強的程序化和規(guī)范化，節(jié)約警力資源，實現(xiàn)指導員、處警員、各警種的協(xié)調配置，最大限度發(fā)揮處置效果[2]。

預警模塊是根據(jù)公安機關長期經(jīng)驗總結出的各類案件、事件的處理方法，并將這些方法設置成未來處理相關案件的制度流程，并最終形成預案制度。預案可以分為：群體性事件處理預案、火災爆炸處理預案、自然災害處理預案、化學危險品處置預案等。

首先，當接警中心接到報案后，會根據(jù)案件的發(fā)生地點甚至是地理坐標位置作為查詢條件，然后根據(jù)事件的具體情況選擇輸入一個攔截半徑，以攔截半徑為圓面查詢該范圍內(nèi)的警力裝備情況和相關屬性信息。

其次，輸入預案信息，調出方案，根據(jù)情況對比進行調整。然后，生成最短路徑線路，根據(jù)第一步的攔截半徑圓面合理通知警力和使用裝備，最終形成理想的路徑合理安排調度。為了確保事件現(xiàn)場的快速處置，還可以根據(jù)線路的長短安排巡警控制交通，甚至是幾條線路的交通;出警的原則是“路線固定、盡量集中”。

根據(jù)以上的步驟，我們可以選用ArcGIS Engine作為最短路徑的地理信息系統(tǒng)的開發(fā)引擎，ArcGIS Engined的功能十分強大，它既支持簡單的地圖應用，同時又滿足對地理信息系統(tǒng)較高要求的分析應用。為了能夠展現(xiàn)大數(shù)據(jù)分析中隨需而變的理念，ArcGIS Engine針對程序員開發(fā)的需求增加了開發(fā)包軟件，能在開發(fā)中很容易地實現(xiàn)動態(tài)制圖和隨需要變化的GIS功能，ArcGIS Engine還增加了構建定制地圖的個性需求，從而為地理信息系統(tǒng)做出了非常好的解決方案[3]。ArcGIS Engine為了更好地靈活支持工業(yè)標準的編程環(huán)境，開發(fā)出更加睿智的地圖界面，ArcGIS Engine在組件中增加協(xié)同關系組件，使地理信息系統(tǒng)數(shù)據(jù)和其他信息無縫對接。豐富的API接口幫助文檔和示例代碼使開發(fā)者不必擔心開發(fā)語言不同會是開發(fā)的障礙;但是ArcGIS Engine開發(fā)包絕不是給普通用戶使用，它更多是為了供開發(fā)編程人員使用，具有很強的專業(yè)性。程序員使用ArcGIS Engine開發(fā)出的應用軟件，可以跨平臺使用，既可以構建在基于Intel架構的微軟視窗系統(tǒng)，也可以輕松部署在大型服務器系統(tǒng)，如UNIX和Linux上，程序員不必將過多的精力放在擔心不同系平臺的應用效果上，而是更好地將更多的聰明才智集中在軟件的應用開發(fā)上。

4? 結語

最短路徑的應用領域廣泛，既可以使用在警務的人員調配、車輛調度等領域，還可以使用在上下班高峰期的車輛紅燈調低的交通疏導上，同時還可以輔助其他算法，如克里金插值算法，不僅得到點、線圖形，還能根據(jù)需要設置一個面里的相關值應用，因此最短路徑算法在預警應用領域非常廣泛。

參考文獻

[1] 李崇貴，陳崢，豐德恩，等.ArcGIS Engine組件式開發(fā)及利用[M].北京：科學出版社，2012.

[2] 姚遠.公安警務調度系統(tǒng)的研究與實現(xiàn)[D].上海交通大學，2008.

[3] 許軍.地理信息系統(tǒng)的應用[D].北京郵電大學，2009.