最短路径分析在MapInfo中的实现

胡殿常，王晋秀

(解放军1206地理信息中心，河北廊坊065000)

最短路径分析在MapInfo中的实现

胡殿常，王晋秀

(解放军1206地理信息中心，河北廊坊065000)

采用MapBasic语言，对MapInfo进行功能扩充，在MapInfo中实现最短路径分析。程序首先完善路网表结构，增加路网拓扑所必需的字段;然后进行路网拓扑，建立拓扑关系，并在此基础上采用Floyd算法实现最短路径分析。

MapInfo;最短路径分析;MapBasic;Floyd;GIS

一、引 言

近几年，GIS在我国快速发展，并随着计算机软、硬件技术的不断成熟，这一高新技术已由研究室走向实际应用领域，融入了人们的日常生活。电子导航是最重要的应用之一，其中最短路径分析是构成电子导航的灵魂。此外，最短路径分析在通信网络、电力网络等地理信息系统中也有着广泛的应用。

MapInfo是一款桌面地理信息系统软件，以简单易学、性能稳定等特点，在GIS领域占有一定优势。由于其数据结构相对简单，无拓扑关系，因此软件中没有提供诸如最短路径分析等基于拓扑关系的功能。但MapInfo提供了强大的二次开发接口，很多功能可通过二次开发解决。

MapInfo提供了3种二次开发方法:MapBasic语言、MapX组件和OLE技术。MapX和OLE适合开发独立的应用系统，而MapBasic比较适合MapInfo功能扩展编程。MapBasic是MapInfo自带的二次开发语言，是一种类似Basic的解释性语言，利用Map-Basic编程生成的*.mbx文件可在MapInfo软件平台上运行。本文主要介绍采用 MapBasic语言在MapInfo中实现最短路径分析的方法。

二、完善表结构

在MapInfo中，路网或其他网络都以“线”的方式表现。每条线有“起点”和“终点”，统称“端点”。线与线首尾相连，构成路网，连接处称为“顶点”或“节点”。然而，路段编号(ID)、路段起止点、路段长度等属性，并没有被记录。因此，首先要完善表结构，增加字段，记录拓扑信息。

增加的字段有 LineID、Fnode、Tnode、Length、Selected，分别记录路段编号、道路起点号、道路终点号、路段长度(m)和是否为选出的路段(计算结果图形显示时用)。主要程序片段为

Alter Table表名 (Add LineID Integer，Fnode Integer，Tnode Integer，Length float，Selected Logical)Interactive

三、建立拓扑关系

建立拓扑关系，主要需完成3项工作:给每个路段编号;计算各路段长度;计算各路段的连接关系。前两项可简单计算赋值，第3项的算法核心是:先选定任一路段;然后寻找所有与该路段起点相连的路段，将相连处各路段端点(路段起点或终点)赋相同编号;路段终点作相同运算。遍历所有路段，作以上相同运算。具体算法如下:

1)针对路网表，生成查询表RoadNet。该表中，计算出路网中各路段的起点坐标(Xf，Yf)和终点坐标(Xt，Yt)，并将各路段起止点编号赋初值0(Fnode=0、Tnode=0)。

2)i=0。

3)查找RoadNet中第一个路段。

4)如果被查到的路段起点编号不为0，说明已赋过值，执行步骤5);如果起点编号等于0，i=i+ 1，Fnode=i，即该顶点编号为i。

在RoadNet其他路段中查找起点与i点坐标值相同的路段，给起点赋相同号(Fnode=i)。

在RoadNet其他路段中查找终点与i点坐标值相同的路段，给终点赋相同号(Tnode=i)。

5)如果被查到的路段终点编号不为0，说明已赋过值，执行步骤6);如果终点编号等于0，i=i+ 1，Tnode=i，即该顶点编号为i。

在RoadNet其他路段中查找起点与i点坐标值相同的路段，给起点赋相同号(Fnode=i)。

在RoadNet其他路段中查找终点与i点坐标值相同的路段，给终点赋相同号(Tnode=i)。

6)找到RoadNet中下一个路段，重复步骤4)、步骤5)。

7)遍历所有路段，结束。

程序片段如下

采用相似的算法，计算与上路段终点相连的路段。遍历全部路段，结束。

四、最短路径计算

迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法，是解决最短路径问题的经典算法。Dijkstra算法又称为单源最短路径，是从一个顶点出发，求该顶点至所有可到达顶点的最短路径;Floyd算法可以计算出所有顶点之间的最短路径，计算结果为两个矩阵，一个是任意两个顶点之间的最短距离;另一个是任意两点之间的最短路径。很显然，Floyd算法时间复杂度要高。但一般情况下，路网不会在短时间内更新，路网拓扑关系也相对固定，所以可采用Floyd算法，将计算结果矩阵以文件的形式保存，在最短路径分析时，随时调用，不再重复计算，这样可大幅提高效率。MapInfo平台上比较适合采用这种方法。该算法简捷，这里不再介绍，但在算法实现中有两点需要说明。

1.二维数组

在MapBasic语言支持的数据类型中，包含一维数组，不包含二维数组。但Floyd算法的邻接矩阵需要用二维数组存储、运算，因此，在程序中需要用一维数组实现二维数组功能。程序片段如下

要访问二维数组G(m，n)时，采用G(a(m，n))的方式调用，这样就实现了用一维数组替代二维数组。

2.计算结果的展示

在MapInfo中，计算结果要以图形(可视化)的方式表现，因为图形能更好地识别和解释，达到所见即所得的效果。为方便处理，在路网表中，增加了Selected字段，最短路径分析时，将最短路径所包含路段的Selected值赋为1，最后在路网表中查找Selected=1即可。程序如下

五、效果展示

1)启动MapInfo，打开或新建一个路网表。

2)运行最短路径分析程序，MapInfo中增加了“最短路径分析”菜单，如图1所示。

图1 程序运行界面

3)依次点击“最短路径分析”、“路网拓扑”，进行路网拓扑(每个路网只进行一次路网拓扑即可)。

4)依次点击“最短路径分析”、“查找最短路径”，选取最短路径分析工具，在图中起点处按下鼠标左键，移动到终点处松开鼠标，即可显示出起点至终点的最短路径，如图2、图3所示。

图2 定义最短路径起止点

六、结束语

最短路径分析是GIS的重要组成部分，有着广泛的应用。本文提供了一种在MapInfo中实现这一功能的算法。通过实际验证，该方法界面友好、操作简捷、运算速度快、计算结果准确、性能稳定，有一定的实用价值。

图3 最短路径分析结果

［1］ 沙宗尧，边馥苓.单源最短路径算法的图示教学设计与实践［J］.测绘通报，2010(4):58-61.

［2］ 彭波.数据结构［M］.北京:清华大学出版社，2002.

［3］ 张剑平，任福继，叶荣华，等.地理信息系统与MapInfo应用［M］.北京:科学出版社，1999.

［4］ 李胜乐，陆远忠，车时.MapInfo地理信息系统二次开发实例［M］.北京:电子工业出版社，2004.

［5］ 王晓东，赵全磊，吴建民.MapBasic在MapInfo功能扩展中的应用［J］.测绘通报，2007(8):51-54.

［6］ 陈继山，须鼎兴.使用Shape文件进行最短路径的分析与跟踪［J］.测绘通报，2004(12):8-10.

［7］ 张虎，施一民.基于MapX的公安110报警系统的设计与实现［J］.测绘通报，2004(9):23-25，39.

［8］ 司连法，王文静.快速Dijkstra最短路径优化算法的实现［J］.测绘通报，2005(8):15-18.

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

Realization of the Shortest Path Analysis in MapInfo

HU Dianchang，WANG Jinxiu

0494-0911(2012)06-0087-03

P208

B

2011-12-02

胡殿常(1968—)，男，河北涞水人，工程师，主要从事GIS工作。