基于Floyd算法的校园最短路径问题分析与实现

严晓凤，陆济湘，唐双平

(武汉理工大学理学院，湖北武汉 430070)

随着计算机技术的快速发展，空间信息及其分析能力、处理能力也大大加强，搜索最短路径已成为当前研究的热点问题。在ArcGIS软件中有自带的网络分析模块，具有分析矢量数据的功能。由于进行分析的矢量数据必须具有拓扑关系，因此，在进行网络分析前，要先对相应的矢量数据进行拓扑分析，再用ArcGIS中的网络分析工具创建几何网络并分析最佳路径［1］。该方法既繁琐又不易掌握。因此，笔者将以武汉理工大学南湖校区为例，研究求解最短路径问题更简便的方法，先对矢量图进行简单处理，提取点要素和线要素的信息，再用先进的Floyd算法对最短路径问题进行分析，并在Matlab中实现。在最短路径问题中有很多算法需要进行矩阵运算，用C语言之类的高级编程语言实现这些算法比较繁琐，编程也比较复杂，但Matlab则提供了许多矩阵运算的高效函数，使得算法的实现方便了许多［2］。

1 ArcGIS中创建校园矢量图

ArcGIS中创建矢量图主要是在ArcMap中完成的，ArcMap是ArcGIS的3个用户桌面组件之一，它能够实现对地图进行绘制、编辑及分析的操作，提供了基于地图的所有功能。

对二维地图进行矢量化操作可分为几个步骤:准备地理数据、创建地理数据库、地图定位(地理配准)、要素矢量化和要素符号化等。在ArcGIS中创建的校园矢量化地图如图1所示。

图1 校园矢量图

ArcGIS中创建的校园地图是基于实际位置及实际大小来完成的，从而可保证后期在该地图上求解最短路径问题的准确性。

2 最短路径及其算法

2.1 最短路径的相关概念

对图进行存储主要是指对图中的顶点及边的相关信息进行存储，图中各个顶点之间为多对多的关系，因此，在实际应用中，一般采用邻接矩阵的存储结构。邻接矩阵是通过一个矩阵来描述图中顶点间的相关信息。若给定一个图G=(V，E)，图 G 的顶点集为 V(G)={v0，v1，v2，…，vn-1}，边集为 E(G)={e0，e1，e2，…，en-1}，则图 G的邻接矩阵为以下的n阶矩阵:

最短路径问题有单源点最短路径问题及全源点最短路径问题。

已知给定的一个带权有向图 G=(V，E)，aij=(vi，vj)为 G 中的任一条弧，W(aij)=Wij为弧aij上的权，给定G中某个源点vs和目的点vt，设p为G中vs到vt的某条路径，定义p的权W(p)为p中所有弧的权之和，即:

若图G中vs到vt的一条路径p1满足条件:W(p1)=min{W(p)|p为从vs到vt的路径}，则称p1为vs到vt的最短路径。对于图G，求给定的源点vs到目标点vt的最短路径及最短距离问题即为单源点最短路径问题。

若vi与vj分别为图G中的任意节点，图G中vi到vj的一条路径p2满足以下条件:W(p2)=min{W(p)|p为从vi到vj的路径}，则称p2为任意两节点vi到vj的最短路径，求任意两节点vi到vj的最短路径及最短距离问题即为全源点最短路径问题。

2.2 最短路径的基本算法

通过许多学者多年来在最短路径问题中的研究，已经发展了多种最短路径算法，如文献［3-7］所示，包括Dijkstra算法、Bellman-Ford算法、A*算法、Floyd-Warshall算法，其比较分析如表1所示。

表1 各种典型算法优缺点的比较分析

通过表1中分析比较可知，由于A*算法中的收敛时间一般为指数级，因此求解最短路径的问题中用的相对较少;而对于遗传算法及蚁群算法［8］，它们的最终结果都会受其参数的影响，且算法比较复杂，不易编程实现。对于要在ArcGIS矢量化地图的基础上，对校园中各地点之间的最短路径问题进行求解，应该采用Dijkstra算法或Floyd算法。比较这两种算法，Dijkstra算法是求解单源点最短路径问题，因而，需要重复执行n次Dijkstra算法才能得到最终解，而Floyd算法可直接用于求解全源点最短路径问题，显而易见，Floyd算法的效率要高于Dijkstra算法。因此，根据以上各种典型算法的特点，决定采用Floyd算法在武汉理工大学南湖校区矢量化地图的基础上，求出校园中各地点之间的最短路径及最短距离［9］。

3 Floyd算法

3.1 Floyd算法的基本思想

不妨将图G中的顶点分别编号为0，1，2，…，n-1，令P表示顶点vi到顶点vj之间的一条路径表示这条路径的长度，在这条路径P中，只将前m个顶点0，1，2，…，m-1作为中间节点。定义如下:

令Dm为一个N阶矩阵，为其(i，j)元素，若图G中每条弧的长度已知，则可以确定矩阵D0，通过迭代最终确定最短路径长度的矩阵

3.2 Floyd算法的步骤

根据Floyd算法的基本思想，其实现步骤主要分为3步:

(1)定义初始的距离矩阵为H0=G，邻接矩阵G如下:

(2)依据以下公式构造矩阵Hk。

(3)当 Hk=Hk+1，终止算法;否则，重复步骤(2)。

以上步骤中，每次求解顶点vi到顶点vj的最短路径时，都要进行n次加法计算，且许多插入的中间节点vk明显不能使当前路径长度变短;此外，要找到从顶点vi到顶点vj的最短路所包含的完整路径，往往需要采用反向追踪的方法进行查找，直到搜索到 H0［i］［j］为止，这些都使得计算效率大大降低。因而采用简化后的步骤:

(1)构造初始距离矩阵H0及序号矩阵C0，矩阵的元素如下:

(2)构造距离矩阵H0的迭代矩阵Hk及中间节点的序号矩阵Ck。

对于Hk［i］［j］，迭代中当中间节点序号m 在1到 n 之间递增，且 m≠i，m≠j时，若 Hk-1［i］［m］≥Hk［i］［j］或 Hk-1［m］［j］≥Hk［i］［j］，则表示插入节点vm后，当前的路径长度Hk-1［i］［j］不会变短，因此，不用再计算 Hk-1［i］［m］+Hk-1［m］［j］;若 Hk-1［i］［m］＜ Hk［i］［j］且 Hk-1［m］［j］＜Hk［i］［j］，则:

对于节点的序号矩阵 Ck，若 Hk［i］［j］=Hk-1［i］［m］+Hk-1［m］［j］，Hk［i］［j］＜ Hk-1［i］［j］，则记录下节点 vm，有 Ck［i］［j］={Ck-1［i］［m］，vm，Ck-1［m］［j］};否则，有 Ck［i］［j］=Ck-1［i］［j］。

(3)当Hk=Hk+1时，终止算法;否则，重复步骤(2)。

3.3 Floyd算法的复杂度分析

对于原始的Floyd算法，当对顶点vi到顶点vj的最短路径 Hk［i］［j］进行计算时，每次都需要对其第i行及第j列所对应的元素进行相加运算，一共有n次加法运算，且对于迭代的距离矩阵，其中共有n×n个元素，因此，算法的时间复杂度为o(n3)。

对简化后的Floyd算法，当对vi到vj的最短路径 Hk［i］［j］进行计算时，有 m≠i，m≠j，因此，对第i行及第j列所对应的元素进行相加运算最多只需要进行n-2次。此外，每次对 Hk［i］［j］计算前，都要对将要插入的节点vm先进行路径的长度比较，若 Hk-1［i］［m］≥Hk［i］［j］或Hk-1［m］［j］≥Hk［i］［j］，则表示插入节点 vm后，当前的路径长度 Hk-1［i］［j］不会变短，因此，不用继续计算 Hk-1［i］［m］+Hk-1［m］［j］;若第 i行或第j列所对应的元素都不小于 Hk-1［i］［j］，则可以直接得出 Hk［i］［j］=Hk-1［i］［j］，此时加法运算的时间复杂度为0。因此，对vi到vj的最短路径 Hk［i］［j］进行计算时，计算量为 0 ～ n-2次，是随机变量，令其为Y，假设Y在0～n-2之间的取值具有相等的可能性，则Y的数学期望为，加法的计算量即为，而对于迭代的距离矩阵，其中共有n×n个元素。因此，用简化后的Floyd算法使时间复杂度大大降低，为

3.4 Matlab中最短路径算法的实现

对图1提取线路的交点，再对它们建立点图层并编号，得到的校园线路图如图2所示。

图2 校园线路图

图2中:v1为校园大门，v2为教学楼2，v3为主教学楼，v4为图书馆，v5为理学院，v6为食堂2，v7为化学楼，v8为学生公寓1，v9为学生公寓2。

从点和线图层中提取节点及弧段的信息，创建邻接矩阵G如下:

矩阵 G 中的元素 dij(i，j=1，2，…，9)为顶点 vi到顶点vj的距离，其中dij=∞为两顶点间无路径。

在Matlab运行程序的过程中，由于∞在计算机中无法进行计算，姑且将其定为100000000000000来计算，由于相对于其他的数据，100000000000000是比较大的，因此，这样改变并不会对程序运行后结果的准确性产生影响。程序的部分代码如下:

采用Matlab语言编程实现Floyd算法可求得最短路径，各顶点之间的最短距离如表2所示。

表2 各顶点之间的最短距离 m

4 结论

通过简化的Floyd算法，较好地解决了网络图中的任意两顶点的最短路径问题，采用简化后的Floyd算法进行计算，可以加快迭代速度，省去大量多余的操作，大大减少运行的时间;此外，由于在计算节点间路径长度之前先对其进行了大小的比较，对于那些与给定节点对不直接相连接的插入节点，它们不能使当前的路径变短，以及那些与节点对直接相连的且其路径长度比节点对路径要长的插入节点，在算法的过程当中并没有参与计算，因此，计算量大大减少了。

此外，在求解最短路径的过程中，引入了序号矩阵用来记录使两顶点间的路径长度变短的中间节点序号，从而使得求解最短路径问题的过程更直观、方便。通过Matlab编程语言对简化后的Floyd算法求解最短路径问题，操作简单，且效果较好。

［1］汤国安，杨昕.ArcGIS地理信息系统空间分析实验教程［M］.北京:科学出版社，2006:19-65.

［2］王沫然.Matlab与科学计算机［M］.北京:电子工业出版社，2004:16-89.

［3］许志海，魏峰远.交通网络中最短路径算法分析与探讨［J］.河南理工大学学报，2005(1):74-78.

［4］荣玮.基于道路网的最短路径算法的研究与实现［D］.武汉:武汉理工大学图书馆，2005.

［5］BENJAMIN F Z.Three fastest shortest path algorithms on real road networks:data structures and procedures［J］.Journal of Geographic Information and Decision Analysis，1998(1):69-82.

［6］JI X Y.Models and algorithm for stochastic shortest path problem［J］.Applied Mathematics and Computation，2005，70(2):503-514.

［7］周先曙.最短路径问题及其解法研究［J］.电脑知识与技术，2010(6):1403-1412.

［8］夏兰.基于蚁群算法的交通地理最佳路径的研究［D］.武汉:武汉理工大学图书馆，2009.

［9］陆济湘，南良改.一种新的基于重采样的曲线重建算法［J］.武汉理工大学学报:信息与管理工程版，2009，31(6):861-864.

［10］WEI D C.Implementation of route selection function based on improved floyd algorithm［C］//Proceedings 2010 WASE International Conference on Information Engineering.［S.l.］:［s.n］，2010:223-227.

［11］WEI D C.An optimized floyd algorithm for the shortest path problem［J］.Journal of Networks，2010，5(12):1496-1504.