A Practical Shortest Path Algorithm with Linear Expected Time

DOI10.1137/070698774MaRDI QIDQ3532580zbMATH OpenOpenAlexFDO

Authors Andrew V. Goldberg

Publication date 28 October 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c80a4935ad5c7faf751822438d39d3a796720ba3

zbMATH Keywords

algorithmsdata structuresexperimental evaluationshortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• PRACTICAL EFFICIENCIES OF EXISTING SHORTEST-PATH ALGORITHMS AND A NEW BUCKET ALGORITHM
• scientific article; zbMATH DE number 1875419
• scientific article; zbMATH DE number 2081016
• Faster algorithms for the shortest path problem
• A theorem on the expected complexity of dijkstra's shortest path algorithm

Cited in

(12)

• Simple linear time approximation algorithm for betweenness
• Simpler computation of single-source shortest paths in linear average time
• User-constrained multimodal route planning
• A novel linear algorithm for shortest paths in networks
• PRACTICAL EFFICIENCIES OF EXISTING SHORTEST-PATH ALGORITHMS AND A NEW BUCKET ALGORITHM
• Via Detours to I/O-Efficient Shortest Paths
• scientific article; zbMATH DE number 3982535 (Why is no real title available?)
• Level graphs and approximate shortest path algorithms
• scientific article; zbMATH DE number 2081016 (Why is no real title available?)
• scientific article; zbMATH DE number 1875419 (Why is no real title available?)
• A forward-backward single-source shortest paths algorithm
• Exploring monotone priority queues for Dijkstra optimization

This page was built for publication: A Practical Shortest Path Algorithm with Linear Expected Time

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