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

An algorithm of Shortest Path for Dynamic Situation and Its Simulation

作　　者：田鹏飞[1] 王剑英[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系,安徽合肥230027

出　　处：《计算机仿真》2007年第6期153-155,206,共4页Computer Simulation

摘　　要：最短路径算法广泛应用在GIS(地理信息系统)、机器人探路、计算机网络等领域,经过几十年发展,有了很大进展。现在流行的最短路径算法有Dijkstra算法、A算法,它们都建立在信息完全准确、静态路网的前提下。但现实中信息常常不准确、不完整,路途环境不断变化。当环境变化时,需要重新修改整个路径,因而速度较慢。介绍一种动态最短路径算法,初始时建立好最短路径,当环境变化时,可以只计算变化处附近局部节点,减少计算量,从而较迅速做出新的最短路径选择。最后经过仿真看出,路网中节点越多,动态最短路径算法优势越大。Finding the shortest path through a graph is applied in many domains, including GIS, route planning for a robot, and computer network. It has made great progress in several decades. There are some popular algorithms of the shortest path, such as Dijkstra and A ＊ algorithm. However these algorithms assume working in static environment and with complete accurate information, whereas in real life, the information is not always ideal, and situation often changes from time to time. When the situation changes, the entire path needs to be modified, thus lowering the speed. This paper introduces a new dynamic algorithm, which establishes an initial path. When the condition changes, it only computes part of the nodes locally, reduces the computing work. It can be concluded from the simulation that the more nodes in the graph, the more efficient the dynamic algorithm can be.

关 键 词：动态 最短路径 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]