賀繼東，程元棟

（1.安徽工貿(mào)職業(yè)技術(shù)學(xué)院，安徽 淮南 232007；2.安徽理工大學(xué)，安徽 淮南 232001）

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

1 最短路徑問題

在圖中原節(jié)點到目標(biāo)節(jié)點有多條路徑，則如何選擇最優(yōu)路徑（即選擇路徑上各邊權(quán)值之和最?。?問題解法

邊上權(quán)值非負(fù)情形的單源最短路徑問題 —Dijkstra算法

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

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

2 邊上權(quán)值非負(fù)情形的單源最短路徑問題

問題的提出：

預(yù)設(shè)已經(jīng)存在給有權(quán)值的有向圖，記為：D=（v，e），現(xiàn)在要解決的是算出從V點到D區(qū)域中的其它頂點的最短路徑.我們可以預(yù)定從V點到各點的權(quán)值大于或等于0.

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

圖1 Dijkstra逐步求解的過程

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

初始狀態(tài)：

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

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

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

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

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

//n為圖中頂點個數(shù)

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

i?V-S;

S←SU{k};

c.修改：

,

對于每一個iV-S;

d.判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)b.

3 邊上權(quán)值為任意值的單源最短路徑問題

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

若設(shè)源點v=0，使用Dijkstra算法，所得到的結(jié)果是不對的.

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

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

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

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

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

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

Bellman-Ford算法的最終目標(biāo)是為了求出.

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

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

從圖的鄰接矩陣?yán)锩婺軌蛘业礁鱾€頂點到達(dá)頂點的距離Edge[j][u]，計算min{+}，能夠得到從源點繞過各個頂點，最多經(jīng)過不構(gòu)成帶負(fù)長度邊有向回路的條邊到終點最短路徑的長度.

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

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

問題的提法：已知一個各邊權(quán)值均大于0的帶有權(quán)值的有向圖，對每一對頂點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的最短路徑長度.

弗洛伊德算法求解的結(jié)果:以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算法允許圖中有帶負(fù)權(quán)值的邊，但不許有包含帶負(fù)權(quán)值的邊組成的回路.

〔1〕嚴(yán)蔚敏,吳偉敏.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1999.12.

〔2〕蔡予經(jīng).數(shù)據(jù)結(jié)構(gòu)教程[M].上海:復(fù)旦大學(xué)出版社，1994.

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

〔4〕楊東凱，吳今培.GPS車輛監(jiān)控系統(tǒng)研究導(dǎo)航.1999(1).

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

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