Computing the shortest path: A search meets graph theory

By Andrew Vladislav Goldberg, Chris Harrelson. ACM-SIAM Symposium on Discrete Algorithms, 2005

998 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/e39ba4c989874285e9473b4532dc275c12ed78c0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Yu Zheng
2. Xing Xie
3. Xiaofang Zhou
4. Jiawei Han
5. Hannah Bast
6. Carlos Castillo
7. Jing Yuan
8. Heng Tao Shen

Citations in the corpus

• Scalable network distance browsing in spatial databases (2008, methodology): “, [8, 14, 30]) as an alternative to Dijkstra’s algorithm to compute the shortest path between two vertices.”
• Engineering Route Planning Algorithms (2009, background): “[25] even report a slow-down of more than a factor of two since the search space is not significantly reduced but a considerable overhead is added.”
• Exact Routing in Large Road Networks Using Contraction Hierarchies (2012, background): “In particular, ALT ( A ∗ , L andmarks, T riangle inequality) by Goldberg and Harrelson (2005) yields strong lower bounds that can direct the search toward the target.”
• Map-matching for low-sampling-rate GPS trajectories (2009, background): “Note that a road may contain several road segments.”
• Reach for A*: Efficient Point-to-Point Shortest Path Algorithms (2006, methodology): “Previous work on exact algorithms with preprocessing includes those using geometric information [23, 36], hierarchical decomposition [27, 29, 30], the notion of reach [16], and A∗ search combined with landmark distances [13, 15].”
• A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, unknown): “4”
• Real-time routing with OpenStreetMap data (2011, methodology): “A sophisticated version of an earlier method is A* with landmarks and triangle inequality (ALT) [6].”
• Route Planning in Transportation Networks (2015, methodology): “The corresponding potential function is feasible [148].”
• Discovering popular routes from trajectories (2011, background): “Other related work includes path planning by considering traffic uncertainty [17], searching similar trajectories [18], [19], [20], [21], [22], shortest path [6], [23], shortest path on time-dependent networks [24], finding the fastest path by speed patterns [25], etc.”
• Self-Driving Cars: A Survey (2019, background): “ALT (A*, landmarks, and triangle inequality) algorithm [GOL05] enhances A* by picking a small set of vertices as landmarks.”
• A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks (2011, background): “Arc flags [23, 21] and landmark-based A∗ search [18] reduce the search space by directing the search towards the goal.”
• Large Language Models on Graphs: A Comprehensive Survey (2023, background): “These graph reasoning tasks include inferring connectivity [6], shortest path [7], subgraph matching [8], and logical rule induction [18].”
• Bidirectional Expansion For Keyword Search on Graph Databases (2005, background): “[14] in the context of searching in a state space, and [6] in the context of finding routes on a road network.”
• Fast shortest path distance estimation in large networks (2009, methodology): “were chosen using Goldberg’s farthest heuristic [17].”
• Fast exact and approximate geodesics on meshes (2005, methodology): “As future work, it would be useful to obtain even tighter A* bounds by precomputing distances to a set of landmark points on the mesh, as explored in [Goldberg and Harrelson 2005] for graph search.”