1黄勇2张航
1德清县消防救援大队2湖州市南太湖新区消防救援大队
湖州市 德清县 313200
摘要：文章首先对Dijkstra算法进行了概述，然后分析了Dijkstra算法的优化，其中包括存储结构的改进、搜索区域的限定、双向查找规划，最后基于优化的Dijkstra算法，文章对其开展了验证，无论是结点总数、计算时间，还是总的路程，都取得了极大的优化比例，以期能为相关人士提供参考。
关键词：最优路径；Dijkstra算法；灭火救援；搜索区域
引言：如今伴随经济的发展，再加上城市化的推进，使得很多方面更加集中化，比如城市建筑，一旦出现火灾的情况，极有可能带来很大的损失与伤亡。以灭火救援系统来分析，其中包含很多项的任务，而确定最佳出警路线是非常关键的，对于这一路线来讲，就是在出现火灾的情况下，消防车可以第一时间赶到现场，并且开展救援行为。当下对于最短路径算法来讲，已得到了较快的发展，一些算法得到了学者的大力研究，比如DNA以及Dijkstra算法。文章基于对Dijkstra算法的探究，给出了一种新的优化算法。
1.Dijkstra算法
这种算法最早出现于上世纪九十年代，由荷兰数学家提出来的，对于最短路径问题的解决，这是一种行之有效的算法，有着最为健全的理论，得到了大力的推广[1]。可对这一算法进行以下描述：（1）初始化。存在任意一个结点，用字母i来表示，若i不等于s，则d(i)趋向于正无穷，S(i)=unreached，否则d（i）等于零，S(i)=permanently labeled；（2）N趋向于T；（3）基于T的集合，从中选择一个结点，而且存在最小权，将其用k来表示，d（k)=min[d(j),j包含于T集合]；S（k)=permanently labeled；(4)若获取k等于t，则表明算法完成；（5）针对和k相连的任何一个结点，用字母j来表示，j包含于T，若d(j)大于d(k)以及l(k,j）之和，则d(k)以及l(k)之和倾向于d（j)，permanently labeled；（6）T等于集合k，而且倾向于T，转至步骤（3）。
2.优化Dijkstra算法
基于灭火救援系统，往往存在出警不够快速的问题，为有效处理这一问题，文章给出了最佳路径算法，对于该算法来讲，就是基于以往的Dijkstra算法，给出了多方面的改进。基于对搜索区域的限定，能够充分利用时间以及空间，避免出现浪费的现象，与此同时，通过对存储结构的改进，极大节约了存储空间，在文章的最后，对双向查找规则进行了探究，基于这一规则，显著降低了衔接数量，极大提升了搜索的效率。
2.1存储结构的改进
具体交通路网中，通常情况下，道路属于单行车道，在方向上存在一定的约束，基于此，可以借助有向图，进一步代表交通路网。另一方面，以交通路网来分析，针对每一个道路结点，对于所连接的路段而言，通常介于三个至五个之间，是一种稀疏图。这个时候，应当采取邻接表存储结构，这一结构有着一系列突出的优势，可以实现对空间的节省，便于对数据域进行扩充以及优化，存在的难度并不是很大，对于路网所存在的特征，可以得到更为充分的体现。在有向图中，存在结点Node类，由此对于道路交叉口，能够得到进一步的描述，另一方面，由于也存在弧Edge类，从而能够对路段进行描述。对于全部路段的距离来讲，也就是Edge的长度，通过对Mapinfo软件的使用，可以达到测距的目的，因为这一软件中包含着测距函数。对于每一个节点来讲，有着很多的数据信息，比如latitute。此外以每一条弧来分析，应当包括下述几点信息，也就是弧尾以及弧头ID，同时包含权值Weight。
2.2搜索区域的限定
对于算法效率的提升，可供选择的技术有很多，其中降低搜索规模是一种非常重要的技术。结合交通路网所存在的特点，针对椭圆约束，数学家给出了其的最佳路径算法，基于交通路网，确定一个起点，用大写字母S来表示，确定一个终点，用大小字母D来表示，基于中间的位置，将某一个节点记作N，通过绝对值SN，进一步表示起点以及终点之间的距离，用绝对值DN，进一步表示节点和终点之间的距离，则对于限制条件来讲，其为SN以及DN之和的绝对值小于M。这个时候，产生了一个搜索区域，而且属于椭圆形的。以这一方法来分析，一定程度上降低了搜索结点，实际上，并未使得算法效率得到提升，由于存在非线性运算，从而使得算法运算量变多了。针对平行四边形约束，我国学者给出了其的最佳路径算法，以这一种方法来分析，虽然不用进行非线性计算，实际上，也会使得计算量变多，由于椭圆要想变成多边形，不得不通过一系列的过程，比如平移的过程。
文章给出了一种区域搜索约束模型，这一模型较为容易达到，而且并不复杂，选取一个点，将其记为S，用大写字母D表示终点，则可以通过式子（1），对这一模型进行描述：D(S,i)以及D(i,D)之和小于kD(S,D),（k大于1）公式（1）,对于D(i,j)来讲，其是一种测距函数，源于Mapinfo软件，针对节点i以及节点j，用来代表两者的几何距离，通过地理坐标，能够进一步算出这一距离[2]。通过小写字母k，表示区域控制参数，而对于该参数以及搜索区域来讲，两者存在正相关的关系，换句话来讲，参数越大，区域也就越大，随之对于最优路径而言，搜出其的概率也就更大，所要进行的运算量也会变多，反之亦然，以最优路径来分析，搜出其的概率也就更小，所要进行的运算量也会变少。由此可以得知，选好区域控制参数是相当关键的，在此基础上，除了能够防止搜索区域偏多、结点偏多，也能够搜出最佳路径。
2.3双向查找规划
为了能够获取更快的搜索过程，文章基于对规则的考虑，给出了双向查找规则，将其运用于搜索系统。对于这一规则的思想来讲，就是基于两个端点，相同时间内进行搜索，在碰上之后，第一时间停止搜索，在此基础上，与单向搜索进行比较，能够增加一倍搜索速度，与此同时，路径也降低了二分之一[3]。通过D（S,i）来表示起点与结点的长度，用D（N，i)来代表终点与结点的长度，而且都属于最短路径。对于每一个结点来讲，均有着1个标号，也就是{D(S,i),P(S,j),D（N，i),P（N,i)}。
3.实验结果与分析
基于优化的Dijkstra算法，文章对其开展验证，对于试验所使用的数据来讲，均源于市区地图数据，在有效处理这些数据的基础上，获取相应的路网数据，而且是满足项目要求的。在这些数据中，路段数达到4516，而节点数达到3188。通过对试验的开展，基于改进前后的Dijkstra算法，获取两者的搜索结果，详情如表1所述，针对终点以及源点，结合两者存在的差异，在表1中列出两组数据。
表1 实验比较表
.png)
结论：文章结合以往的Dijkstra算法，给出了多个方面的改进对策，比如存储结构的改进，在优化这一算法之后，除了可以实现对存储空间的节省，很大程度上也能提升算法效率。对于文章的改进算法来讲，就是基于算法本身的，在具体的消防出警方面，能够起到一定的参考作用，不过在运用中，以最佳路径选取来分析，交通信息会对其造成较大的影响。伴随两种系统的持续进步，一是GPS，二是路径导航系统，探究更能满足实时交通的路径，存在很大的现实价值。
参考文献：
[1]李波.消防灭火救援最优路径算法研究[J].科技展望,2019,26(36):276.
[2]李超鹏.一种基于分层分析算法的实时最优消防应急救援路径算法[J].武警学院学报,2018,29(08):21-24.
[3]魏新宇. 消防灭火救援最优路径算法研究[D].西安科技大学,2018.
第一作者简介：姓名：黄勇（1975.10--）；性别：男，民族：汉，籍贯：浙江杭州学历：本科；现有职称：助理工程师；研究方向：消防监督管理和消防灭火救援
第二作者简介：姓名：张航（1985.8--）；性别：男，民族：汉，籍贯：吉林长春，学历：在职研究生；现有职称：助理工程师；研究方向：消防监督管理和消防灭火救援