基于重大事故應急救援的最佳路徑選擇算法

賀繼東，程元棟

（1.安徽工貿職業技術學院，安徽 淮南 232007；2.安徽理工大學，安徽 淮南 232001）

隨著我國的社會經濟的高速發展，城鎮化率也越來越高，城鄉人口居住密度提高，各項安全事故事故頻頻發生，這些重特大事故造成的經濟財產損失以及社會影響越來越大，對構建和諧社會造成了巨大的負面影響.全國性的安全生產形勢的依然嚴峻，因此重大事故隱患排查和重點火險源管理已經受到各級政府的重點關注.因此，防止事故發生的關鍵在于對重點火險源研究辨識與事故后果的快速處理是做好重點火險源管理的前提條件，更是關鍵性步驟.

1 最短路徑問題

在圖中原節點到目標節點有多條路徑，則如何選擇最優路徑（即選擇路徑上各邊權值之和最小）.問題解法

邊上權值非負情形的單源最短路徑問題 —Dijkstra算法

邊上權值為任意值的單源最短路徑問題 —Bellman和Ford算法

所有頂點之間的最短路徑 —Floyd算法

2 邊上權值非負情形的單源最短路徑問題

問題的提出：

預設已經存在給有權值的有向圖，記為：D=（v，e），現在要解決的是算出從V點到D區域中的其它頂點的最短路徑.我們可以預定從V點到各點的權值大于或等于0.

如何求出類似模型的單源最短路徑，Dijkstra提出的算法是：按路徑長度的遞增次序，逐步產生最短路徑的.亦即：（1）求出長度最短的一條最短路徑，再以求出的最短路徑計算出次短路徑；（2）重復步驟（1），以此類推，直到從頂點V到其它各頂點的全部最短路徑求出為止.

圖1 Dijkstra逐步求解的過程

引入一個輔助數組dist[].dist[i]表示當前找到的從源點v0到終點vi的最短路徑的長度 (i表示輔助數組下表.

初始狀態：

若從源點v0到頂點vi有路徑，則用dist[i]表示該邊上的權值；

若從源點v0到頂點vi無路徑，則取dist[i]的值為+∞.

一般情況下，假設S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0出發，中間只經過S中的頂點便可到達的那些頂點Vx(VxV-S)的路徑中的一條.

每次求得一條最短路徑之后，其終點Vk加入集合S，然后對所有的Vi，V-S，修改權值dist[i].Dijkstra詳細算法如下：

a.初始化：S←{v0};

//n為圖中頂點個數

b.求出最短路徑的長度：

i?V-S;

S←SU{k};

c.修改：

,

對于每一個iV-S;

d.判斷：若S=V,則算法結束，否則轉b.

3 邊上權值為任意值的單源最短路徑問題

帶權有向圖D的某幾條邊或所有邊的長度可能為負值.利用Dijkstra算法，不一定能得到正確的結果.

若設源點v=0，使用Dijkstra算法，所得到的結果是不對的.

源點0到終點2的最短路徑應是0,1,2，其長度為2，它小于算法中計算出來的dist[2]的值.

Bellman和Ford發明了一種從源點一次繞過其它頂點，從而縮短到達終點的最短路徑長度的計算方法.

這種計算方法有一個前提限制條件，即圖中不能含有由權值為負的邊組成的閉合回路.

當圖不含由權值為負的邊組成有向閉合回路的時侯，則有個頂點的圖中任意兩頂點間假如存在有最短路徑，那么此路徑至多有條邊.

以上述理論為依據可以計算出從源點v到其它頂點u的最短路徑的長度值dist[u].

使用Bellman-Ford方法需要首先構造出一個最短路徑長度數組序列，分別記作.其中，認為是從源點到達終點的只通過一條邊最短路徑的長度；表示從源點開始最多通過兩條邊從而到達終點的最短路徑的長度，表示從源點開始最多通過不構成帶負長度邊有向回路的三條邊到達終點的最短路徑的長度，，表示從源點出發最多通過不構成帶負長度邊有向回路的條邊從而到達終點的最短路徑的長度.

Bellman-Ford算法的最終目標是為了求出.

可以采用遞推的方式求解出.

設已經求出distk-1[j],j=0,1,…,n-1,此即從該源點開始最多經過不構成帶負長度邊有向回路的條邊到終點最短路徑的長度.

從圖的鄰接矩陣里面能夠找到各個頂點到達頂點的距離Edge[j][u]，計算min{+}，能夠得到從源點繞過各個頂點，最多經過不構成帶負長度邊有向回路的條邊到終點最短路徑的長度.

用該值和進行比較，取值小者作為的值.圖的最短路徑長度：

4 所有頂點之間的最短路徑

問題的提法：已知一個各邊權值均大于0的帶有權值的有向圖，對每一對頂點Vi與Vj，要求出Vi與Vj之間的最短路徑以及最短路徑長度.

Floyd算法的基本思想：

定義一個n階方陣序列：

A(-1),A(0),…,A(n-1).(n=1,2,3……)

其中A(-1)[i][j]=Edge[i][j]；

A(k)[i][j]=min{A(k-1)[i][j]，

A(k-1)[i][k]+A(k-1)[k][j]},k=0,1,…,n-1

A(0)[i][j]是從頂點點Vi到Vj,中間頂點是v0的最短路徑的長度,A(k)[i][j]是從頂點點Vi到Vj,中間頂點的序號不大于k的最短路徑的長度,A(n-1)[i][j]是從頂點Vi到Vj的最短路徑長度.

弗洛伊德算法求解的結果:以Path(3)為例，對最短路徑的讀法加以說明.

從A(3)知，頂點1到0的最短路徑長度為a[1][0]=11,其最短路徑看 path[1][0]=2，path[1][2]=3，path[1][3]=1,表示頂點0<-頂點2<-頂點3<-頂點1;

從頂點1到頂點0最短路徑為<1,3>,<3,2>,<2,0>.Floyd算法允許圖中有帶負權值的邊，但不許有包含帶負權值的邊組成的回路.

〔1〕嚴蔚敏,吳偉敏.數據結構[M].北京：清華大學出版社，1999.12.

〔2〕蔡予經.數據結構教程[M].上海:復旦大學出版社，1994.

〔3〕劉南，劉仁義.WebGIS原理及其應用[M].北京:科學出版社，2002.

〔4〕楊東凱，吳今培.GPS車輛監控系統研究導航.1999(1).

〔5〕Morgan-Oven,G.J.Johnston,Differential GPS positioning Electronics&Communication Engineering journal.1995(l).

〔6〕威廉姆，等.企業應用集成[M].北京：機械工業出版社，2003.10-15.