Source-linked AI summary
A Survey of Shortest-Path Algorithms
Amgad Madkour, Walid G. Aref, Faizan Ur Rehman, Mohamed Abdur Rahman, Saleh Basalamah
TL;DR
Shortest-path research covers many problem variants for which no single algorithm is suitable across all space and time constraints. This survey introduces a taxonomy to classify algorithms by graph setting, answer type, and search objective, and reviews the challenges and proposed solutions in each category.
Problem
Shortest-path algorithms address diverse graph variants, and no single algorithm solves all of them because their space and time complexities differ.
Method
The survey introduces a taxonomy organizing shortest-path algorithms by problem flavor, static or dynamic graphs, exact or approximate answers, and time-dependent or goal-directed objectives.
Results
The survey classifies shortest-path algorithms across taxonomy branches and presents the challenges and proposed solutions associated with each category.
Takeaways & Limitations
The taxonomy provides a guideline for mapping a shortest-path problem definition to relevant existing work and selecting an algorithm for a specific setting.
Abstract
from arXiv · showhide
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.
1 Introduction
Shortest-path research spans diverse graph types, applications, and problem variants, motivating a taxonomy that organizes algorithms by their operating settings and objectives.
- Shortest-path algorithms support applications including network routing, route planning, traffic control, social-network path finding, computer games, and transportation systems.
- The problem varies across aspatial, spatial, and planar graphs, whose vertex locations and edge arrangements differ.
- Algorithms address static or dynamic graphs, directed or undirected edges, and negative or non-negative weights.
- Shortest-path computation includes single-source and all-pairs objectives, with algorithms producing either exact or approximate solutions.
- Approximate methods can use spanners, subgraphs that preserve approximate distances while enabling shortest-path computation on a smaller graph.
- The survey’s taxonomy organizes shortest-path algorithms by category to help users select methods for specific scenarios and application domains.
4 PROBLEM DEFINITION
The survey situates shortest-path research among specialized surveys of traffic, dynamic, time-dependent, and heuristic settings. It contributes a broader taxonomy that maps problem definitions to related algorithms and incorporates newer work.
- Prior surveys specialize in traffic applications, dynamic graphs, dynamic weights or topology, and time-dependent FIFO networks.
- This survey differs by providing a taxonomy that helps identify an appropriate algorithm for a specific setting.
- It presents algorithms chronologically within each taxonomy branch to capture the evolution of ideas and methods.
- The formal problem takes a graph G = (V, E), source s, destination d, and weighted edges, seeking a minimum-weight path between s and d.
5 Static Shortest-Path Algorithms
Static shortest-path algorithms address SSSP and APSP under fixed graph settings, with methods differing in edge-weight support, data structures, preprocessing, and approximation. The survey covers classical algorithms, priority-queue improvements, negative-weight handling, approximate distance methods, and query-speedup techniques.
- Static Shortest-Path Algorithms: SSSP computes distances from one source to all vertices, while APSP computes shortest paths between every vertex pair.
- Single-Source Shortest-Path (SSSP): Breadth-first search solves unweighted SSSP by scanning neighbors and finding paths with the minimum number of edges.
- Single-Source Shortest-Path (SSSP): Dijkstra’s algorithm greedily solves directed SSSP with non-negative weights by progressively adding vertices with the shortest identified distances.
- Single-Source Shortest-Path (SSSP): Fibonacci heaps improve Dijkstra’s running time to O(nlogn + m), while other priority-queue structures provide alternative complexity and storage trade-offs.
- Single-Source Shortest-Path (SSSP): Bellman-Ford handles negative edge weights and detects negative cycles, but runs in O(nm) and has no finite shortest path when a negative cycle exists.
- Goal-Directed and Approximate Search: Approximate distance methods trade exactness for efficiency through partial distance queries, triangle-inequality reconstruction, spanners, and graph-region or hierarchical speedups.
6 DYNAMIC SHORTEST-PATH ALGORITHMS
Dynamic shortest-path work includes labeling, hierarchical, and highway-based approaches that trade preprocessing, space, and query efficiency. The survey highlights methods that exploit graph structure to accelerate shortest-path queries, including a dynamic algorithm reported as much faster than Dijkstra’s algorithm.
- Labeling Algorithms: Approximate hub-labeling reduces maximum label size in O(logn) by reducing the hub-labeling problem to set cover, but produces unbalanced label sizes.
- Labeling Algorithms: Two-hop labeling precomputes inbound and outbound labels so shortest-path queries minimize distances through vertices shared by both labels.The approach stores a 2-hops cover of graph paths, with preprocessing described as approximately O(logn) for invariant paths.
- Labeling Algorithms: Multi-hop distance labeling uses parent functions, vertex separation, and connected-subgraph decomposition to obtain smaller labels than a prior 2-hop approach.
- Highway Node Routing: Highway node routing uses prominent vertices shared by many shortest paths to create sparse overlay graphs with faster queries and lower space overhead.
- Highway Node Routing: A dynamic algorithm is reported to be thousand times faster in query time than Dijkstra’s algorithm while remaining space-efficient.It shifts computational complications into preprocessing, simplifying query processing, including dynamic variants.
- Highway Dimension: A sparse set S_r is defined so every shortest path longer than r contains a vertex from S_r when balls of radius O(r) contain fewer vertices than S_r.
6 Dynamic Shortest-Path Algorithms
Dynamic shortest-path algorithms maintain distances while graphs change through insertions, deletions, and weight modifications. The surveyed work spans fully, incrementally, and decrementally dynamic settings for both SSSP and APSP, with exact and approximate trade-offs.
- Dynamic Graph Settings: Dynamic shortest-path algorithms process graph updates online and answer distance queries, with fully dynamic methods supporting both insertions and deletions.Incremental methods support insertions only, while decremental methods support deletions only.
- All-Pairs Shortest Paths: Dynamic APSP maintains distances between any two vertices while handling graph inserts, deletes, and updates.
- All-Pairs Shortest Paths: A fully dynamic directed-graph APSP algorithm with real-valued edge weights achieves amortized update time O(Sn2.5log3n) and optimal worst-case query time.
- All-Pairs Shortest Paths: Thorup reduces fully dynamic APSP to a smaller set of decremental problems, using decremental efficiency to address the fully dynamic case.
- All-Pairs Shortest Paths: Approximate dynamic APSP methods include (2 + ǫ)-approximation with almost-linear updates and O(loglogn) queries, and (1 + ǫ)-approximation with update time o(mn2).The cited approaches target undirected positive-weight graphs or decremental weighted graphs and use randomized procedures.
- Single-Source Shortest Paths: Dynamic SSSP reports distances from one source while supporting online edge insertion, deletion, or weight modification and source-to-target queries.
7 TIME-DEPENDENT SHORTEST-PATH ALGORITHMS
Time-dependent shortest-path algorithms model travel costs through edge-delay functions or time-varying graph structure. The surveyed methods seek fastest paths or best departure times while balancing preprocessing, query efficiency, and changing traffic or topology.
- Planar Graphs: A planar-graph algorithm combines Monge matrices with Bellman-Ford and Dijkstra searches, achieving O(nlog3n) time and O(n4/5log13/5n) amortized updates and queries.
- Dynamic Approximation: Randomized decremental methods for moderately sparse unweighted undirected graphs achieve O(n2+o(1)) total update time with constant query time, later improved to O(n1.8+o(1) + m1+o(1)).
- Time-Dependent Models: Time-dependent shortest-path queries find minimum travel time over edges whose delay functions vary with departure time, returning the best departure time in an interval.
- Time-Dependent Algorithms: One method partitions a specified departure or arrival interval into sub-intervals, assigning fastest paths while probing the graph only once rather than repeatedly as A∗ does.
- Time-Dependent Models: Time-dependent methods address changing traffic, time-varying topology, and edges or vertices absent at particular times.The Time-Aggregated Graph models vertices and edges as time series and supports shortest-path and best-start-time computations.
- Time-Dependent Algorithms: A large-graph least-travel-time algorithm achieves space complexity O((n + m)α(T )) and time complexity O((nlogn + m)α(T )).
8 STOCHASTIC SHORTEST-PATH ALGORITHMS
The supplied passages describe goal-directed shortest-path techniques for time-dependent graphs, emphasizing bidirectional A∗ search, preprocessing, lower-bound functions, and correctness guarantees. They also examine the computational complexity of changing arrival times.
- Goal-Directed Search: Bidirectional A∗ restricts search using a time-independent vertex set, with forward search using a cost function and backward search using a lower-bound function.
- Correctness: Time-dependent techniques commonly preserve correctness by augmenting preprocessing and query-phase subroutines.
- Computational Complexity: With linear edge-cost functions, the shortest path to a destination changes nθ(logn) times, motivating a parametric shortest-path analysis of arrival-time complexity.
- Goal-Directed Search: A bidirectional time-dependent A∗ method partitions a spatial graph during preprocessing and computes lower-bound distance labels for vertices and borders before online fastest-path queries.
8 Stochastic Shortest-Path Algorithms
Stochastic shortest-path algorithms model edge uncertainty and seek paths with minimum expected cost or other probability- and utility-based objectives. The surveyed approaches include adaptive routing, threshold-probability optimization, and utility maximization reducible to classical shortest-path methods.
- Stochastic shortest-path objectives: Stochastic shortest-path problems model edge costs as random variables and seek paths minimizing expected cost.The surveyed research distinguishes adaptive algorithms, which choose the next hop using the current graph, from non-adaptive algorithms focused on path length.
- Adaptive and non-adaptive algorithms: Adaptive algorithms select the next hop from the graph state at a given time, whereas non-adaptive algorithms focus on minimizing path length.
- Probability-based objectives: A threshold-based model selects the path with the highest probability of staying within a specified length threshold.Edge weights are drawn from known probability distributions.
- Utility-based objectives: For linear or exponential monotone utility functions, utility separates across edge lengths and can be optimized with classical shortest-path algorithms.
9 PARAMETRIC SHORTEST-PATH ALGORITHMS
Parametric shortest-path algorithms compute shortest paths as edge values vary with a parameter, identifying breakpoints where the optimal path changes. The surveyed work develops lower-bound models and polynomial-time methods, including a Fibonacci-heap modification of an earlier algorithm.
- Time-dependent optimization: Nikolova et al. formulate route planning using both path length and departure time, with joint optimization reducible to classical shortest-path algorithms.The objective penalizes early and late arrivals.
- Parametric shortest-path objective: Parametric shortest-path algorithms compute shortest paths across parameter values and identify breakpoints where the optimal path changes.Edge values vary according to linear functions of the parameter.
- Lower-bound analysis: The shortest-path cost as a function of the parameter forms a piecewise-linear, concave optimal-cost graph.Breakpoints correspond to a fixed set of linear weight functions on a fixed graph.
- Polynomial-time algorithms: Young et al. modify Karp and Orlin’s algorithm to use Fibonacci heaps, enabling polynomial-time shortest-path computation under their more tractable edge-value model.
- Planar-graph methods: Erickson’s planar-graph maximum-flow algorithm maintains an edge spanning tree, predecessor dual vertices, and dual-edge slacks, initialized in O(nlogn) using Dijkstra’s algorithm.
10 Replacement Shortest-Path Algorithms
Replacement-path algorithms compute shortest paths that avoid each specified edge on an original source-to-destination path. The survey covers exact, randomized, and approximate methods with preprocessing, query, and graph-size-dependent running-time guarantees.
- Replacement-path objective: For each edge on an s-to-d shortest path, replacement-path algorithms compute the shortest s-to-d path that avoids that edge.
- Exact algorithms: An algorithm for weighted planar directed graphs uses O(nlog^3n) preprocessing and answers replacement-path queries in O(hloglogn) time.Here, h is the number of hops.
- Randomized algorithms: A Monte-Carlo randomized algorithm computes replacement paths in unweighted directed graphs in approximately O(m√n) time.The approach also improves the running time of the k-simple shortest-path and Vickrey pricing problems by a factor of √n.
- Approximate algorithms: Bernstein’s approximate (1 + ǫ) algorithm has approximately O(mlog(nC/c)/ǫ) running time, where C/c is the ratio of largest to smallest edge weights.Applied to the k-th simple shortest-path problem, its running time is approximately O(km√n).
11 ALTERNATIVE SHORTEST-PATH ALGORITHMS
Alternative shortest-path algorithms reuse previously computed results for paths avoiding unwanted vertices or edges, unlike replacement paths, which specify the avoided edge. This reuse can improve performance, and SPQF-based storage supports single-source and all-pairs queries.
- Alternative-path formulation: Alternative shortest-path algorithms reuse results for paths avoiding unwanted vertices or edges, seeking better performance than recomputing each replacement path.Unlike replacement paths, the unwanted vertex or edge is not required to be specified in advance for the replacement-path formulation.
- SPQF storage: The SPQF method reduces the number of shortest-path quad-trees stored at each vertex and has O(n^1.5) space complexity.
- Query support: SPQF supports alternative shortest-path queries for both one source-to-destination pair and all source-set to destination-set pairs avoiding a vertex.The reported query time is O(n).
12 Weighted Region Shortest-Path Algorithms
Weighted-region shortest-path research addresses planar environments subdivided into weighted polygonal regions, seeking minimum-cost paths under a weighted Euclidean metric. Surveyed approaches include exact and approximate methods, with path-nets providing bounded approximations.
- The Weighted Region Problem minimizes path cost across weighted polygonal regions under a weighted Euclidean metric.
- Mitchell and Papadimitriou propose a weighted-region algorithm with O(n8L) running time.
- Path-net approximations use Snell’s law to form vertex cones and produce paths within a factor of (1 + ǫ) from the optimum.The path-net has O(kn) vertices and requires O(kn3) worst-case construction time, where k is the number of cones.
13 Conclusion
The paper develops a taxonomy for shortest-path problems and uses it to organize discriminating features and state-of-the-art research across the field.
- The taxonomy classifies shortest-path algorithms by branch and highlights each category’s discriminating features and state-of-the-art research.
- The taxonomy guides investigators in mapping a required shortest-path problem definition to relevant existing work.
- The survey’s taxonomy is intended to support systematic organization of the shortest-path problem.