A Survey of Shortest-Path Algorithms
arXiv:1705.02044
Abstract
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.
References in corpus (4)
Cited by in corpus (8)
- A Real-Time Dispatching Strategy for Shared Automated Electric Vehicles with Performance Guarantees
- Recent Advances in Fully Dynamic Graph Algorithms
- Collective Shortest Paths for Minimizing Congestion on Temporal Load-Aware Road Networks
- Dynamic Shortest Path and Transitive Closure Algorithms: A Survey
- On Distributed Routing in Underwater Optical Wireless Sensor Networks
- An Extension of BIM Using AI: a Multi Working-Machines Pathfinding Solution
- Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
- On scenario construction for stochastic shortest path problems in real road networks