[分享]GIS中最短路径的实现

　　1 引言

　　随着地理信息产业的建立和数字化信息产品在全世界的普及，地理信息系统将深入到各行各业甚至各家各户，成为人们生产、生活学习和工作中不可缺少的工具和助手。

　　地理信息系统中网络分析功能的主要目的是对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化。

　　最短路径问题是地理信息系统网络分析中的最基本最关键的问题，在交通网络结构的分析，交通运输线路的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。

　　关于最短路径问题，目前为人们所公认的最好求解方法，是1959年由E.W.Dijkstar提出的标号法，但具体实现中在存储空间及运行效率上还存在着一定的问题。

　　本文从图形数据的存储结构及最短路径顶点的搜索策略两个方面对Dijkstra算法进行了改进，提出了一种基于矢量角度的最短路径搜索算法。

　　2 道路网络数据结构

　　构造类似于面向对象的数据结构存储网络图：

　　Public Type Mynode（点结构）

　　　　Dim NodeID As Integer '节点ID，唯一标识节点

　　　　Dim AdjoinNum As Integer '邻接弧段数量

　　　　Dim AdjoinArcID() As Integer '邻接弧段ID

　　　　Dim AdjoinNodeID() As Integer '邻接节点ID

　　　　Dim AdjoinClamp() As Double '指向邻接节点的矢量的角度

　　End Type

　　Public Type MyArc（弧结构）

　　　　Dim ArcID As Integer '弧段ID，唯一标识弧段

　　　　Dim Length As Double '弧段长

　　End Type

　　其中节点对象中的三个数组大小在初始化时利用邻接弧段数量设置大小，因此对应不同的节点对象其大小是不固定的，使用此种结构，对于有向图不会造成数据的冗余，而对应于无向图也仅多存储了一倍的弧段ID，邻接节点ID及矢量角度，相对于经典Dijkstra算法来说，需要的存储空间仍较小。对于弧段对象来说，其中的Length可以设置为弧段长度，也可根据需要设置为时间、费用等相应的权值。

　　3 算法原理

　　由两点之间直线最短的定理，构造一条理想最短路径（如图一中的AB），这条直线段一定是A、B两点间弧段中距离最短的一条。但实际上这条直线段作为一段道路存在的可能性极小，但这条从起点到终点的直线段却代表了一个路线的趋势，从概率的角度，顺着这个方向的某些路段的集合组成最短路径的可能性较大。

　　　　　　　　　　　　　　　　　　

　　以矢量夹角标量值做为最短路径顶点选取的第一要素。

　　如图一，求解A、B两点间的最短路径。∠1为矢量Aa与矢量AB间夹角的标量值，当前节点的每个邻接节点都对应一个角度标量值，按照标量值的正负值大小，构造标识分别为正负的两个队列，两个队列均根据节点对应标量值的绝对值从小到大进行排序。

　　分别从正负两个队列中选出排在最前位的节点，加入到最短路径树中。

　　除第一次搜索外，其余过程中都需要判断搜索到的节点是否已存在于最短路径树中，如果该节点已存在于最短路径树中，则需要比较本次搜索过程结束后该节点信息与对应的最短路径树节点信息。

　　假设在第m次搜索过程中已确定指向节点S的树节点Sm，之后在第n次（n ≥ m）搜索得到的树节点Sn再次指向网络图中节点S。

　　当Sn的Length值大于Sm的Length值时，在Sn处停止搜索，如图二所示。

　　　　　　　　　　

　　当Sn的Length值小于或等于Sm的Length值，如图三所示，将Sm之下的所有树节点移动到Sn之下，并依据Sn的Length值对应修改原Sm之下所有树节点（图示方框中所有树节点）的Length值。

　　　　　　　　　　

　　4 算法实现

　　本算法在武汉市经济开发区道路网络图上得到实现。武汉市经济开发区道路网络图中共有节点371个，边653条。在ArcMap的VBA环境中，通过VB＋ArcObjects的编程方式，由VB实现算法逻辑控制，ArcMap管理图形的显示与控制，实现在图形窗口中动态显示求得的最短路径以及选取组成最短路径的路段集合的过程。实现流程图如下：

　　　　　　　　　　　　

　　在武汉市经济开发区道路图上任意选取六个节点，分别进行三次最短路径求解的实验，得出的参数如下表：

　　
　 　其中：

　　Arc Number表示的是最短路径经过的弧段数，单位为段；

　　Node Number表示的是最短路径经过的结点个数，单位为个；

　　Path Length表示的是最短路径的长度，单位为米；

　　Modification在本文算法中表示的是求解过程中树节点修改次数，在Dijkstra算法中表示的是求解过程中节点标号的修改次数；

　　Time表示的是求解最短路径花费的时间，单位为秒。

　　由上表可以看到，在求解最短路径的过程中本文讨论的算法与传统的Dijkstra算法，最大的差别在于Modification。

　　由于文中探讨的算法在求解最短路径过程中具有起、止点的方向性趋势，每次搜索过程中仅考虑当前节点的邻节点，故修改次数较小；而在Dijksra算法中，每次搜索过程中都将遍历所有未确定永久标号的节点，故修改次数较大。

　　文中探讨的算法求解过程简单，速度快，求得的最短路径与用Dijkstra算法求得的最短路径相同或相近，所以该算法具有一定的实用性和可操作性。

　　5 结论

　　在对于搜索技术性能评价的时候，在各种不同的情况下有着不同的要求，并非只注重最优解，而是注重在一定条件下的非劣解。虽然本文讨论的算法在道路较不规整时求得的最短路径可能有一定的误差，但是与最短路径的最优解相近，而非劣解，且在其他情况下都能求得最优解，求解的速度快，故具有一定的实用性和可操作性。

　　由于实际情况的复杂性，为了减小算法在求解时产生的误差，使得算法有更好的适应性，有进一步研究道路网络图中拓扑关系的必要，增加矢量条件，真正使最短路径的求解过程简单快速，结果准确可信。