基于重大事故应急救援的最佳路径选择算法

贺继东，程元栋

（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.