公安行业综合指挥调度系统GIS应用中实时最佳路径算法研究

　　[摘要]：根据报警电话(或突发事件)的地理位置及其周边交通信息获得最近的出警点及最佳路径,是现代公安综合指挥调度系统GIS应用中的一个现实难题。笔者对Dijkstra经典算法进行了深入研究，提出了一种Dijkstra优化算法，并结合我国交通网络的特点建立了基于数据库技术的实时最佳路径查询分析模型。理论分析和实验对比均证明,该算法与模型可以节约大量的内存且效率很高。

　　近年来，GIS技术迅猛发展，其动态信息交互显示为其在现代公安行业综合应用中的引进和采用创造了前提。GIS技术提供的高质量地理信息画面为公安内部对突发事件的处置决策提供了更直观的信息。当前，GIS在公安领域中的应用主要有：110、122、119报警服务系统，突发事件应急处置预案决策系统，公安信息数据的分析，模拟演练系统等[1]。其中，GIS在110、122、119报警系统中运用得最早，也是最能体现成果的技术，关键技术就是其网络分析功能。

　　在公安行业GIS应用中，确定报警点与出警点之间的最短路径是GIS技术的一项重要应用。110、122、119报警等应急系统，一般要求尽快计算出到事发地的最佳路径，甚至还要求在行车过程中实时计算出车辆前方的行驶路线，这就要求最短路径问题的解决必须是高效的。

　　常用的最短路径算法有Dijkstra算法和Floyd算法等，由于受当时计算机硬件水平的限制，这些算法采用的数据结构及其实现方法将空间存储问题放在首位，以牺牲适当的时间效率来换取空间的节省，处理复杂交通网络时常存在很多问题，且效率较低[3]。目前，空间存储已不是考虑的主要问题，因此有必要对已有的算法进行改进，可利用空间换时间来提高效率。

　　1.实时最佳路径分析的总体思想

　为了实现公安地理信息系统（GIS）要求的实时性，解决复杂交通网络的最佳路径问题，本文采用了基于数据库技术的实时最佳路径查询分析模型，其总体思想是：利用最短路径算法计算所有点对点间的最优路径并存入数据库中，当需要计算两个路口间的最佳路径时只要从数据库中查询获取并在地图上渲染即可。

　　2.最佳路径分析的空间数据模型

　　交通网络与简单有向拓扑网络不同，而最佳路径分析对数据的要求比较严格，因此首先要建立交通网络模型，并建立网络拓扑关系，最佳路径分析的基本流程如图1所示。

　2.1交通网络模型的建立

建立交通网络模型包括两方面的内容：交通道路与交通路口的抽象。

　　1)交通道路的抽象

　　交通道路的抽象有一项基本原则：取道路中心线，两路口间的道路矢量化后为单独的弧段。交通道路的抽象要考虑以下三个影响因素：道路的等级、道路的通行条件限制和防护栏的限制。其中前两项可以通过属性字段进行设置，而防护栏的限制就需要在矢量化时进行细致的处理。

　2)交通路口的抽象

交通路口的抽象比较复杂，主要考虑的问题是车辆的拐向限制，可通过以下方式进行抽象：将道路抽象为单行线，或增加路口。

　　2.2交通网络拓扑关系的建立

　　要进行最佳路径分析，必须将交通网络实体抽象为图论中的网络图，这就需要为网络实体建立拓扑关系。而在MapInfo中各对象间不存在任何关系，建立空间拓扑关系的唯一办法就是在相应的表结构中扩展必需的字段[4]。最佳路径分析所需要的拓扑属性有：弧段的标识码和弧段的首、末结点标识码，建立拓扑关系关键就是将这些属性匹配。

　　建立交通网络拓扑关系的算法思想是：得到线段的两端点坐标值和路段的长度，分别在两端点创建一个圆，如果圆没有与其它的点对象相交，则在路口表中新增一个点，并将路段的起始点和终止点的代码分别设为这两端点的代码值。最后将以上所有信息都存放到表中。

　　在该算法中，圆半径会对结果造成重大影响。如图2，因为圆半径过大，造成弧段的首、末结点号相同，在最佳路径分析中按零长度计算，以致造成较大误差。但是如果半径太小，又会降低算法对于人为误差的处理能力。因此要根据实际情况慎选圆半径。

　
　　3.Dijkstra优化算法及算法比较

　　3.1Dijkstra经典算法及其存在的问题

　　Dijkstra算法按长度递增次序产生最短路径，每次只能计算单源最短路径，通过优化可解决全源最短路径问题，是目前多数系统解决最短路径问题采用的理论基础。
　　Dijkstra算法相当有效，但仍存在着一些问题有待改进。
　　1)存储问题
　　Dijkstra算法采用二维数组进行计算，但在实际应用中平均有n2-e2个空间浪费了，其中n为结点个数，e为图的平均出入度。
　　2)结点搜索方式
　　Dijkstra算法的核心步骤是从未标记点集中选择权重最小的弧段，这是一个循环执行过程[5]。未标记点是以无序的形式存放在数组中的，所以要选择权重最小的弧段就必须把所有的点都扫描一遍。
　　3.2Dijkstra算法的优化
　　针对Dijkstra算法存在的问题，结合交通网络的特点，笔者对Dijkstra算法进行了优化。Dijkstra优化算法主要针对结点搜索方式，通过改变存储形式来实现。该算法使用了一个顺序邻接链表存储结点信息，如图3所示，链表结点按弧段的权重从大到小排列，因此权重最小的弧段存放在链表的尾结点，直接获取即可。

　

　　算法的基本思想如下（G为图的邻接表，G[V]表示第V个链表，ShortDist是一个单链表，Final[]用以标识结点类型，PathMatrix[]记录路径信息）：
　　1)构建图结构G，将弧段信息按路段的权重由大到小的顺序存储。
　　2)初始化起始点V到其它点的信息。
　　3)获得G[V]链表中的最后一个结点，假设该结点号为Vj，若Final[j]为真，则表示该结点已经计算过了，可以将其真接删除；如果Final[j]为假，该结点就是权值最小的顶点。将Final[j]置为真，PathMatrix[j]= PathMatrix[j]+ "j"。
　　4)修改从Ｖ出发到Vj可以直接连通的任一点顶点Ｖk可达的最短路径长度。方法如下：得到G[j]链表中的结点信息，即依附于顶点Vj的弧段信息，如果ShortDist[j]+G[j]->[k][k]，PathMatrix[k]= PathMatrix[j]+ "k"，就将它们插入到G[V]链表中。
　　5)重复操作3、4共n-1次，即可完成一次单源最短路径分析。
　　在Dijkstra优化算法中，关键在于邻接表中插入结点这一操作。在顺序邻接表中插入结点的方法如下：首先判断路段的起始结点，如果路段的起始点标记为Vi，则把路段信息插入到邻接表中第Vi个数据项指

示的单链表中，从单链表头开始遍历，比较结点的权值大小，遍历过程中可能会遇到以下几种情况：1）如果插入结点Vk的权值比结点Vj的权值小，则与Vj的下一个结点进行比较；2）如果插入结点Vk的权值比结点Vj的权值大，则将结点Vk插入到结点Vj前面，见图4a；3）如果遍历查找到终止结点号与插入结点Vk相同，则比较他们的大小，假如插入结点Vk的权值较小，则删除链表中的结点Vj再找到合适的位置插入Vk，假如插入结点Vk的权值较大，则退出，见图4b，但是可能在链表末尾找到一个结点号相同的Vj，这就需要一个辅助指针Vi指向Vj，再删除结点，以避免指针指向未知地址，如图4c；4）如果遍历整个链表都未找到比Vk权值小的结点，则直接在链表末插入，如图4d。

　
　　3.3Dijkstra优化算法与Dijkstra算法的比较

　　Dijkstra优化算法相较于经典Dijkstra算法有很大的改进，本节将比较这两种算法。

　　这两种算法对于GIS 网络图中各种权值的最短路径分析都是适用的，且考虑了道路单双向问题，对具有道路转变限制的问题具一定的解决能力。

　　在数据结构上，Dijkstra优化算法使用了一个顺序邻接链表存储图结构和一个邻接链表暂时存放起始点到其它结点的路径。Dijkstra算法则使用了一个二维数组来存放所有结点间的路径和一个一维数组存放所有结点间的最短路径。

　　在空间上，Dijkstra优化算法的空间复杂度为O(3m+2n)， Dijkstra经典算法的空间复杂度为O(n2+3n)。

　　在时间上，Dijkstra优化算法的时间复杂度为O(e*(e-1)*n2/8)， Dijkstra经典算法的时间复杂度为O(2n2)。

　　Dijkstra优化算法是一种针对交通网络图（即平均出入度e∈[2,5]）的特点而提出的改进方法，节省了大量的内存空间而且效率很高。若网络图中顶点的平均出入度较大，Dijkstra优化算法就会退化，算法的运行效率就会受到较大影响。

　　4.结论

　　本文针对交通网络的特点，以Dijkstra单源最短路径算法为理论基础，利用顺序邻接链表存储结点信息，改变了结点搜索方式，从而实现了Dijkstra经典算法的优化。通过理论分析和比较，Dijkstra优化算法比Dijkstra经典算法在内存空间和运行效率上都有了很大的改进，而通过多次实验对比，采用不同数据或电脑配置，也证明了该优化算法是高效和稳定的。

　　参考文献

　　[1]张虎,施一民. 基于MapX的公安110 报警系统的设计与实现[J]. 测绘通报.2004,(9):23-25

　　[2]乐阳,龚健雅. Dijkstra 最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报. 1999,24(3):209-212

　　[3]朱晓青, 周涛, 张海堂. Mapinfo 中道路拓扑与最优路径的研究[J]. 测绘学院学报，2001. 18(2):133-135

　　[4]夏松,韩用顺. GIS中最短路径算法和改进实现[J]. 测绘通报，2004,(9):40-42

李春芳:益阳市道路交通管理科学技术研究所
毛先成:益阳市道路交通管理科学技术研究所
郭瑶琴:中南大学GIS研究中.心

示的单链表中，从单链表头开始遍历，比较结点的权值大小，遍历过程中可能会遇到以下几种情况：1）如果插入结点Vk的权值比结点Vj的权值小，则与Vj的下一个结点进行比较；2）如果插入结点Vk的权值比结点Vj的权值大，则将结点Vk插入到结点Vj前面，见图4a；3）如果遍历查找到终止结点号与插入结点Vk相同，则比较他们的大小，假如插入结点Vk的权值较小，则删除链表中的结点Vj再找到合适的位置插入Vk，假如插入结点Vk的权值较大，则退出，见图4b，但是可能在链表末尾找到一个结点号相同的Vj，这就需要一个辅助指针Vi指向Vj，再删除结点，以避免指针指向未知地址，如图4c；4）如果遍历整个链表都未找到比Vk权值小的结点，则直接在链表末插入，如图4d。

　
　　3.3Dijkstra优化算法与Dijkstra算法的比较

　　Dijkstra优化算法相较于经典Dijkstra算法有很大的改进，本节将比较这两种算法。

　　这两种算法对于GIS 网络图中各种权值的最短路径分析都是适用的，且考虑了道路单双向问题，对具有道路转变限制的问题具一定的解决能力。

　　在数据结构上，Dijkstra优化算法使用了一个顺序邻接链表存储图结构和一个邻接链表暂时存放起始点到其它结点的路径。Dijkstra算法则使用了一个二维数组来存放所有结点间的路径和一个一维数组存放所有结点间的最短路径。

　　在空间上，Dijkstra优化算法的空间复杂度为O(3m+2n)， Dijkstra经典算法的空间复杂度为O(n2+3n)。

　　在时间上，Dijkstra优化算法的时间复杂度为O(e*(e-1)*n2/8)， Dijkstra经典算法的时间复杂度为O(2n2)。

　　Dijkstra优化算法是一种针对交通网络图（即平均出入度e∈[2,5]）的特点而提出的改进方法，节省了大量的内存空间而且效率很高。若网络图中顶点的平均出入度较大，Dijkstra优化算法就会退化，算法的运行效率就会受到较大影响。

　　4.结论

　　本文针对交通网络的特点，以Dijkstra单源最短路径算法为理论基础，利用顺序邻接链表存储结点信息，改变了结点搜索方式，从而实现了Dijkstra经典算法的优化。通过理论分析和比较，Dijkstra优化算法比Dijkstra经典算法在内存空间和运行效率上都有了很大的改进，而通过多次实验对比，采用不同数据或电脑配置，也证明了该优化算法是高效和稳定的。

　　参考文献

　　[1]张虎,施一民. 基于MapX的公安110 报警系统的设计与实现[J]. 测绘通报.2004,(9):23-25

　　[2]乐阳,龚健雅. Dijkstra 最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报. 1999,24(3):209-212

　　[3]朱晓青, 周涛, 张海堂. Mapinfo 中道路拓扑与最优路径的研究[J]. 测绘学院学报，2001. 18(2):133-135

　　[4]夏松,韩用顺. GIS中最短路径算法和改进实现[J]. 测绘通报，2004,(9):40-42

李春芳:益阳市道路交通管理科学技术研究所
毛先成:益阳市道路交通管理科学技术研究所
郭瑶琴:中南大学GIS研究中.心