A simple and fast label correcting algorithm for shortest paths
Author:
Abstract
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.Keywords
This publication has 11 references indexed in Scilit:
- An Auction Algorithm for Shortest PathsSIAM Journal on Optimization, 1991
- Shortest path methods: A unifying approach1986
- Shortest‐path methods: Complexity, interrelations and new propositionsNetworks, 1984
- Computational study of an improved shortest path algorithmNetworks, 1984
- A note on finding shortest path treesNetworks, 1981
- Properties of Labeling Methods for Determining Shortest Path TreesJournal of Research of the National Bureau of Standards, 1981
- A computational analysis of alternative algorithms and labeling techniques for finding shortest path treesNetworks, 1979
- Technical Note—Shortest-Path Algorithms: A ComparisonOperations Research, 1976
- Implementation and efficiency of Moore-algorithms for the shortest route problemMathematical Programming, 1974
- NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network ProblemsManagement Science, 1974