一种基于城市应急系统的最短路径算法

《一种基于城市应急系统的最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第25卷第4期2007年12月广西师范大学学报：自然科学版JournalofGuangxiNormalUniversKy：NaturalScienceEditionVol_25No，4Dee．2007一种基于城市应急系统的最短路径算法襄桂琴“2，杨青1，黄祖锋1，王雪萍1(1．华中师范大学计算机科学系．胡北武汉430079l2．中原工学院计算机学院。河南郑州450007)摘要：城市应急系统(如119火警、110报警以及120急救等)要求在事故发生时，救援者能以最快的速度到达事故现场，而。最短路径”问题是满足该系统需求的关键技术之一。正是针对城市应急系统的

2、这种特点，以消防信息系统为例，在对现有最短路径算法分析研究的基础上，结合GIS技术的应用，提出了一种实时、高效的最短路径生成算法。关键词z城市应急系统，最短路径}消防信息系统；C-IS；Dijkstra算法中图分类号：TP301．6文献标识码：A文章编号：1001—6600(2007)04-0092—04城市应急系统关系到人们的生命财产和社会安全问题。该系统一般要求在1～3a的时间内计算出最佳路线，其算法直接影响到该种系统的效率。从网络模型的角度看，最短路径分析就是在指定网络中两结点间找一条阻碍强度最小的路径。根据阻碍强度的不同定义，最短路径不仅仅指一般地理意义

3、上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题在城市应急系统中就成为最快路径问题。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础(如TQQ、DKA、DKD等算法Ⅲ)，但是这些算法是以牺牲适当的时间效率来换取空间节省。目前虽然已经有了许多在此基础上的改进算法，但采用的是空间换时间来提高最短路径算法的效率[24]。本文针对城市应急系统的特点，在经典Dijkstra算法的基础上，从时间和空间的角度对最短路径算法进行了深入研究。1经典Dijkstra算法1．1算法原理求解最短路径问题的算法中，

4、Dijkstra算法“3是目前国内外一致公认的比较成功的算法。在Dijkstra算法中网络被抽象为图论中定义的有向图或无向图，用图的遍历方法搜索最短路径。在本系统中所讨论的最短路径算法主要针对平面有向图，其求解源结点s到目的结点t的最短路径的基本过程如下：①初始化网络。对所有结点i，如果睁％，则d(f)一+o。，S(i)=unreached，否则d(f)一o，S(f)=per—manentlylabeled；②丁一Ⅳ；⑧从丁中取出权值最小的结点k，d旺)=min[d(j)，J∈T3f5(^)=permanentlylabeled；④如果k=t，则算法结束；⑤对于

5、和k相连的每个结点j，J∈丁，如果d(j)>d强)+z旺，J)，则d(J)一d(^)+f(^，j)，S(j)一temporarilylabeled；⑥丁一丁一{h)，转到步骤③。’其中：d(i)表示源结点s到结点i的加权距离：，(i，J)表示连接结点i和J的弧的权值；5(j)表示结点j的状态，分为未标记(unreached)、临时标记(temporarilylabeled)和永久标记(permanentlylabeled)三种收稿日期：2007—04—20基金项目：国家重点实验室开放研究基金资助项目(SKLSE04—018)；湖北省重点科技公关项目(2005AA

6、l01C43)。通讯联系人：杨青(1966～)，女t湖北武汉人．华中师范大学副教授。Email：yangq@mail．ccnu．edu，C11万方数据第4期窦桂琴等：一种基于城市应急系统的最短路径算法状态。1．2算法分析针对城市应急系统的特点，经典I)ijkstra算法应用在该系统中的主要不足之处为。①该算法基于静态数学模型，投有考虑道路搜索过程中静态和动态的交通限制信息，计算出的最短路径没有实际意义}②在经典的Dijkstra算法中，每搜索一个结点需要重新比较和修改所有丁中的节点，浪费了大量的时间，在分析城市应急系统中的复杂网络时存在效率低下的问题I．③若采用

7、邻接矩阵的空间存储方式，则要记录所有节点的出度和入度信息，浪费了大量的存储空间。2优化后的最短路径算法从上文对Dijkstra算法的分析中可以看出，提高算法效率的关键技术是：如何从丁中快速选择权值最小的结点。因此，本文在Dijkstra算法的基础上提出一种快速搜索算法。2．1快速搜索算法原理采用编号不同的FIFO(FirstInFirstOut)队列存放所有临时标记结点的权值(考虑道路交通状况变化的加权长度值，用通过该路段的时间丁表示，且T为整数值)。其中，队列编号依据结点权值的大小(如按o，1，2，3，⋯编号)。则队列i中存放权值为i的结点。这样第一个非空的队

8、列一定存放的是当前权值最