摘要：介绍了地理信息系统（GIS）和MapInfo及其二次开发语言MapBasic，同时介绍了最短路径问题的应用背景及其经典算法和经典算法的改进方法，最后把MapInfo和MapBasic以及Visual C++相结合对最短路径程序进行了改进开发。

  关键词：地理信息系统；MapInfo；最短路径；拓扑

在笔者之前发表的论文^[1]中对电子商务下的港口物流系统与GIS相结合进行了一些研究，分析了地理信息系统（GIS）的特点及GIS与港口物流系统相结合的优点，并基于GIS用MapInfo及MapBasic按经典算法^[7]开发了自动运输路径选择即最短路径计算的程序。本文对此最短路径程序进行了算法与开发方法的改进研究，提高了它的计算速度，使其具有更高的实际应用价值。

1．地理信息系统（GIS）和MapInfo及其二次开发语言MapBasic

   理信息系统是一种先进的计算机软件技术。它是对各种空间信息进行收集、存储、分析和可视化表达的信息处理与管理系统。GIS是一种决策支持系统，它具有信息系统的各种特点。GIS提供给你的信息产品不仅仅是简单的文字和数据，而且还有一幅幅空间图形或图像。位置图往往比文字更能说明空间问题，它给人以直观完整而深刻的印象。GIS表达问题准确，这种系统特别适合管理各种与空间位置有关的事物。这类事物在我们的日常生活和工作中是大量的，专家估计，80%以上的信息具有空间属性。因此，GIS现在已广泛应用于政府行政管理、军事、国防，尤其广泛应用于专业技术性管理，如国土资源、矿产资源、交通运输、防灾减灾、环境保护、水电建设、水土保持、森林防火、建设规划、公安、消防、工程、邮电、海洋、农林和银行等方面的技术管理。凡是需要用到各种位置图的地方都可以用GIS。有了GIS，便有了图库和数据库，就可以通过鼠标来实现信息的快速查询和分析处理。大到地球、国家、省市，小到村镇、街道乃至地面上的一个点位，GIS都能做到要图有图，要数据有数据；图文关联，天衣无缝。

 GIS 支撑软件很多，比较常用的有美国GIS开发商ESRI, Intergraph和MapInfo三种软件，国内也有三种软件，分别是：MapGIS, GeoStar和CityStar。在小型和桌面系统领域里，MapInfo及其二次开发语言Map Basic地理信息开发应用平台是目前地理信息领域里最为广泛的工具之一。MapInfo提供了完整的地理信息解决方案，同时推出了可以进行二次开发和使MapInfo智能化的MapBasic语言。 

2．最短路径问题的应用背景

   网络分析作为GIS最主要的功能之一，在物流系统、电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。在实际应用中，最短路径问题的实现应该是高效率的，因此一个需要漫长等待才能出结果的最短路径算法也是让人无法忍受的。其实,无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。所以最短路径算法的效率直接影响其他GIS的应用，如何选择一个好的最短路径算法并高效率实现成为GIS系统建设的关键。

3．图的拓扑和存储结构

最短路径算法在很多领域被使用，在数学上通常把实际中的最短路径问题抽象成有向带权图的最短路径问题，在MapInfo提供的GIS系统中只是记录路段的空间位置，并没有将路网的结构表现成图形式的拓扑结构，但是凭借MapBasic的强大功能，很容易就可以将矢量形式的路网按其节点和边的关系拓扑成数学上的图。图的存储结构也有很多种，如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低，在本系统中采用按弧段存储原则，即每个弧段只记录它的源节点和目的节点。这样就大大压缩了存储图的空间。