浅析Ｄｉｊｋｓｔｒａ最短路径算法在消防力量调集中的应用

刘　蕊　李　峰

摘要：文章从我国的火灾形势出发，以优化城市道路交通网中路段的权值为出发点，结合消防工作实际情况的特点，介绍了消防力量调集路径最优指标的选取方案，着重分析了Dijkstra最短路径算法的基本原理，并给出了算法优化方案。优化后的算法能够有效降低Dijkstra算法的时间复杂性，提高运行效率。实例应用表明，该方法兼具灵活性和实用性，能够满足消防灭火救援工作中实现消防力量优化调集的要求。

关键字：Dijkstra算法；最短路径；力量调集

中图分类号：TP311.1文献标识码：A文章编号：1009-2374（2009）02-00734-02

火灾是城市中较为频繁的灾害，其损失经常是巨大的。如果在火灾发生后的短暂时间内，消防力量能有效地控制火势，则火灾损失会大大减少。火灾的经济损失有很大的波动性，它与火灾的持续时间、燃烧物的类别、过火面积等因素有关。但是，对于一个具体的建筑物子系统，火灾损失的变化主要与火灾持续时间有关。消防队必须在15分钟内达到火场出水，这是基于我国通讯、道路和消防装备的实际情况以及对大量的火灾案例的分析得出的，这样才能有效地扑救火灾并防止火势继续蔓延。但在实际工作中往往由于消防资源调度不当等各种迟滞因素使得消防人员不能尽早赶到火灾事故现场，丧失了对早期火灾扑救的良好时机。为将损失降低到最低程度，消防部门面临的问题是如何迅速调动消防救援力量到达事故地点及时扑灭火灾，这就涉及到调集路径选取的问题。地理信息系统中的DIJKSTRA最短路径算法可以很好的解决这个问题。

一、消防力量调集路径最优指标的选取

Dijkstra算法在通用路径选择算法中，对最短路径的衡量标准是通过计算路径的边权来决定的。如何确定边权，使设定的边权更符合系统实际的需要，是建立算法参数标准的重要因素，其值设定的好坏，直接决定了算法的适用性。在实际城市交通网络中，道路长度最短的路径不一定是耗时最短的。如何设定最优路径的标准也是设计权值的重要前提。影响消防车辆到达火灾事故现场时间的因素很多，如车流量、车道数、时间段、路面状况等等。将救援时间最短作为最优目标，相应的道路权重如何标定是一个非常值得研究的问题。一般而言，确定以出行时间度量的道路权重建议采用以下方案：

引进表征路段行程时间与交通流量之间关系的路阻函数模型以及交叉口延误模型，计算当前时段的路段行程时间及交叉口延误，以此确定道路权重。这样既考虑了交通流的特性，体现了实时因素，又在当前基础设施状况允许的范围内。该方案较好地反映了现实情况，且技术上切实可行，综合考虑了实用性与可行性。

因此，本文选取时间作为路径权值的最优指标，并用路阻函数求出道路交通网中各路段的权值，在此基础上利用DIJKSTRA最短路径算法实现消防力量调集的最优化。

二、Dijkstra最短路径经典算法及分析

（一）问题定义

我们讨论的问题是城市消防单源点的最短路径，即对于给定带时间权的无向图G、源点Vi和终点Vj，求得源Vi和终点Vj之间路径中的最短路径。

（二）Dijkstra 算法

我们设定一个辅助向量D[i]。D[i]表示当前从源点V到每个终点Vi的最短路径的时间长度。它的初始值为：如果V到Vi有直接相联的路径，则D[i]为这条路径的时间权值。否则，设定D[i]=∞，设D[j]=min{ D[i]|Vi∈V }。显然，D[j]为从V出发的一条最短路径。下一条次短路径的长度一定是：D[j] = min{ D[i]|Vi∈V-S }，其中S为已求得最短路径的终点的集合。根据对以上求出的最短时间路径序列的查询，我们可得出两地的最短时间路径。

（三）Dijkstra算法优化及分析

1．优化Dijkstra算法的思路

根据以上对Dijkstra算法的分析，我们可以知道，当n较大时，Dijkstra算法的运行时间急剧增加。如果能有效地减小n值，就能大大地减少运行时间，提高效率。基于以上考虑，为了有效地减小n值，我们把需要计算两节点最佳时间路径的公路网图分成若干个子图，对每个子图分别采用Dijkstra算法进行计算，再把每段计算的节点连接起来，就是我们需要的结果。在把一个图划分成若干个子时遵循以下原则：

（1）根据几何中关于两点间的时间距离最短的原理，我们用直线连接源点和终点，最佳路径一般情况应在这条直线附近。划分子图应顺着这条直线来进行。

（2）每个子图应尽可能均匀，即每个子图的节点数基本上接近。否则，本优化算法效果不明显。如果在划分子图时，每个子图的节点数相差悬殊，则子图查找效率低，造成优化算法效果不明显。

（3）划分子图尽可能使图的边接近连接源点和终点这条直线附近，以减少重复计算的次数，提高命中率。

2．优化Dijkstra算法的描述

（1）依据以上原则，把一个公路网图划分成若干个子图。

（2）划分时，每个子图的节点最接近连接源点和终点的直线。

（3）分别对每个子图采用Dijkstra算法进行计算。

（4）我们把相邻子图的源点和终点分别进行核对。如果前一子图的终点就是后一子图的源点，那么我们连接这两段，并且认为这段就是最佳路径中的一段；如果前一子图的终点不是后一子图的源点，那么我们修改前一子图的终点，把它定义成后一子图的源点，再对前一子图采用Dijkstra算法进行计算，同时，修改后一子图的源点，把它定义成前一子图的终点，再对后一子图采用Dijkstra算法进行计算，连接这两段。根据计算结果，取这两段中权值最小的一段，作为最佳路径中的一段。

（5）重复以上步骤，直到找出连接源点和终点的最佳路径。

采用以上方法找出的路径不一定是最短路径，但它是最接近或就是最短路径。

三、结语

通过对消防力量调集最短路径算法的研究，了解Dijkstra基本算法和优化算法。同时，我们也注意到，优化Dijkstra算法适应等级较高的公路，对于等级较低的公路，若公路线型过于弯曲，可能效果不理想。

参考文献

[1]黄伟东，万义玲．公路网最佳路径算法的研究[J]．南昌大学学报（工科版），2003，（3）．

[2]魏新宇．消防灭火救援最优路径算法研究[D]．西安科技大学，2006，（4）．

[3]李斌．基于GIS的城市消防信息系统[D]．贵州大学，2006，（5）．