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

摘要：

最短路径算法广泛应用在GIS(地理信息系统)、机器人探路、计算机网络等领域,经过几十年发展,有了很大进展.现在流行的最短路径算法有Dijkstra算法、A*算法,它们都建立在信息完全准确、静态路网的前提下.但现实中信息常常不准确、不完整,路途环境不断变化.当环境变化时,需要重新修改整个路径,因而速度较慢.介绍一种动态最短路径算法,初始时建立好最短路径,当环境变化时,可以只计算变化处附近局部节点,减少计算量,从而较迅速做出新的最短路径选择.最后经过仿真看出,路网中节点越多,动态最短路径算法优势越大.

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

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2007-07-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：153-155,206