简单拓扑 求最短路径 matlab,基于floyd算法的校园最短路径问题分析与实现.pdf

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

第34卷第6期 武汉理工大学学报(信息与管理工程版) 2012年12月 JOURNAL OF WUT(INATION&MANAGEMENT ENGINEERING) Vo1．34 No．6 Dec．2012 文章编号：2095—3852(2012)06—0695—04 文献标志码：A 基于Floyd算法的校园最短路径问题分析与实现 严晓凤，陆济湘，唐双平 (武汉理工大学理学院，湖北武汉430070) 摘要：利用ArcGIS软件创建校园矢量图，并结合Floyd算法，解决校园中各地点间的最短路径问题。对 Floyd算法从两个方面简化：对于插入的节点，先对其路径长度进行比较，若其到所求节点路径比所求节点对 问路径长，则不需参与计算；引入序号矩阵记录使两顶点间的路径长度变短的中间节点序号。最后，在Matlab 软件中编程实现，得出校园各地点间的最短路径，结果表明，该方法具有可行性。 关键词：ArcGIS；最短路径；Floyd算法；Matlab 中图分类号：TP246 DOI：10．3963／j．issn．2095—3852．2012．06．008 随着计算机技术的快速发展，空间信息及其 分析能力、处理能力也大大加强，搜索最短路径已 成为当前研究的热点问题。在ArcGIS软件中有 自带的网络分析模块，具有分析矢量数据的功能。 由于进行分析的矢量数据必须具有拓扑关系，因 此，在进行网络分析前，要先对相应的矢量数据进 行拓扑分析，再用ArcGIS中的网络分析工具创建 几何网络并分析最佳路径¨ 。该方法既繁琐又 不易掌握。因此，笔者将以武汉理工大学南湖校 区为例，研究求解最短路径问题更简便的方法，先 对矢量图进行简单处理，提取点要素和线要素的 信息，再用先进的Floyd算法对最短路径问题进 行分析，并在Matlab中实现。在最短路径问题中 有很多算法需要进行矩阵运算，用c语言之类的 高级编程语言实现这些算法比较繁琐，编程也比 较复杂，但Matlab则提供了许多矩阵运算的高效 函数，使得算法的实现方便了许多 。 1 ArcGIS中创建校园矢量图 ArcGIS中创建矢量图主要是在ArcMap中完 成的，ArcMap是ArcGIS的3个用户桌面组件之 一，它能够实现对地图进行绘制、编辑及分析的操 作，提供了基于地图的所有功能。 对二维地图进行矢量化操作可分为几个步 骤：准备地理数据、创建地理数据库、地图定位 (地理配准)、要素矢量化和要素符号化等。在 ArcGIS中创建的校园矢量化地图如图1所示。 图1校园矢量图 ArcGIS中创建的校园地图是基于实际位置 及实际大小来完成的，从而可保证后期在该地图 上求解最短路径问题的准确性。 2最短路径及其算法 2．1最短路径的相关概念 对图进行存储主要是指对图中的顶点及边的 相关信息进行存储，图中各个顶点之间为多对多 的关系，因此，在实际应用中，一般采用邻接矩阵 的存储结构。邻接矩阵是通过一个矩阵来描述图 中顶点间的相关信息。若给定一个图G=( ， E)，图G的顶点集为V(G)={ ， ， ，…， 一 }，边集为E(。G)={e。，e ，e：，…，e }，则图G 的邻接矩阵为以下的n阶矩阵： 收稿日期：2012—06—09． 作者简介：严晓凤(1987一)，女，湖北鄂州人，武汉理工大学理学院硕士研究生 基金项目：国防科技基金资助项目(201103HX01)． 696 武汉理工大学学报(信息与管理工程版) 2012年12月 G ={ 裘 ㈩ 最短路径问题有单源点最短路径问题及全源 点最短路径问题。 已知给定的一个带权有向图G=( ，E)， 。 =( ，vj)为G中的任一条弧， (。。f)= ，为弧 o 上的权，给定G中某个源点 和目的点 ，设P 为G中 到 的某条路径，定义P的权W(p)为 P中所有弧的权之和，即： W(p)=∑ (2) (vl，vj)Ep 若图G中 到 的一条路径P 满足条件： W(p )=min{tr(p)l p为从 到 的路径}，则 称P 为 到 的最短路径。对于图G，求给定的 源点 到目标点 的最短路径及最短距离问题 即为单源点最短路径问题。 若 与vj分别为图G中的任意节点，图G中 到 ，的一条路径P：满足以下条件：W(p：)= min{ (p)Ip为从V 到 的路径}，则称p 为任 意两节点 到 的最短路径，求任意两节点 到 v，的最短路径及最短距离问题即为全源点最短路 径问题。 2．2最短路径的基本算法 通过许多学者多年来在最短路径问题中的研 究，已经发展了多种最短路径算法，如文献[3—7]所 示，包括Dijkstra算法、Bellman—Ford算法、A 算 法、Floyd—Warshall算法，其比较分析如表1所示。 表1各种典型算法优缺点的比较分析 通过表1中分析比较可知，由于A 算法中 的收敛时问一般为指数级，因此求解最短路径的 问题中用的相对较少；而对于遗传算法及蚁群算 法 ]，它们的最终结果都会受其参数的影响，且 算法比较复杂，不易编程实现。对于要在ArcGIS 矢量化地图的基础上，对校园中各地点之间的最 短路径问题进行求解，应该采用Dijkstra算法或 Floyd算法。比较这两种算法，Dijkstra算法是求 解单源点最短路径问题，因而，需要重复执行凡次 Dijkstra算法才能得到最终解，而Floyd算法可直 接用于求解全源点最短路径问题，显而易见， Floyd算法的效率要高于Dijkstra算法。因此，根 据以上各种典型算法的特点，决定采用Floyd算法 在武汉理工大学南湖校区矢量化地图的基础上，求 出校园中各地点之间的最短路径及最短距离 J。 3 Floyd算法 3．1 Floyd算法的基本思想 不妨将图G中的顶点分别编号为0，1，2，…， n一1，令P表示顶点 到顶点 ，之间的一条路 径，d 表示这条路径的长度，在这条路径P中，只 将前m个顶点0，1，2，…，m一1作为中间节点。 定义如下： r 0 ( ，vj)∈E(G) d ={0 ( ，vj) E(G)且i= (3) 【∞ ( ，v1)隹E(G)且i≠ 令D 为一个Ⅳ阶矩阵，d 为其(i， )元素， 若图G中每条弧的长度已知，则可以确定矩阵 D。，通过迭代最终确定最短路径长度的矩阵 D [ 。一 3．2 Floyd算法的步骤 根据Floyd算法的基本思想，其实现步骤主 要分为3步： (1)定义初始的距离矩阵为Ho=G，邻接矩 阵G如下： rW ( ，vj)∈E(G) G[i][ ]={0 ( ，vj)岳E(G)且i= 【∞ ( ， )岳E(G)且 ≠ (4) (2)依据以下公式构造矩阵 。 [i][ ]=min{ 一 [i] ， 日¨[ ][m]+日 [m] }，1≤m≤n (3)当 = 小终止算法；否则，重复步骤(2)。 以上步骤中，每次求解顶点 到顶点vi的最 短路径时，都要进行n次加法计算，且许多插入的 中间节点 明显不能使当前路径长度变短；此 第34卷第6期 严晓凤，等：基于Floyd算法的校园最短路径问题分析与实现 697 外，要找到从顶点 到顶点 的最短路所包含的 完整路径，往往需要采用反向追踪的方法进行查 找，直到搜索到日