基于MapX的最短路径分析方法的设计与实现
MapX是一个基于ActiveX(OCX)技术的可编程控件。它使用与MapInfo Professional一致的地图数据格式，并实现了大多数MapInfo Professional的功能。
本文基于Mapx技术使用Dijkstra算法，通过一系列研究工作实现了一种较为实用的最短路径分析。19392
关键词：Mapx；地理信息系统；Dijkstra算法；最短路径分析
毕业论文设计说明书（论文）外文摘要
Title Design and implementation of the shortest path analysis method based on MapX
Abstract
Network analysisis is an important aspect of the spatial analysis,and the shortest path analysis is the leading section.The shortest path problem in graph theory is the study of a classical algorithm problem.The purpose is to find the shortest path between two nodes in the diagram(composed by the nodes and paths).Through the shortest path analysis can solve a variety of complex issues, including mine rescue, etc.As used herein,
MapX is an ActiveX (OCX) technology-based programmable control.It uses the same map data formatas MapInfo Professional, and achieved the most function of MapInfo Professional.This article is based Mapx Technology,and using the Dijkstra algorithm achieving a more practical shortest path analysis through a series of studies.
Key-words：Mapx；geographic information system，Dijkstra algorithm；shortestpath analysis
目 次
1 绪论 1
1.1 背景及意义 1
1.2 本文的主要工作 2
2 Mapx技术 3
2.1 Mapx技术简介 3
2.2 Mapx主要功能 3
2.3 本章小结 5
3 最短路径算法 6
3.1 图论及其相关概念 6
3.2 图的遍历 7
3.3 最短路径算法 10
3.4 本章小结 14
4.1 数据处理 15
4.2 拓扑关系构建 16
4.3 Dijkstra算法的实现 18
4.4 最短路径的显示 20
4.5 本章总结 20
致 谢 22
参考文献 23
1 绪论
1.1 背景及意义
现在生活发展使得网络优化问题应运而生，而最短路径问题又是其中之关键。最短路径问题多用于解决现实生活中的事件，因此在很多网络优化算法中均有或大或小的使用。作为图论问题中的经典，最短路径问题旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
随着现代文明的发展，传统的寻路方式已经不能满足普通民众的需求。在错综复杂的地图环境下，仅依靠传统方法不仅浪费了大量的人力物力，且占用大量时间。因此，通过高级的算法从而设计出一种能够有效提升效率的最短路径寻找法，极为必要。
地理信息系统(Geographic Information System，GIS)是用于输入、存储、查询、分析和显示地理数据的计算机系统，随着GIS的发展，也有称GIS为“地理信息科学”（Geographic Information Science），近年来，也有称GIS为"地理信息服务"（Geographic Information service）[1]。地理信息系统基于计算机，将地图内容和其上的具体内容与一般的数据库相联系，使之集成。地理信息系统系统在企业工作，公众生活应用中起到解释事件，预测结果，规划战略中起到极大的作用。1967年，加拿大联邦林业和农村发展部研发并投入使用了世界上第一个地理信息系统[2]。其开发者，加拿大科学家罗杰•汤姆林森称其为加拿大地理信息系统（CGIS ）。而直到二十世纪末，微型计算机的蓬勃发展才使得地理信息系统的普及和商业化。地理信息系统从传统的空间信息管理阶段经过模型化发展阶段、支持空间信息化的预测和模拟阶段到现在的支持系统空间结构信息的优化和宏微观的调控阶段。随着二十一世纪初期信息爆炸时代的降临，地理信息系统技术的研究和应用领域逐渐的扩展到现代科学计算、大数据存储、宽带互联网、数据共学、云计算、虚拟现实等高新产业技术领域。