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.
Zwick @cite_42 survey adopts a theoretical stand-point with regards to the exact and approximate shortest paths algorithms. Zwick's survey addresses single-source shortest-path (SSSP), all pairs shortest-path (APSP), spanners (a weighted graph variation), and distance oracles. The survey illustrates the various variations that each category adopts when handling negative and non-negative edge weights as well as directed and undirected graphs. Sen @cite_41 surveys approximate shortest-paths algorithms with a focus on spanners and distance oracles. Sen's survey discusses how spanners and distance oracles algorithms are constructed and their practical applicability over a static all-pairs shortest-paths setting. Sommer @cite_61 surveys query processing algorithms that trade-off the index size and the query time. Sommer's survey also introduce the transportation network class of algorithms, and include algorithms for general graphs as well as planar and complex graphs.
@cite_41 @cite_42 @cite_61
1581228220 2019003829
We consider the point-to-point (approximate) shortest-path query problem, which is the following generalization of the classical single-source (SSSP) and all-pairs shortest-path (APSP) problems: we are first presented with a network (graph). A so-called preprocessing algorithm may compute certain information (a data structure or index) to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance queries, which should be answered as fast as possible. Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast route planning methods; database and information systems researchers investigate materialization tradeoffs, query processing on spatial networks, and reachability queries; and theoretical computer scientists analyze distance oracles and sparse spanners. Related problems are considered for compact routing and distance labeling schemes in networking and distributed computing and for metric embeddings in geometry as well. In this survey, we review selected approaches, algorithms, and results on shortest-path queries from these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguable practical significance such as planar graphs and complex networks. Computing all-pairs distances in a graph is a fundamental problem of computer science but there has been a status quo with respect to the general problem of weighted directed graphs. In contrast, there has been a growing interest in the area of algorithms for approximate shortest paths leading to many interesting variations of the original problem. In this article, we trace some of the fundamental developments like spanners and distance oracles, their underlying constructions, as well as their applications to the approximate all-pairs shortest paths. We obtain the following results related to dynamic versions of the shortest-paths problem: (i) Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems. (ii) A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of O(mn) and a worst case query time is O(n 3 4 ). (iii) A deterministic O(n 2 log n) time algorithm for constructing a (log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.