賀繼東，程元棟

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

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

1 最短路徑問(wèn)題

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

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

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

所有頂點(diǎn)之間的最短路徑 —Floyd算法

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

問(wèn)題的提出：

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

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

圖1 Dijkstra逐步求解的過(guò)程

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

初始狀態(tài)：

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

若從源點(diǎn)v0到頂點(diǎn)vi無(wú)路徑，則取dist[i]的值為+∞.

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

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

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

//n為圖中頂點(diǎn)個(gè)數(shù)

b.求出最短路徑的長(zhǎng)度：

i?V-S;

S←SU{k};

c.修改：

,

對(duì)于每一個(gè)iV-S;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

用該值和進(jìn)行比較，取值小者作為的值.圖的最短路徑長(zhǎng)度：

4 所有頂點(diǎn)之間的最短路徑

問(wèn)題的提法：已知一個(gè)各邊權(quán)值均大于0的帶有權(quán)值的有向圖，對(duì)每一對(duì)頂點(diǎn)Vi與Vj，要求出Vi與Vj之間的最短路徑以及最短路徑長(zhǎng)度.

Floyd算法的基本思想：

定義一個(gè)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]是從頂點(diǎn)點(diǎn)Vi到Vj,中間頂點(diǎn)是v0的最短路徑的長(zhǎng)度,A(k)[i][j]是從頂點(diǎn)點(diǎn)Vi到Vj,中間頂點(diǎn)的序號(hào)不大于k的最短路徑的長(zhǎng)度,A(n-1)[i][j]是從頂點(diǎn)Vi到Vj的最短路徑長(zhǎng)度.

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

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

從頂點(diǎn)1到頂點(diǎn)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].北京：機(jī)械工業(yè)出版社，2003.10-15.