一种基于双向搜索的K则最优路径算法

被引：55

作者：

高松

陆锋

段滢滢

机构：

[1] 中国科学院资源与环境信息系统国家重点实验室

来源：

武汉大学学报(信息科学版) | 2008年 / 04期

关键词：

K则最优路径算法; 双向搜索; Dijkstra算法;

D O I：

暂无

中图分类号：

O224 [最优化的数学理论];

学科分类号：

070105 [运筹学与控制论];

摘要：

提出了一种基于双向搜索策略的K则最优路径算法,以改进的Dijkstra最优路径算法为基础,从起点和终点同时搜索,分别构造正序和逆序最优路径树,计算网络中两点之间的多条参考K则最优路径。详细描述了算法设计思想和运行过程,分析了算法的时间复杂度,并通过实际路网验证了算法的效率和精度。

引用

页码：418 / 421

页数：4

共 8 条

[1]

A METHOD FOR THE SOLUTION OF THE NTH BEST PATH PROBLEM [J].

HOFFMAN, W ;

PAVLEY, R .

JOURNAL OF THE ACM, 1959, 6 (04) :506-514

[2]

Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用 [J].

王峰 ;

游志胜 ;

曼丽春 ;

高燕 ;

汤丽萍 .

计算机应用研究, 2006, (09) :203-205+208

[3]

一个求解次短和渐次短路径的实用算法 [J].

陈文兰 ;

潘荫荣 .

计算机应用与软件, 2006, (01) :94-96

[4]

一个求解k短路径实用算法 [J].

戴树贵 ;

陈文兰 .

计算机工程与应用 , 2005, (36) :63-65

[5]

交通网络最短路径标号算法的实现与效率分析 [J].

陈洁 ;

陆锋 .

中国图象图形学报, 2005, (09) :1134-1138

[6]

一种新的Kth最短路径搜索算法 [J].

王明中 ;

谢剑英 ;

陈应麟 ;

不详 .

计算机工程与应用 , 2004, (30) :49-50+89

[7]

K优路径的一种求解算法与实现 [J].

袁红涛 ;

朱美正 .

计算机工程与应用, 2004, (06) :51-53+73

[8]

最短路径算法:分类体系与研究进展 [J].

陆锋 .

测绘学报, 2001, (03) :269-275

← 1 →