A SIMPLE AND FAST LABEL CORRECTING ALGORITHM FOR SHORTEST PATHS

被引:72
作者
BERTSEKAS, DP
机构
[1] Laboratory for Information and Decision Systems, M.I.T, Cambridge, Massachusetts
关键词
D O I
10.1002/net.3230230808
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We propose a new method for ordering the candidate nodes in label correcting methods for shortest path problems. The method tries to scan nodes with small labels as early as possible and may be viewed as a low-overhead approximation to Dijkstra's algorithm. Compared with the D'Esopo-Pape algorithm, our method is equally simple but much faster. Our method can also be combined with the threshold algorithm, thereby considerably improving its practical performance. (C) 1993 by John Wiley & Sons, Inc.
引用
收藏
页码:703 / 709
页数:7
相关论文
共 17 条
[1]  
Bellman R. E., 1957, DYNAMIC PROGRAMMING
[2]  
Bertsekas D.P., 1991, LINEAR NETWORK OPTIM
[3]   AN AUCTION ALGORITHM FOR SHORTEST PATHS [J].
Bertsekas, Dimitri P. .
SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (04) :425-447
[4]  
BERTSEKAS DP, 1992, LIDS P2107 REP
[5]   COMPUTATIONAL ANALYSIS OF ALTERNATIVE ALGORITHMS AND LABELING TECHNIQUES FOR FINDING SHORTEST PATH TREES [J].
DIAL, R ;
GLOVER, F ;
KARNEY, D ;
KLINGMAN, D .
NETWORKS, 1979, 9 (03) :215-248
[6]  
FORD LR, 1956, P923 RAND CORP REP
[7]  
GALLO G, 1986, MATH PROGRAM STUD, V26, P38, DOI 10.1007/BFb0121087
[8]   NEW POLYNOMIAL SHORTEST-PATH ALGORITHMS AND THEIR COMPUTATIONAL ATTRIBUTES [J].
GLOVER, F ;
KLINGMAN, DD ;
PHILLIPS, NV ;
SCHNEIDER, RF .
MANAGEMENT SCIENCE, 1985, 31 (09) :1106-1128
[9]  
GLOVER F, 1986, NETWORKS, V14
[10]  
GOLDEN B, 1976, OPER RES, V44, P1164