交通网络最短路径并行算法研究综述

被引：9

作者：

倪安宁 ^{[1
]}

隽志才 ^{[2
]}

高林杰 ^{[2
]}

机构：

[1] 吉林大学交通学院

[2] 上海交通大学管理学院交通运输研究所

来源：

公路交通科技 | 2006年 / 12期

关键词：

最短路径; 并行算法; 网络分割;

D O I：

暂无

中图分类号：

U491.13 [];

学科分类号：

082302 ; 082303 ;

摘要：

首先回顾了最短路径并行算法的国内外研究进展,对当前的最短路径并行算法进行分类。接着讨论了交通网络分析中最短路径并行算法常用的两种实现策略以及各自的优缺点;分析了影响网络分割策略并行算法性能的3个主要因素:最短路径算法选择、网络分割及终止检测方法。最后就实际交通网络中最短路径并行算法需进一步研究的问题给出了建议。

引用

页码：128 / 132

页数：5

共 6 条

[1] 最短路径的并行加速比的研究 [J].

李丹 ;

张爱华 ;

张志强 .

渤海大学学报(自然科学版), 2004, (03) :230-232

[2] PC机群环境下最短路径并行算法的研究 [J].

谭国真 ;

隋春丽 .

小型微型计算机系统, 2001, (11) :1302-1304

[3]

倪安宁.交通网络分析中的最短路径并行算法研究与实现[D].吉林大学,2004

[4]

D. P. Bertsekas,F. Guerriero,R. Musmanno.Parallel asynchronous label-correcting methods for shortest paths[J].Journal of Optimization Theory and Applications,1996

[5]

Boris V. Cherkassky,Andrew V. Goldberg,Tomasz Radzik.Shortest paths algorithms: Theory and experimental evaluation[J].Mathematical Programming,1996

[6]

P. Adamson,E. Tick.Greedy partitioned algorithms for the shortest-path problem[J].International Journal of Parallel Programming,1991

← 1 →