动态最短路径算法及其仿真

《动态最短路径算法及其仿真》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、万方数据第24卷第06期计算机仿真2007年06月文章编号：1006—9348(2007)06—0153—03动态最短路径算法及其仿真田鹏飞，王剑英(中国科学技术大学计算机科学与技术系，安徽合肥230027)摘要：最短路径算法广泛应用在GIS(地理信息系统)、机器人探路、计算机网络等领域，经过几十年发展，有了很大进展。现在流行的最短路径算法有Dijkstra算法、A*算法，它们都建立在信息完全准确、静态路网的前提下。但现实中信息常常不准确、不完整，路途环境不断变化。当环境变化时，需要重新修改整个路径，因而速度较慢。介绍一种动态最短路径算法，初始时建立好最短路径，当环境变化时，可

2、以只计算变化处附近局部节点，减少计算量，从而较迅速做出新的最短路径选择。最后经过仿真看出，路网中节点越多，动态最短路径算法优势越大。关键词：动态；最短路径；算法中图分类号：TP301．6文献标识码：BAnalgorithmofShortestPathforDynamicSituationandItsSimulationTIANPeng—fei，WANGJian—ying(Dept．ofComputerSci．&Teeh．，Univ．ofSci．&Tech．ofChina，HefeiAnhui230027，China)ABSTRACT：Findingtheshortestpath

3、throughagraphisappliedinmanydomains，includingGIS，routeplanningforarobot，andcomputer．network．1thasmadegreatprogressi‘nseveraldecades．Therearesomepopularalgorithmsoftheshortestpath，suchasDijkstraandA$algorithm．Howeverthesealgorithmsassumeworkinginstaticenvironmentandwithcompleteaccurateinforma

4、tion，whereasinreallife，theinformationisnotalwaysideal，andsituationoftenchangesfromtimetotime．Whenthesituationchanges，theentirepathneedstobemodified，thUSloweringthespeed．Thispaperintroducesanewdynamicalgorithm，whichestablishesaninitialpath．Whentheconditionchanges，itonlycomputespartofthenodesl

5、ocally，reducesthecomputingwork．Itcanbeconcludedfromthesimulationthatthemorenodesinthegraph，themoreefficientthedynamicalgorithmcanbe．KEYWORDS：Dynamic；Shortestpath；Algorithm1引言最短路径算法广泛应用在GIS(地理信息系统)、机器人探路、计算机网络等领域。随着计算机和地理信息科学的发展，地理信息系统GIS的应用领域越来越广，最短路径问题无论是在交通运输，还是在城市规划、物流管理等方面，它都发挥了重要的作用。近几年

6、，城市化发展越来越快，汽车销售总量也逐年上升，用户对汽车GPS导航产品需求增大，而最短路径分析是导航系统的必备功能之一。GPS导航中最短路径大致分为时间最短、路程最短两种。现在时间最短路径分析基本上基于路段旅行时间是静态不变，他们首先用历史统计信息确定道路网中路段的旅行时间，然后用最短路径算法收稿El期：2006—04—28修回日期：2006一05—03计算出车辆当前位置到目的地的完整路径，使得其预期旅行时间最短，这些算法最基本模型是假设路段旅行时问是固定不变的，也就是两点之间的路径是确定的并且与时间无关。路程最短分析也类似，没有考虑到堵车、事故、道路施工修路等因素，都假设在静

7、态路网中。近几十年，对静态路网的最短路径算法得到了很大成就，流行的有Dijkstra算法和A+算法。这些算法的缺点是每发现一个变化(堵车、修路等)，都要将所有路径重新计算一次，而导航系统一般使用嵌入式处理器，其计算能力较弱，当节点较多时，需要较多时间。本文针对这个问题，采取一种新的方法，尽量将计算范围局限在变化点附近，减少计算量，从而缩短计算时间。2现阶段常用的Dijkstra和A：I：算法简介Dijkstra算法是最短路径算法中最常用的算法，用于计算一个节点到其他所有节点的最短路径。主要特