基于MapX的最短路径分析方法的设计与实现 (3)
2.3 本章小结
本章介绍了Mapx软件的背景及其主要功能，并对Mapx的使用进行了阐述。
3 最短路径算法
3.1 图论及其相关概念
3.1.1 图
图论最早由欧洲数学家欧拉于1736年提出。其广泛的运用有效的推动了图论的发展，并于上世纪40-60年代，赢来了大跨越。此时的拟阵理论、超图理论 、极图理论，以及代数图论、拓扑图论等都有很大的发展。
图论中将若干点以及两点间的连线组成的图形称之为图。图是顶点和边的集合，也是顶点集上的二元关系。两个顶点之间的连线为弧(Arc)；[7]而两个顶点之间的数据关系为R，VR表示两个顶点之间关系的集合。其边不具有长度属性。从一个边到另一个边的距离（即与图的边相关联的数）用权（weight）来表示。网（network）是带权的图，对道路系统中的路网进行分析时便使用此概念。
图可分为有向图和无向图两种。有向图中的边是由一个顶点指向另一个顶点，具有方向性。相反的，无向图中，两个顶点之间的边并不具有方向性。以顶点A和顶点B为例，从顶点A到顶点B的距离相通，没有差别。
在无向图中，若两个顶点之间存在有边将两个顶点相连，则称这两个点相邻接，两个顶点互为邻接点。同时，这两个顶点间的边与这两个顶点相关联。对于一个顶点来说，存在且与此顶点相关联的边的数量被称为这个顶点的度（degree）。
无向图中，从一个确定的起始顶点出发，到达目标顶点，其过程中所经过的顶点，称为路径。而有向图中，从某一顶点出发到达另一顶点，这个过程所通过的路径也具有方向性。路径的长度等于路径上的边的数目。如果路径处于带权值的网中，此时路径的长度值等于路径上的边的权值和[8]。
3.1.2 图的存储方式
常用的图的存储方式有：数组表示法(邻接矩阵)、邻接表、邻接多重表、十字链表等。一般情况下图的存储选用数组表示法和邻接表。
1.数组表示法：用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。
由于数组表示法是由两个数组来存储图中的顶点和链接顶点的边的信息，则可得当二文数组中图的顶点为n时，需要存储n个顶点和n*n个边的存储量。由于是无向图，此时可将图压缩为矩阵的上半三角或下半三角。
2.邻接表（Adjacency List）：是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。
表结点由3个域组成：
adjvex：邻接点域，指示与顶点vi邻接的点在图中的位置。
nextarc：链域，指示下一条边或弧的结点。
info：数据域，存储和边或弧相关的信息，如权值等。
头结点由2个域组成：
data：数据域，存储顶点vi的名或其他有关信息。
firstarc：链域，指向链表中第一个结点。
可以使用邻接表来储存图中的顶点与边的信息。而由于邻接表采用链式的存储结构。所以在邻接表中，每一个单链表对应着单独一个顶点的信息。此方法较之数组表示法，只储存已有边或弧的信息，可以节省大量空间。
3.2 图的遍历
在图论中，最短路径的求解，是指遍历图中所有节点的过程。图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。