A computational study of efficient shortest path algorithms

DOI10.1016/0305-0548(88)90052-4MaRDI QIDQ1112733zbMATH OpenOpenAlexFDO

Authors Ming S. Hung, James J. Divoky

Publication date 1988

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0305-0548(88)90052-4

zbMATH Keywords

computational comparisonsCurve fittingsFive efficient shortest path algorithmsheapssensitivitythreshold functions

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35)

Review text

Five efficient shortest path algorithms are implemented and compared in this report. The selected algorithms are the most efficient, measured either in terms of worst case bounds or from previous computational studies. The algorithms include two using threshold functions, two using heaps, and one using buckets for sorting node labels. The last three algorithms have not been studied in detail before. The computational experiment employs a rigorous design to ensure that the results have statistical validity. Three different cost functions are generated to measure the sensitivity of each algorithm to cost distributions. Curve fittings are performed to summarize the results and they show high degrees of goodness-of-fit. The results reveal some heretofore unknown properties of some of the algorithms.

Recommendations

• scientific article; zbMATH DE number 1003284
• Shortest paths algorithms: Theory and experimental evaluation
• PRACTICAL EFFICIENCIES OF EXISTING SHORTEST-PATH ALGORITHMS AND A NEW BUCKET ALGORITHM
• Comparaison d'algorithmes de plus courts chemins sur des graphes routiers de grande taille
• scientific article; zbMATH DE number 2081016

Cites work

• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• A New Polynomially Bounded Shortest Path Algorithm
• A note on two problems in connexion with graphs
• A shortest augmenting path method for solving minimal perfect matching problems
• An Appraisal of Some Shortest-Path Algorithms
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3770836 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• Network generation using the Prufer code
• New Polynomial Shortest Path Algorithms and Their Computational Attributes
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• Shortest‐path methods: Complexity, interrelations and new propositions
• Technical Note—Shortest-Path Algorithms: A Comparison
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(11)

• Multiple UAVs path planning algorithms: a comparative study
• Shortest path algorithms: A computational study with the C programming language
• Some personal views on the current state and the future of locational analysis
• Some new algorithms for location problems on networks
• Intelligent transportation systems -- Enabling technologies
• Shortest paths algorithms: Theory and experimental evaluation
• Heuristic shortest path algorithms for transportation applications: state of the art
• On the equivalence between some shortest path algorithms
• Computational efficiency of shortest path algorithms in C language
• Efficient Algorithms for Solving the Shortest Covering Path Problem
• Extended dominance and a stochastic shortest path problem

Describes a project that uses

Uses Software

• Algorithm 360

This page was built for publication: A computational study of efficient shortest path algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112733)