A computational study of efficient shortest path algorithms (Q1112733): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q4130999 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3707420 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Appraisal of Some Shortest-Path Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Shortest‐path methods: Complexity, interrelations and new propositions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Technical Note—Shortest-Path Algorithms: A Comparison / rank
 
Normal rank
Property / cites work
 
Property / cites work: Shortest-Route Methods: 1. Reaching, Pruning, and Buckets / rank
 
Normal rank
Property / cites work
 
Property / cites work: A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: New Polynomial Shortest Path Algorithms and Their Computational Attributes / rank
 
Normal rank
Property / cites work
 
Property / cites work: A note on two problems in connexion with graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4057549 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fibonacci heaps and their uses in improved network optimization algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Polynomially Bounded Shortest Path Algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3951448 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A shortest augmenting path method for solving minimal perfect matching problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Network generation using the Prufer code / rank
 
Normal rank

Latest revision as of 10:14, 19 June 2024

scientific article
Language Label Description Also known as
English
A computational study of efficient shortest path algorithms
scientific article

    Statements

    A computational study of efficient shortest path algorithms (English)
    0 references
    0 references
    0 references
    1988
    0 references
    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.
    0 references
    computational comparisons
    0 references
    Five efficient shortest path algorithms
    0 references
    threshold functions
    0 references
    heaps
    0 references
    sensitivity
    0 references
    Curve fittings
    0 references

    Identifiers