A simple and fast label correcting algorithm for shortest paths
1993; Wiley; Volume: 23; Issue: 8 Linguagem: Inglês
10.1002/net.3230230808
ISSN1097-0037
Autores Tópico(s)Constraint Satisfaction and Optimization
ResumoAbstract 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. © 1993 by John Wiley & Sons, Inc.
Referência(s)