The shortest-path problem. Analysis and comparison of methods

DOI10.2200/S00618ED1V01Y201412TCS001MaRDI QIDQ5255986zbMATH OpenOpenAlexFDO

Authors Hector Ortega-Arranz, Diego R. Llanos, Arturo González-Escribano

Publication date 22 June 2015

Published in Synthesis Lectures on Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2200/s00618ed1v01y201412tcs001

zbMATH Keywords

\(A^*\) algorithmDijkstra's algorithmgraph algorithmsgraph searchnon-hierarchical approachespreprocessing-dependent approaches, hierarchical approachesshortest path problem

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph algorithms (graph-theoretic aspects) (05C85) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Point-to-Point Shortest Path Algorithms with Preprocessing
• Reach for \(A^\ast\): efficient point-to-point shortest path algorithms
• Computing the shortest path: A^ search meets graph theory
• Reach for A^*: shortest path algorithms with preprocessing
• Engineering Highway Hierarchies

Cited in

(20)

• A walk over the shortest path: Dijkstra's algorithm viewed as fixed-point computation.
• Shortest path solvers. From software to wetware
• On the isometric path partition problem
• SHORTEST PATH SIMPLEX ALGORITHM WITH A MULTIPLE PIVOT RULE: A COMPARATIVE STUDY
• Application of topology connectedness: the storage structure of information in road network
• A Shortest Path Algorithm Based on Limited Search Heuristics
• Real-world applications of shortest path algorithms
• scientific article; zbMATH DE number 1054931 (Why is no real title available?)
• AN APPROACH TO TRIP- AND ROUTE-PLANNING PROBLEMS
• scientific article; zbMATH DE number 1844689 (Why is no real title available?)
• Study on planning method of optimum route in multi-scale road network based on Dijkstra's algorithm
• Shortest path reoptimization vs resolution from scratch: a computational comparison
• Shortest path algorithms
• An improvement of the Roy-Floyd algorithm
• Shortest-path algorithms and dynamic cost changes
• A discussion of the traffic jam problem in cities
• Shortest paths in a lattice network: A comparative study
• Algorithms for path optimizations: a short survey
• On the hardness of the drone delivery problem
• Heuristic search for one-to-many shortest path queries

This page was built for publication: The shortest-path problem. Analysis and comparison of methods

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