Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm

DOI10.1145/1671970.1671976zbMath1284.05265OpenAlexW2150418461MaRDI QIDQ5406231

Peter Sanders, Daniel Delling, Dominik Schultes, Reinhard Bauer, Dennis Schieferdecker, Dorothea Wagner

Publication date: 1 April 2014

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://publikationen.bibliothek.kit.edu/1000014952

zbMATH Keywords

Dijkstra's algorithmspeed-up technique

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Shortest paths avoiding forbidden subpaths ⋮ Unnamed Item ⋮ Engineering graph-based models for dynamic timetable information systems ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ A Numerical Framework for Nonlinear Peridynamics on Two-Dimensional Manifolds Based on Implicit P-(EC)\(^{ {\boldsymbol k}}\) Schemes ⋮ Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind ⋮ Hybrid Bellman-Ford-Dijkstra algorithm ⋮ Shortest-path queries in static networks ⋮ Unnamed Item ⋮ Core Routing on Dynamic Time-Dependent Road Networks ⋮ Traffic Networks and Flows over Time ⋮ Energy-optimal routes for battery electric vehicles ⋮ Efficient Computation of Shortest Paths in Time-Dependent Multi-Modal Networks ⋮ Candidate Sets for Alternative Routes in Road Networks ⋮ User-Constrained Multimodal Route Planning ⋮ Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates ⋮ Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles ⋮ Non-crossing shortest paths in undirected unweighted planar graphs in linear time ⋮ Dynamically Maintaining Shortest Path Trees under Batches of Updates

This page was built for publication: Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm