A computational study of efficient shortest path algorithms (Q1112733): Difference between revisions
From MaRDI portal
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
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
0 references