基于Floyd算法的校园最短路径问题分析与实现
第34卷第6期2012年12月
武汉理工大学学报(信息与管理工程版)
JOURNALOFWUT(INFORMATION&MANAGEMENTENGINEERING)
Vol.34No.6Dec.2012文献标志码:A
文章编号:2095-3852(2012)06-0695-04
基于Floyd算法的校园最短路径问题分析与实现
严晓凤,陆济湘,唐双平
(武汉理工大学理学院,湖北武汉430070)
摘要:利用ArcGIS软件创建校园矢量图,并结合Floyd算法,解决校园中各地点间的最短路径问题。对
Floyd算法从两个方面简化:对于插入的节点,先对其路径长度进行比较,若其到所求节点路径比所求节点对间路径长,则不需参与计算;引入序号矩阵记录使两顶点间的路径长度变短的中间节点序号。最后,在Matlab软件中编程实现,得出校园各地点间的最短路径,结果表明,该方法具有可行性。
关键词:ArcGIS;最短路径;Floyd算法;Matlab中图分类号:TP246
DOI:10.3963/j.issn.2095-3852.2012.06.008
随着计算机技术的快速发展,空间信息及其分析能力、处理能力也大大加强,搜索最短路径已成为当前研究的热点问题。在ArcGIS软件中有具有分析矢量数据的功能。自带的网络分析模块,
由于进行分析的矢量数据必须具有拓扑关系,因此,在进行网络分析前,要先对相应的矢量数据进再用ArcGIS中的网络分析工具创建行拓扑分析,
几何网络并分析最佳路径
[1]
(地理配准)、要素矢量化和要素符号化等。在
ArcGIS中创建的校园矢量化地图如图1所示

。
。该方法既繁琐又
不易掌握。因此,笔者将以武汉理工大学南湖校区为例,研究求解最短路径问题更简便的方法,先对矢量图进行简单处理,提取点要素和线要素的再用先进的Floyd算法对最短路径问题进信息,
行分析,并在Matlab中实现。在最短路径问题中有很多算法需要进行矩阵运算,用C语言之类的高级编程语言实现这些算法比较繁琐,编程也比较复杂,但Matlab则提供了许多矩阵运算的高效使得算法的实现方便了许多函数,
[2]
图1校园矢量图
ArcGIS中创建的校园地图是基于实际位置及实际大小来完成的,从而可保证后期在该地图
上求解最短路径问题的准确性。
2
2.1
最短路径及其算法
最短路径的相关概念
。
1ArcGIS中创建校园矢量图
ArcGIS中创建矢量图主要是在ArcMap中完
对图进行存储主要是指对图中的顶点及边的相关信息进行存储,图中各个顶点之间为多对多的关系,因此,在实际应用中,一般采用邻接矩阵的存储结构。邻接矩阵是通过一个矩阵来描述图中顶点间的相关信息。若给定一个图G=(V,E),v1,v2,…,图G的顶点集为V(G)={v0,vn-1},e1,e2,…,en-1},边集为E(G)={e0,则图G的邻接矩阵为以下的n阶矩阵:
ArcMap是ArcGIS的3个用户桌面组件之成的,
一,它能够实现对地图进行绘制、编辑及分析的操作,提供了基于地图的所有功能。
对二维地图进行矢量化操作可分为几个步
骤:准备地理数据、创建地理数据库、地图定位
收稿日期:2012-06-09.
作者简介:严晓凤(1987-),女,湖北鄂州人,武汉理工大学理学院硕士研究生.基金项目:国防科技基金资助项目(201103HX01).
基于Floyd算法的校园最短路... 5页 免费 校园站点网最短路径的分析... 12页...《校园最短路径问题的研究与实现》 第5页共 37 页 2 详细设计 2.1 功能...
基于Floyd算法的校园最短... 5页 免费 最短路径 ...by leon_jlu 在图论中经常会遇到这样的问题,在一个...本人自己写的蚁群算法。完全能 够实现功能,就是收敛...
Floyd算法在校园信息智能查... 2人阅读 3页 2.00...基于Floyd算法的最短路径问题应用研究 最短路径问题在...本文主要研究了Floyd算法的JAVA语言实现过程及其应用...
Floyd算法——最短路径算法 C语言实现_计算机软件及应用...基于Floyd算法的校园最短... 5页 免费 如何用FLOYD...最短路径问题 2页 2下载券 C++求两点间的最短路...
最短路径算法的C程序实现... 1页 免费 基于最短路径优化问题Di... 暂无评价...三维最短路径分析算法的... 3页 1下载券 基于Floyd算法的校园最短... 5页...
设计中发挥了重要的作用,而网络分析中最基本、最关键 的问题是最短路径问题。...基于Floyd算法的校园最短... 5页 免费 最短路径Floyd算法 3页 免费喜欢...
网络分析中最基本、最关键的问 题是最短路径问题。...编程实现了该算法,最后测试了该算法的性能 本算法...基于Floyd算法的校园最短... 5页 免费喜欢...
求解PERT两点间最短路径的Floyd算法分析与程序实现_专业资料。运用Floyd算法对求解PERT问题中任意两点间最短距离路径的方法进行了讨论,指出了2种确定最短路径岛上的弧...
规划方式, 移动机器人最短路径规划研究即是实现始点和终点间最短路径规划问 题...因此本文基于 Floyd 算法对移动机器人的最短路径 规划问题进行研究,主要对移动...
最短路径Floyd算法动态规划问题及其程序设计_计算机软件及应用_IT/计算机_专业资料...基于Floyd算法的校园最短... 5页 免费喜欢此文档的还喜欢 动态规划-最短路径...
基于matlab的floyd算法 matlab计算最短路径。基于 matlab 的 floyd 算法 matlab 计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd % % Syntax: [d,...
热门文档