# A Survey of Shortest-Path Algorithms

arXiv: https://arxiv.org/abs/1705.02044 · HTML: https://mlsanity.com/paper/1705.02044/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2017.

## Built on by (most cited first, 10 of 10)

- [Learning Shortest Paths with Generative Flow Networks](https://mlsanity.com/paper/2603.01786/) (2026)
- [An Extension of BIM Using AI: a Multi Working-Machines Pathfinding Solution](https://mlsanity.com/paper/2105.06635/) (2021)
- [Deep Recurrent Q-learning for Energy-constrained Coverage with a Mobile Robot](https://mlsanity.com/paper/2210.00327/) (2022)
- [An Empirical Survey and Benchmark of Learned Distance Indexes for Road Networks](https://mlsanity.com/paper/2602.04068/) (2026)
- [GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning](https://mlsanity.com/paper/2605.06671/) (2026)
- [ERA*: Enhanced Relaxed A* algorithm for Solving the Shortest Path Problem in Regular Grid Maps](https://mlsanity.com/paper/2308.10988/) (2023)
- [Reciprocal Visibility](https://mlsanity.com/paper/2402.06991/) (2024)
- [Skeleton-Guided Learning for Shortest Path Search](https://mlsanity.com/paper/2508.02270/) (2025)
- [Predictive Spike Timing Enables Distributed Shortest Path Computation in Spiking Neural Networks](https://mlsanity.com/paper/2509.10077/) (2025)
- [Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance](https://mlsanity.com/paper/2606.18267/) (2026)

## Abstract (arXiv)

A shortest-path algorithm finds a path containing the minimal cost between two vertices in a graph. A plethora of shortest-path algorithms is studied in the literature that span across multiple disciplines. This paper presents a survey of shortest-path algorithms based on a taxonomy that is introduced in the paper. One dimension of this taxonomy is the various flavors of the shortest-path problem. There is no one general algorithm that is capable of solving all variants of the shortest-path problem due to the space and time complexities associated with each algorithm. Other important dimensions of the taxonomy include whether the shortest-path algorithm operates over a static or a dynamic graph, whether the shortest-path algorithm produces exact or approximate answers, and whether the objective of the shortest-path algorithm is to achieve time-dependence or is to only be goal directed. This survey studies and classifies shortest-path algorithms according to the proposed taxonomy. The survey also presents the challenges and proposed solutions associated with each category in the taxonomy.