网络最短路径定界搜索算法

被引：13

作者：

李引珍

郭耀煌

机构：

[1] 西南交通大学经济管理学院

[2] 西南交通大学经济管理学院四川成都兰州交通大学交通运输学院甘肃兰州

[3] 四川成都

来源：

西南交通大学学报 | 2004年 / 05期

关键词：

网络分析; 最短路径; 双向定界搜索算法; 效率;

D O I：

暂无

中图分类号：

U113 [运输网];

学科分类号：

08 ; 0823 ;

摘要：

用Dijkstra算法求解大规模网络两顶点间最短路径时,需计算大量与最短路径无关的顶点,效率较低.双向定界搜索算法是首先对网络进行双向搜索,得到一条经任意点的最短路径.一般情况下,这条路径已非常接近、甚至等于最短路径.然后,以此路径的标号(即路径长)作为搜索计算的界,进行双向标号计算,对超过界的顶点不再计算,以提高计算效率.算法分析表明,用该算法可使计算效率提高约一倍.

引用

页码：561 / 564

页数：4

共 6 条

[1] 一种启发式遗传算法及其在最短路径求取中的应用 [J].