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.
Demetrescu and Italiano @cite_135 survey algorithms that investigate fully dynamic directed graphs with emphasis on dynamic shortest-paths and dynamic transitive closures. The survey focuses on defining the algebraic and combinatorial properties as well as tools for dynamic techniques. The survey tackles two important questions, namely whether dynamic shortest-paths achieve a space complexity of @math , and whether single-source shortest path algorithms in a fully-dynamic setting be solved efficiently over general graphs. Nannicini and Liberti @cite_68 survey techniques for dynamic graph weights and dynamic graph topology. They list classical and recent techniques for finding trees and shortest-paths in large graphs with dynamic weights. They target two versions of the problem, namely, time-dependence, and what they refer to as cost updates of the weights. Dean's survey @cite_109 focuses on time-dependent techniques in a dynamic setting. It surveys one special case, namely, the First-In-First-Out (FIFO) network as it exposes structural properties that allow for the development of efficient polynomial-time algorithms.
@cite_68 @cite_135 @cite_109
2166460706 1965948320
Abstract In this paper, we survey fully dynamic algorithms for path problems on general directed graphs. In particular, we consider two fundamental problems: dynamic transitive closure and dynamic shortest paths. Although research on these problems spans over more than three decades, in the last couple of years many novel algorithmic techniques have been proposed. In this survey, we will make a special effort to abstract some combinatorial and algebraic properties, and some common data-structural tools that are at the base of those techniques. This will help us try to present some of the newest results in a unifying framework so that they can be better understood and deployed also by non-specialists. Among the variants of the well known shortest path problem, those that refer to a dynamically changing graphs are theoretically interesting, as well as computationally challenging. Applicationwise, there is an industrial need for computing point-to-point shortest paths on large-scale road networks whose arcs are weighted with a travelling time which depends on traffic conditions. We survey recent techniques for dynamic graph weights as well as dynamic graph topology. We obtain the following results related to dynamic versions of the shortest-paths problem: 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. A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of @math (we use @math to hide small poly-logarithmic factors) and a worst case query time is O(n3 4). A deterministic O(n2log n) time algorithm for constructing an O(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. 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.