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
2189110458 1965948320 2038084411 2130674086
We consider the problem of computing shortest paths through a dynamic network – a network with time-varying characteristics, such as arc travel times and costs, which are known for all values of time. Many types of networks, most notably transportation networks, exhibit such predictable dynamic behavior over the course of time. Dynamic shortest path problems are currently solved in practice by algorithms which operate within a discrete-time framework. In this thesis, we introduce a new set of algorithms for computing shortest paths in continuous-time dynamic networks, and demonstrate for the first time in the literature the feasibility and the advantages of solving dynamic shortest path problems in continuous time. We assume that all time-dependent network data functions are given as piece-wise linear functions of time, a representation capable of easily modeling most common dynamic problems. Additionally, this form of representation and the solution algorithms developed in this thesis are well suited for many augmented static problems such as time-constrained minimum-cost shortest path problems and shortest path problems with time windows. We discuss the classification, formulation, and mathematical properties of all common variants of the continuous-time dynamic shortest path problem. Two classes of solution algorithms are introduced, both of which are shown to solve all variants of the problem. In problems where arc travel time functions exhibit First-In-First-Out (FIFO) behavior, we show that these algorithms have polynomial running time; although the general problem is NP-hard, we argue that the average-case running time for many common problems should be quite reasonable. Computational results are given which support the theoretical analysis of these algorithms, and which provide a comparison with existing discrete-time algorithms; in most cases, continuous-time approaches are shown to be much more efficient, both in running time and storage requirements, than their discretetime counterparts. Finally, in order to further reduce computation time, we introduce parallel algorithms, and hybrid continuous-discrete approximation algorithms which exploit favorable characteristics of algorithms from both domains. Thesis Supervisor: Ismail Chabini Title: Assistant Professor, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology 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. 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.