A Survey of Shortest-Path Algorithms
---
paper_title: Heuristic shortest path algorithms for transportation applications: state of the art

paper_content:

There are a number of transportation applications that require the use of a heuristic shortest path algorithm rather than one of the standard, optimal algorithms. This is primarily due to the requirements of some transportation applications where shortest paths need to be quickly identified either because an immediate response is required (e.g., in-vehicle route guidance systems) or because the shortest paths need to be recalculated repeatedly (e.g., vehicle routing and scheduling). For this reason a number of heuristic approaches have been advocated for decreasing the computation time of the shortest path algorithm. This paper presents a survey review of various heuristic shortest path algorithms that have been developed in the past. The goal is to identify the main features of different heuristic strategies, develop a unifying classification framework, and summarize relevant computational experience.
---
paper_title: Shortest-path queries in static networks

paper_content:

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.
---
paper_title: Dynamic shortest paths and transitive closure: algorithmic techniques and data structures

paper_content:

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.
---
paper_title: Approximating Shortest Paths in Graphs

paper_content:

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.
---
paper_title: Combining speed-up techniques for shortest-path computations

paper_content:

In practice, computing a shortest path from one node to another in a directed graph is a very common task. This problem is classically solved by Dijkstra's algorithm. Many techniques are known to speed up this algorithm heuristically, while optimality of the solution can still be guaranteed. In most studies, such techniques are considered individually. The focus of our work is combination of speed-up techniques for Dijkstra's algorithm. We consider all possible combinations of four known techniques, namely, goal-directed search, bidirectional search, multilevel approach, and shortest-path containers, and show how these can be implemented. In an extensive experimental study, we compare the performance of the various combinations and analyze how the techniques harmonize when jointly applied. Several real-world graphs from road maps and public transport and three types of generated random graphs are taken into account.
---
paper_title: Shortest paths on dynamic graphs

paper_content:

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.
---
paper_title: Design and implementation of an efficient priority queue

paper_content:

We present a data structure, based upon a hierarchically decomposed tree, which enables us to manipulate on-line a priority queue whose priorities are selected from the interval 1,⋯,n with a worst case processing time of\(\mathcal{O}\) (log logn) per instruction. The structure can be used to obtain a mergeable heap whose time requirements are about as good. Full details are explained based upon an implementation of the structure in a PASCAL program contained in the paper.
---
paper_title: Trans-dichotomous algorithms for minimum spanning trees and shortest paths

paper_content:

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure, the atomic heap. The atomic heap accommodates heap (priority queue) operations in constant amortized time under suitable polylog restrictions on the heap size. The linear-time minimum spanning tree algorithm results from a direct application of the atomic heap. To obtain the shortest path algorithm, the atomic heap is used as a building block to construct a new data structure, the AF-heap, which has no size restrictions and surpasses information theoretic limitations. The AF-heap belongs to the Fibonacci heap family. >
---
paper_title: Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms

paper_content:

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.
---
paper_title: Randomized Speedup of the Bellman-Ford Algorithm

paper_content:

We describe a variant of the Bellman-Ford algorithm for single-source shortest paths in graphs with negative edges but no negative cycles that randomly permutes the vertices and uses this randomized order to process the vertices within each pass of the algorithm. The modification reduces the worst-case expected number of relaxation steps of the algorithm, compared to the previously-best variant by Yen (1970), by a factor of 2/3 with high probability. We also use our high probability bound to add negative cycle detection to the randomized algorithm.
---
paper_title: Preserving order in a forest in less than logarithmic time

paper_content:

We present a data structure, based upon a stratified binary tree, which enables us to manipulate on-line a priority queue whose priorities are selected from the interval 1...n, with an average and worst case processing time of O(log log n) per instruction. The structure is used to obtain a mergeable heap whose time requirements are about as good.
---
paper_title: Dynamic programming : foundations and principles

paper_content:

Introduction Welcome to Dynamic Programming! How to Read This Book SCIENCE Fundamentals Introduction Meta-Recipe Revisited Problem Formulation Decomposition of the Solution Set Principle of Conditional Optimization Conditional Problems Optimality Equation Solution Procedure Time Out: Direct Enumeration! Equivalent Conditional Problems Modified Problems The Role of a Decomposition Scheme Dynamic Programming Problem - Revisited Trivial Decomposition Scheme Summary and a Look Ahead Multistage Decision Model Introduction A Prototype Multistage Decision Model Problem vs Problem Formulation Policies Markovian Policies Remarks on the Notation Summary Bibliographic Notes Dynamic Programming - An Outline Introduction Preliminary Analysis Markovian Decomposition Scheme Optimality Equation Dynamic Programming Problems The Final State Model Principle of Optimality Summary Solution Methods Introduction Additive Functional Equations Truncated Functional Equations Nontruncated Functional Equations Summary Successive Approximation Methods Introduction Motivation Preliminaries Functional Equations of Type One Functional Equations of Type Two Truncation Method Stationary Models Truncation and Successive Approximation Summary Bibliographic Notes Optimal Policies Introduction Preliminary Analysis Truncated Functional Equations Nontruncated Functional Equations Successive Approximation in the Policy Space Summary Bibliographic Notes The Curse of Dimensionality Introduction Motivation Discrete Problems Special Cases Complete Enumeration Conclusions The Rest Is Mathematics and Experience Introduction Choice of Model Dynamic Programming Models Forward Decomposition Models Practice What You Preach! Computational Schemes Applications Dynamic Programming Software Summary ART Refinements Introduction Weak-Markovian Condition Markovian Formulations Decomposition Schemes Sequential Decision Models Example Shortest Path Model The Art of Dynamic Programming Modeling Summary Bibliographic Notes The State Introduction Preliminary Analysis Mathematically Speaking Decomposition Revisited Infeasible States and Decisions State Aggregation Nodes as States Multistage vs Sequential Models Models vs Functional Equations Easy Problems Modeling Tips Concluding Remarks Summary Parametric Schemes Introduction Background and Motivation Fractional Programming Scheme C-Programming Scheme Lagrange Multiplier Scheme Summary Bibliographic Notes The Principle of Optimality Introduction Bellman's Principle of Optimality Prevailing Interpretation Variations on a Theme Criticism So What Is Amiss? The Final State Model Revisited Bellman's Treatment of Dynamic Programming Summary Post Script: Pontryagin's Maximum Principle Forward Decomposition Introduction Function Decomposition Initial Problem Separable Objective Functions Revisited Modified Problems Revisited Backward Conditional Problems Revisited Markovian Condition Revisited Forward Functional Equation Impact on the State Space Anomaly Pathologic Cases Summary and Conclusions Bibliographic Notes Push! Introduction The Pull Method The Push Method Monotone Accumulated Return Processes Dijkstra's Algorithm Summary Bibliographic Notes EPILOGUE What Then Is Dynamic Programming? Review Non-Optimization Problems An Abstract Dynamic Programming Model Examples The Towers of Hanoi Problem Optimization-Free Dynamic Programming Concluding Remarks Appendix A: Contraction Mapping Appendix B: Fractional Programming Appendix C: Composite Concave Programming Appendix D: The Principle of Optimality in Stochastic Processes Appendix E: The Corridor Method Bibliography Index
---
paper_title: NETWORK FLOW THEORY

paper_content:

Abstract : The labeling algorithm for the solution of maximal network flow problems and its application to various problems of the transportation type are discussed.
---
paper_title: Surpassing the information theoretic bound with fusion trees

paper_content:

Abstract This paper introduces a new sublogarithmic data structure for searching, the fusion tree. These trees lead to improved worst-case algorithms for sorting and searching, surpassing the limitations of the information theoretic lower bound.
---
paper_title: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation

paper_content:

The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap—a sequence of m decrease_key and n delete_min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case—O(1) time for decrease_key and O(log n) for delete_min. Relaxed heaps give a processor-efficient parallel implementation of Dijkstra's shortest path algorithm, and hence other algorithms in network optimization. A relaxed heap is a type of binomial queue that allows heap order to be violated.
---
paper_title: Improved fast integer sorting in linear space

paper_content:

We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, ?, m?1} in linear space in O(n log log n log log log n) time. When log m?log2+?n, ?>0, we can further achieve O(n log log n) time. This improves the O(n(log log n)2) time bound given in M. Thorup (1998) in “Proc. 1998 ACM-SIAM Symp. on Discrete Algorithms (SODA'98),” pp. 550?555). This result is obtained by combining our new technique with that of Thorup's. Signature sorting (A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, 1995, in “Proc. 1995 Symposium on Theory of Computing,” pp. 427?436), A. Andersson's result (1996, in “Proc. 1996 IEEE Symp. on Foundations of Computer Science,” pp. 135?141), R. Raman's result (1996, Lecture Notes in Computer Science, Vol. 1136, pp. 121?137, Springer-Verlag Berlin/New York), and our previous result (Y. Han and X. Shen, 1999, in “Proc. 1999 Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99),” Baltimore, MD, January, pp. 419?428) are also used for the design of our algorithms. We provide an approach and techniques which are totally different from previous approaches and techniques for the problem. As a consequence our technique can be extended to apply to nonconservative sorting and parallel sorting. Our nonconservative sorting algorithm sorts n integers in {0, 1, ?, m?1} in time O(n(log log n)2/(log k+log log log n)) using word length k log(m+n), where k?log n. Our EREW parallel algorithm sorts n integers in {0, 1, ?, m?1} in O((log n)2) time and O(n(log log n)2/log log log n) operations provided log m=?((log n)2).
---
paper_title: Undirected single-source shortest paths with positive integer weights in linear time

paper_content:

The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertex s , find the shortest path from s to all other vertices in the graph. Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from s . Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from s . However, we do not know how to sort in linear time. Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.
---
paper_title: ON A ROUTING PROBLEM

paper_content:

Abstract : Given a set of N cities, with every two linked by a road, and the times required to traverse these roads, we wish to determine the path from one given city to another given city which minimizes the travel time. The times are not directly proportional to the distances due to varying quality of roads, and v varying quantities of traffic. The functional equation technique of dynamic programming, combined with approximation in policy space, yield an iterative algorithm which converges after at most (N-1) iterations.
---
paper_title: Introduction to Algorithms

paper_content:

From the Publisher: ::: The updated new edition of the classic Introduction to Algorithms is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Like the first edition,this text can also be used for self-study by technical professionals since it discusses engineering issues in algorithm design as well as the mathematical aspects. ::: In its new edition,Introduction to Algorithms continues to provide a comprehensive introduction to the modern study of algorithms. The revision has been updated to reflect changes in the years since the book's original publication. New chapters on the role of algorithms in computing and on probabilistic analysis and randomized algorithms have been included. Sections throughout the book have been rewritten for increased clarity,and material has been added wherever a fuller explanation has seemed useful or new information warrants expanded coverage. ::: As in the classic first edition,this new edition of Introduction to Algorithms presents a rich variety of algorithms and covers them in considerable depth while making their design and analysis accessible to all levels of readers. Further,the algorithms are presented in pseudocode to make the book easily accessible to students from all programming language backgrounds. ::: Each chapter presents an algorithm,a design technique,an application area,or a related topic. The chapters are not dependent on one another,so the instructor can organize his or her use of the book in the way that best suits the course's needs. Additionally,the new edition offers a 25% increase over the first edition in the number of problems,giving the book 155 problems and over 900 exercises thatreinforcethe concepts the students are learning.
---
paper_title: Finding the hidden path: time bounds for all-pairs shortest paths

paper_content:

The all-pairs shortest-paths problem in weighted graphs is investigated. An algorithm—the Hidden-Paths Algorithm—that finds these paths in time $O(m^ * n + n^2 \log n)$, where $m^ * $ is the number of edges participating in shortest paths, is presented. The algorithm is a practical substitute for Dijkstra’s algorithm. It is argued that $m^ * $ is likely to be small in practice since $m^ * = O(n\log n)$ with high probability for many probability distributions on edge weights. An $\Omega (mn)$ lower bound on the running time of any path-comparison-based algorithm for the all-pairs shortest-paths problem is also proved. Path-comparison-based algorithms form a natural class containing the Hidden-Paths Algorithm, as well as the algorithms of E. W. Dijkstra [Numer. Math., 1 (1959), pp. 269–271] and R. W. Floyd [Comm. ACM, 5 (1962), p. 345]. Lastly, generalized forms of the shortest-paths problem are considered, and it is shown that many of the standard shortest-paths algorithms are effective in this more genera...
---
paper_title: A new approach to dynamic all pairs shortest paths

paper_content:

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n2log3n) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice.
---
paper_title: Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time

paper_content:

For any fixed $1 ≫ \eps ≫ 0$ we present a fully dynamic algorithm for maintaining $(2 + \eps)$-approximate all-pairs shortest paths in undirected graphs with positive edge weights. We use a randomized (Las Vegas) update algorithm (but a deterministic query procedure), so the time given is the \emph{expected} amortized update time. \\\indent Our query time $O(\log \log \log n)$. The update time is $\widetilde{O}(mn^{O(1/\sqrt{\log n})}\log(nR))$, where $R$ is the ratio between the heaviest and the lightest edge weight in the graph (so $R = 1$ in unweighted graphs). Unfortunately, the update time does have the drawback of a super-polynomial dependence on $\eps$: it grows as $(3 / \eps)^{\sqrt{\log n / \log(3/\eps)}} = n^{\sqrt{\log(3/\eps) / \log n}}$.\\\indent Our algorithm has a significantly faster update time than any other algorithm with sub-polynomial query time. For exact distances, the state of the art algorithm has an update time of $\widetilde{O}(n^2)$. For approximate distances, the best previous algorithm has a $O(kmn^{1/k})$ update time and returns $(2k - 1)$ stretch paths. Thus, it needs an update time of $O(m\sqrt{n})$ to get close to our approximation, and it has to return $O(\sqrt{\log n})$ approximate distances to match our update time.
---
paper_title: More algorithms for all-pairs shortest paths in weighted graphs

paper_content:

In the first part of the paper, we reexamine the all-pairsshortest paths (APSP) problem and present a newalgorithm with running time approaching O(n3/log2n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors. In the second part of the paper, we use fast matrix multiplication to obtain truly subcubic APSP algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. For example, for graphs embedded in Euclidean space of a constant dimension d, we obtain a time bound near O(n3-(3-Ω)/(2d+4)), where Ω
---
paper_title: All-pairs shortest paths with a sublinear additive error

paper_content:

We show that, for every 0 ≤ p ≤ 1, there is an O(n2.575−p/(7.4−2.3p))-time algorithm that given a directed graph with small positive integer weights, estimates the length of the shortest path between every pair of vertices u, v in the graph to within an additive error Δp(u, v), where Δ(u, v) is the exact length of the shortest path between u and v. This algorithm runs faster than the fastest algorithm for computing exact shortest paths for any 0 Previously the only way to “beat” the running time of the exact shortest path algorithms was by applying an algorithm of Zwick [2002] that approximates the shortest path distances within a multiplicative error of (1 + e). Our algorithm thus gives a smooth qualitative and quantitative transition between the fastest exact shortest paths algorithm, and the fastest approximation algorithm with a linear additive error. In fact, the main ingredient we need in order to obtain the above result, which is also interesting in its own right, is an algorithm for computing (1 + e) multiplicative approximations for the shortest paths, whose running time is faster than the running time of Zwick's approximation algorithm when e L 1 and the graph has small integer weights.
---
paper_title: Matrix multiplication via arithmetic progressions

paper_content:

We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.
---
paper_title: Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs

paper_content:

We present an improved algorithm for maintaining all-pairs $(1 + \epsilon)$ approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem is total update time $\widetilde{O}(n^2\sqrt{m}/\epsilon)$ over all updates for directed unweighted graphs [S. Baswana, R. Hariharan, and S. Sen, J. Algorithms, 62 (2007), pp. 74--92], and $\widetilde{O}(mn/\epsilon)$ for undirected unweighted graphs [L. Roditty and U. Zwick, in Proceedings of the 45th FOCS, Rome, Italy, 2004, pp. 499--508]. Both algorithms are randomized and have constant query time. Very recently, Henzinger, Krinninger, and Nanongkai presented a deterministic version of the latter algorithm [M. Henzinger, S. Krinninger, and D. Nanongkai, in IEEE FOCS, 2013, pp. 538--547]. Note that $\widetilde{O}(mn)$ is a natural barrier because even with a $(1 + \epsilon)$ approximation, there is no $o(mn)$ combinatorial algorithm for the static all-pairs shortest path problem. Our algorithm works on directed weighte...
---
paper_title: Faster shortest-path algorithms for planar graphs

paper_content:

We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph with the source and sink on the same face. The previous best algorithms for these problems required $\Omega(n \sqrt{\log n})$ time where $n$ is the number of nodes in the input graph. For the case where negative edge-lengths are allowed, we give an algorithm requiring $O(n^{4/3} \log nL)$ time, where $L$ is the absolute value of the most negative length. Previous algorithms for shortest paths with negative edge-lengths required $\Omega(n^{3/2})$ time. Our shortest-path algorithm yields an $O(n^{4/3} \log n)$-time algorithm for finding a perfect matching in a planar bipartite graph. A similar improvement is obtained for maximum flow in a directed planar graph.
---
paper_title: Planar graphs, negative weight edges, shortest paths, and near linear time

paper_content:

In this paper, we present an O(n log3 n) time algorithm for finding shortest paths in an n-node planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by Lipton, Rose, and Tarjan in 1978 which runs in O(n3/2) time, and the best polynomial time algorithm developed by Henzinger, Klein, Subramanian, and Rao in 1994 which runs in O(n 4/3) time. We also present significantly improved data structures for reporting distances between pairs of nodes and algorithms for updating the data structures when edge weights change.
---
paper_title: Exact Distance Oracles for Planar Graphs

paper_content:

We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation $S\in[n\lg\lg n,n^2]$, we show how to construct in $\tilde O(S)$ time a data structure of size $O(S)$ that answers distance queries in $\tilde O(n/\sqrt S)$ time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever $k\in[\sqrt n,n)$. * We provide a linear-space exact distance oracle for planar graphs with query time $O(n^{1/2+eps})$ for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space $\tilde O(n)$ such that for any pair of nodes at distance D the query time is $\tilde O(min {D,\sqrt n})$. Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with $c = O(\sqrt n)$ nodes, we can preprocess G in $\tilde O(n)$ time to produce a data structure of size $O(n \lg\lg c)$ that can answer the following queries in $\tilde O(c)$ time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For $\sigma\in(1,4/3)$ and space $S=n^\sigma$, we essentially improve the query time from $n^2/S$ to $\sqrt{n^2/S}$.
---
paper_title: Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm

paper_content:

We give an O(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires O(n log3 n) time and O(n log n) space.
---
paper_title: Many Distances in Planar Graphs

paper_content:

Let G be a planar graph with n vertices and non-negative edge-lengths. Given a set of k pairs of vertices, we are interested in computing the distance in G between those k pairs of vertices. We describe how this can be achieved in O(n2/3k2/3 log n + n4/3log1/3 n) time, improving previous results for a large range of k. As possible applications, we show how this result speeds up previous algorithms for finding shortest non-contractible cycles for graphs on a bounded-genus surface or for computing the dilation of a geometric planar graph.
---
paper_title: Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

paper_content:

Abstract Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G can be computed in o ( n 2 ) time. We show that both problems can be solved in O ( n 2 log log n / log n ) time with O ( n ) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G. More generally, for any parameter S ∈ [ ( log n / log log n ) 2 , n 2 / 5 ] , distance queries can be answered in O ( S log S / log n ) time per query with O ( n 2 / S ) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when log S = o ( log n ) . All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.
---
paper_title: $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs

paper_content:

An {\em $(\alpha,\beta)$-spanner} of a graph G is a subgraph H such that $\mathit{dist}_H(u,w)\le \alpha\cdot \mathit{dist}t_G(u,w)+\beta$ for every pair of vertices u,w, where distG'(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible $(2\kappa-1,0)$-spanner (also known as multiplicative $(2\kappa-1)$-spanner) of size $O(n^{1+1/\kappa})$ for every integer $\kappa\ge 1$, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size ${\tilde O}(n^{3/2})$. This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant $\epsilon, \lambda > 0$ there exists a constant $\beta = \beta(\epsilon, \lambda)$ such that for every $n$-vertex graph G there is an efficiently constructible $(1+ \epsilon, \beta)$-spanner of size $O(n^{1 + \lambda})$.
---
paper_title: Shortest-path queries in static networks

paper_content:

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.
---
paper_title: Distance Oracles beyond the Thorup--Zwick Bound

paper_content:

We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick. For unweighted undirected graphs, our distance oracle has size $O(n^{5/3})$ and, when queried about vertices at distance $d$, returns a path of length at most 2d+1. For weighted undirected graphs with $m=n^2/\alpha$ edges, our distance oracle has size $O(n^2 / \sqrt[3]{\alpha})$ and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space $\widetilde{\Omega}(n^2 / \sqrt{\alpha})$. For unweighted graphs, this implies a $\widetilde{\Omega}(n^{1.5})$ space lower bound to achieve approximation 2d+1.
---
paper_title: All-pairs small-stretch paths

paper_content:

Let G=(V,E) be a weighted undirected graph. A path between u,v?V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n×n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH2, runs in O(n3/2m1/2) time and finds stretch 2 paths. The second algorithm, STRETCH7/3, runs in O(n7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH3, runs in O(n2) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.
---
paper_title: Compact oracles for reachability and approximate distances in planar digraphs

paper_content:

It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from {0, …, N}, it approximates distances within a factor (1 + e) in O(log log (nN) + 1/e) time. Our scheme can be extended to find and route along correspondingly short dipaths.
---
paper_title: Approximate distance queries and compact routing in sparse graphs

paper_content:

A distance oracle is a compact representation of the shortest distance matrix of a graph. It can be queried to approximate shortest paths between any pair of vertices. Any distance oracle that returns paths of worst-case stretch (2k-1) must require space $\Omega(n^{1 + 1/k})$ for graphs of n nodes. The hard cases that enforce this lower bound are, however, rather dense graphs with average degree \Omega(n^{1/k}). We present distance oracles that, for sparse graphs, substantially break the lower bound barrier at the expense of higher query time. For any 1 \leq \alpha \leq n, our distance oracles can return stretch 2 paths using O(m + n^2/\alpha) space and stretch 3 paths using O(m + n^2/\alpha^2) space, at the expense of O(\alpha m/n) query time. By setting appropriate values of \alpha, we get the first distance oracles that have size linear in the size of the graph, and return constant stretch paths in non-trivial query time. The query time can be further reduced to O(\alpha), by using an additional O(m \alpha) space for all our distance oracles, or at the cost of a small constant additive stretch. We use our stretch 2 distance oracle to present the first compact routing scheme with worst-case stretch 2. Any compact routing scheme with stretch less than 2 must require linear memory at some nodes even for sparse graphs; our scheme, hence, achieves the optimal stretch with non-trivial memory requirements. Moreover, supported by large-scale simulations on graphs including the AS-level Internet graph, we argue that our stretch-2 scheme would be simple and efficient to implement as a distributed compact routing protocol.
---
paper_title: All Pairs Almost Shortest Paths

paper_content:

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth et al. [SIAM J. Comput., 28 (1999), pp. 1167--1181], we describe an $\Ot(\min\{n^{3/2}m^{1/2},n^{7/3}\})$-time algorithm APASP2 for computing all distances in G with an additive one-sided error of at most 2. Algorithm APASP2 is simple, easy to implement, and faster than the fastest known matrix-multiplication algorithm. Furthermore, for every even k>2, we describe an ${\tilde{O}}(\min\{n^{2-{2}/{(k+2)}}m^{{2}/{(k+2)}}, n^{2+{2}/{(3k-2)}}\})$-time algorithm APASPk for computing all distances in G with an additive one-sided error of at most k. We also give an ${\tilde{O}}(n^2)$-time algorithm ${\bf APASP}_\infty$ for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in ${\tilde{O}}(n^2)$ time. ::: We say that a weighted graph F=(V,E') k-emulates an unweighted graph G=(V,E) if for every $u,v\in V$ we have $\delta_G(u,v)\le \delta_F(u,v)\le \delta_G(u,v)+k$. We show that every unweighted graph on n vertices has a 2-emulator with ${\tilde{O}}(n^{3/2})$ edges and a 4-emulator with ${\tilde{O}}(n^{4/3})$ edges. These results are asymptotically tight. ::: Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with ${\tilde{O}}(n^{3/2})$ edges and that such a 3-spanner can be built in ${\tilde{O}}(mn^{1/2})$ time. We also describe an ${\tilde{O}}(n(m^{2/3}+n))$-time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.
---
paper_title: A compact routing scheme and approximate distance oracle for power-law graphs

paper_content:

Compact routing addresses the tradeoff between table sizes and stretch, which is the worst-case ratio between the length of the path a packet is routed through by the scheme and the length of an actual shortest path from source to destination. We adapt the compact routing scheme by Thorup and Zwick [2001] to optimize it for power-law graphs. We analyze our adapted routing scheme based on the theory of unweighted random power-law graphs with fixed expected degree sequence by Aiello et al. [2000]. Our result is the first analytical bound coupled to the parameter of the power-law graph model for a compact routing scheme. ::: Let <i>n</i> denote the number of nodes in the network. We provide a <i>labeled</i> routing scheme that, after a stretch--5 handshaking step (similar to DNS lookup in TCP/IP), routes messages along stretch--3 paths. We prove that, instead of routing tables with <i>Õ</i>(<i>n</i><sup>1/2</sup>) bits (<i>Õ</i> suppresses factors logarithmic in <i>n</i>) as in the general scheme by Thorup and Zwick, expected sizes of <i>O</i>(<i>n<sup>γ</sup></i> log <i>n</i>) bits are sufficient, and that all the routing tables can be constructed at once in expected time <i>O</i>(<i>n<sup>1+γ</sup></i> log <i>n</i>), with γ = τ-22/τ-3 + ϵ, where τ∈(2,3) is the power-law exponent and ϵ 0 (which implies ϵ < γ < 1/3 + ϵ). Both bounds also hold with probability at least 1-1/<i>n</i> (independent of ϵ). The routing scheme is a labeled scheme, requiring a stretch--5 handshaking step. The scheme uses addresses and message headers with <i>O</i>(log <i>n</i> log log <i>n</i>) bits, with probability at least 1-<i>o</i>(1). We further demonstrate the effectiveness of our scheme by simulations on real-world graphs as well as synthetic power-law graphs. ::: With the same techniques as for the compact routing scheme, we also adapt the approximate distance oracle by Thorup and Zwick [2001, 2005] for stretch-3 and we obtain a new upper bound of expected <i>Õ</i>(<i>n</i><sup>1+γ</sup>) for space and preprocessing for random power-law graphs. Our distance oracle is the first one optimized for power-law graphs. Furthermore, we provide a linear-space data structure that can answer 5--approximate distance queries in time at most <i>Õ</i>(<i>n</i><sup>1/4+ϵ</sup>) (similar to γ, the exponent actually depends on τ and lies between ϵ and 1/4 + ϵ).
---
paper_title: Fast estimation of diameter and shortest paths (without matrix multiplication)

paper_content:

In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths problem running in time significantly smaller than the obvious time bound of O(n^3). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that we present algorithms with a small additive error in the length of the paths obtained. Our algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small. Our main result is an algorithm which solves the all-pairs shortest paths problem in unweighted, undirected graphs with an additive error of 2 in time O(n^{2.5} sqrt{log n}). This algorithm returns actual paths and not just the distances. In addition, we give more efficient algorithms with running time O(n^{1.5} sqrt{k log n} + n^2 log^2 n) for the case where we are only required to determine shortest paths between k specified pairs of vertices rather than all pairs of vertices. The starting point for all our results is an O(m sqrt{n log n}) algorithm for distinguishing between graphs of diameter 2 and 4, and this is later extended to obtaining a ratio 2/3 approximation to the diameter in time O(m sqrt{n log n} + n^2 log n). Unlike in the case of all-pairs shortest paths, our results for approximate diameter computation can be extended to the case of directed graphs with arbitrary positive real weights on the edges.
---
paper_title: All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms

paper_content:

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in O/spl tilde/(n/sup 2+/spl mu//) time, where /spl mu/ satisfies the equation /spl omega/(1,/spl mu/,1)=1+2/spl mu/ and /spl omega/(1,/spl mu/,1) is the exponent of the multiplication of an n/spl times/n/sup /spl mu// matrix by an n/sup /spl mu///spl times/n matrix. The currently best available bounds on /spl omega/(1,/spl mu/,1), obtained by Coppersmith and Winograd, and by Huang and Pan, imply that /spl mu/ 0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1+/spl epsiv/. Corresponding paths can also be found efficiently.
---
paper_title: Generalized nested dissection

paper_content:

J. A. George has discovered a method, called nested dissection, for solving a system of linear equations defined on an n = k $\times$ k square grid in O(n log n) space and O($n{3/2}$) time. We generalize this method without degrading the time and space bounds so that it applies to any system of equations defined on a planar or almost-planar graph. Such systems arise in the solution of two-dimensional finite element problems. Our method uses the fact that planar graphs have good separators. More generally, we show that sparse Gaussian elimination is efficient for any class of graphs which have good separators, and conversely that graphs without good separators (including almost all sparse graphs) are not amenable to sparse Gaussian elimination.
---
paper_title: Triangulation and embedding using small sets of beacons

paper_content:

Concurrent with recent theoretical interest in the problem of metric embedding, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of recent approaches that approximately embed this distance matrix into low-dimensional Euclidean space. There is a fundamental distinction, however, between the theoretical approaches to the embedding problem and this recent Internet-related work: in addition to computational limitations, Internet measurement algorithms operate under the constraint that it is only feasible to measure distances for a linear (or near-linear) number of node pairs, and typically in a highly structured way. Indeed, the most common framework for Internet measurements of this type is a beacon-based approach one chooses uniformly at random a constant number of nodes (“beacons”) in the network, each node measures its distance to all beacons, and one then has access to only these measurements for the remainder of the algorithm. Moreover, beacon-based algorithms are often designed not for embedding but for the more basic problem of triangulation, in which one uses the triangle inequality to infer the distances that have not been measured. Here we give algorithms with provable performance guarantees for beacon-based triangulation and embedding. We show that in addition to multiplicative error in the distances, performance guarantees for beacon-based algorithms typically must include a notion of slack—a certain fraction of all distances may be arbitrarily distorted. For metric spaces of bounded doubling dimension (which have been proposed as a reasonable abstraction of Internet latencies), we show that triangulation-based distance reconstruction with a constant number of beacons can achieve multiplicative error 1 + Δ on a 1 − e fraction of distances, for arbitrarily small constants Δ and e. For this same class of metric spaces, we give a beacon-based embedding algorithm that achieves constant distortion on a 1 − e fraction of distances; this provides some theoretical justification for the success of the recent Global Network Positioning algorithm of Ng and Zhang [2002], and it forms an interesting contrast with lower bounds showing that it is not possible to embed all distances in a doubling metric space with constant distortion. We also give results for other classes of metric spaces, as well as distributed algorithms that require only a sparse set of distances but do not place too much measurement load on any one node.
---
paper_title: A Formal Basis for the Heuristic Determination of Minimum Cost Paths

paper_content:

Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.
---
paper_title: Goal directed shortest path queries using precomputed cluster distances

paper_content:

We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong “sense of direction”. We evaluate our approach experimentally using large, real-world road networks.
---
paper_title: Fast shortest path distance estimation in large networks

paper_content:

In this paper we study approximate landmark-based methods for point-to-point distance estimation in very large networks. These methods involve selecting a subset of nodes as landmarks and computing offline the distances from each node in the graph to those landmarks. At runtime, when the distance between a pair of nodes is needed, it can be estimated quickly by combining the precomputed distances. We prove that selecting the optimal set of landmarks is an NP-hard problem, and thus heuristic solutions need to be employed. We therefore explore theoretical insights to devise a variety of simple methods that scale well in very large networks. The efficiency of the suggested techniques is tested experimentally using five real-world graphs having millions of edges. While theoretical bounds support the claim that random landmarks work well in practice, our extensive experimentation shows that smart landmark selection can yield dramatically more accurate results: for a given target accuracy, our methods require as much as 250 times less space than selecting landmarks at random. In addition, we demonstrate that at a very small accuracy loss our techniques are several orders of magnitude faster than the state-of-the-art exact methods. Finally, we study an application of our methods to the task of social search in large graphs.
---
paper_title: Fast Point-to-Point Shortest Path Computations with Arc-Flags.

paper_content:

We present a number of improvements of the basic variant of the arc-flag acceleration (Lauther, 1997, 2004) for point-to-point (P2P) shortest path computations on large graphs. Arc-flags are a modification to the standard Dijkstra algorithm and are used to avoid exploring unnecessary paths during shortest path computation. We assume that for the same input graph the shortest path problem has to be solved repeatedly for different node pairs. Thus, precomputing the arc-flags is possible. We show that the improved arc-flag acceleration achieves speedups of P2P shortest path queries of more than 1,470 on a subnetwork of the German road network with 1M node and 2.5M arcs using 450 bits of additional information per arc. The acceleration factors increase with the size of the input graph. Finally, we present an improved preprocessing version which allows precomputing arc-flags for European and North-American road networks within hours.
---
paper_title: Goal directed shortest path queries using precomputed cluster distances

paper_content:

We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong “sense of direction”. We evaluate our approach experimentally using large, real-world road networks.
---
paper_title: SHARC: Fast and robust unidirectional routing

paper_content:

During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, the most advanced techniques use bidirectional search which makes it hard to use them in scenarios where a backward search is prohibited. Even worse, such scenarios are widely spread, e.g., timetable-information systems or time-dependent networks. ::: ::: In this work, we present a unidirectional speed-up technique which competes with bidirectional approaches. Moreover, we show how to exploit the advantage of unidirectional routing for fast exact queries in timetable information systems and for fast approximative queries in time-dependent scenarios. By running experiments on several inputs other than road networks, we show that our approach is very robust to the input.
---
paper_title: Dijkstra's Algorithm On-Line: An Empirical Case Study from Public Railroad Transport

paper_content:

Traffic information systems are among the most prominent real-world applications of Dijkstra's algorithm for shortest paths. We consider the scenario of a central information server in the realm of public railroad transport on wide-area networks. Such a system has to process a large number of on-line queries in real time. In practice, this problem is usually solved by heuristical variations of Dijkstra's algorithm, which do not guarantee optimality. We report results from a pilot study, in which we focused on the travel time as the only optimization criterion. In this study, various optimality-preserving speed-up techniques for Dijkstra's algorithm were analyzed empirically. This analysis was based on the timetable data of all German trains and on a "snapshot" of half a million customer queries.1
---
paper_title: Partitioning graphs to speedup Dijkstra's algorithm

paper_content:

We study an acceleration method for point-to-point shortest-path computations in large and sparse directed graphs with given nonnegative arc weights. The acceleration method is called the arc-flag approach and is based on Dijkstra's algorithm. In the arc-flag approach, we allow a preprocessing of the network data to generate additional information, which is then used to speedup shortest-path queries. In the preprocessing phase, the graph is divided into regions and information is gathered on whether an arc is on a shortest path into a given region. The arc-flag method combined with an appropriate partitioning and a bidirected search achieves an average speedup factor of more than 500 compared to the standard algorithm of Dijkstra on large networks (1 million nodes, 2.5 million arcs). This combination narrows down the search space of Dijkstra's algorithm to almost the size of the corresponding shortest path for long-distance shortest-path queries. We conduct an experimental study that evaluates which partitionings are best suited for the arc-flag method. In particular, we examine partitioning algorithms from computational geometry and a multiway arc separator partitioning. The evaluation was done on German road networks. The impact of different partitions on the speedup of the shortest path algorithm are compared. Furthermore, we present an extension of the speedup technique to multiple levels of partitions. With this multilevel variant, the same speedup factors can be achieved with smaller space requirements. It can, therefore, be seen as a compression of the precomputed data that preserves the correctness of the computed shortest paths.
---
paper_title: Round-based public transit routing

paper_content:

We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for two criteria: arrival time and number of transfers. Existing algorithms consider this as a graph problem, and solve it using variants of Dijkstra's algorithm. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Moreover, it can be easily extended to handle flexible departure times or arbitrary additional criteria, such as fare zones. When run on London's complex public transportation network, RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications.
---
paper_title: Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm

paper_content:

In [1], basic speed-up techniques for Dijkstra's algorithm have been combined. The key observation in their work was that it is most promising to combine hierarchical and goal-directed speed-up techniques. However, since its publication, impressive progress has been made in the field of speed-up techniques for Dijkstra's algorithm and huge data sets have been made available. ::: ::: Hence, we revisit the systematic combination of speed-up techniques in this work, which leads to the fastest known algorithms for various scenarios. Even for road networks, which have been worked on heavily during the last years, we are able to present an improvement in performance. Moreover, we gain interesting insights into the behavior of speed-up techniques when combining them.
---
paper_title: Shortest-path queries in static networks

paper_content:

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.
---
paper_title: Fast and Exact Shortest Path Queries Using Highway Hierarchies

paper_content:

The computation of shortest paths in a graph is a well-known problem in graph theory. One of the most obvious practical applications is route planning in a road network, i.e., finding an optimal route from a start location to a target location. We assume that a given road network does not change very often and that there are many source-target queries on the same network. Therefore, it pays to invest some time for a preprocessing step that accelerates all further queries. We present a new speedup technique for route planning that exploits the hierarchy inherent in real-world road networks. In a preprocessing step, we investigate the given road network in order to extract and prepare a hierarchical representation. Our route planning algorithm then takes advantage of this data. It is an adaptation of the bidirectional version of DIJKSTRA’s algorithm, massively restricting its search space. In several experiments, we concentrate on the computation of fastest routes in Western Europe and the USA. Both networks consist of about 20 million nodes each. Our algorithm preprocesses these networks in a few hours using linear space. Queries then take around eight milliseconds to produce optimal routes. This is more than 2 000 times faster than using DIJKSTRA’s algorithm. There are numerous possibilities to further improve and extend our approach.
---
paper_title: Engineering highway hierarchies

paper_content:

Highway hierarchies exploit hierarchical properties inherent in real-world road networks to allow fast and exact point-to-point shortest-path queries. A fast preprocessing routine iteratively performs two steps: First, it removes edges that only appear on shortest paths close to source or target; second, it identifies low-degree nodes and bypasses them by introducing shortcut edges. The resulting hierarchy of highway networks is then used in a Dijkstra-like bidirectional query algorithm to considerably reduce the search space size without losing exactness. The crucial fact is that ‘far away’ from source and target it is sufficient to consider only high-level edges. Experiments with road networks for a continent show that using a preprocessing time of around 15 min, one can achieve a query time of around 1ms on a 2.0GHz AMD Opteron. Highway hierarchies can be combined with goal-directed search, they can be extended to answer many-to-many queries, and they can be used as a basis for other speed-up techniques (e.g., for transit-node routing and highway-node routing).
---
paper_title: Fast paths in large-scale dynamic road networks

paper_content:

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.
---
paper_title: Distributed time-dependent contraction hierarchies

paper_content:

Server based route planning in road networks is now powerful enough to find quickest paths in a matter of milliseconds, even if detailed information on time-dependent travel times is taken into account. However this requires huge amounts of memory on each query server and hours of preprocessing even for a medium sized country like Germany. This is a problem since global internet companies would like to work with transcontinental networks, detailed models of intersections, and regular re-preprocessing that takes the current traffic situation into account. By giving a distributed memory parallelization of the arguably best current technique – time-dependent contraction hierarchies, we remove these bottlenecks. For example, on a medium size network 64 processes accelerate preprocessing by a factor of 28 to 160 seconds, reduce per process memory consumption by a factor of 10.5 and increase query throughput by a factor of 25.
---
paper_title: Exact Routing in Large Road Networks Using Contraction Hierarchies

paper_content:

Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of road networks by adding shortcut edges. A subsequent modified bidirectional Dijkstra algorithm can then find a shortest path in a fraction of a millisecond, visiting only a few hundred nodes. This small search space makes it suitable to implement it on a mobile device. We present a mobile implementation that also handles changes in the road network, like traffic jams, and that allows instantaneous routing without noticeable delay for the user. Also, an algorithm to calculate large distance tables is currently the fastest if based on contraction hierarchies.
---
paper_title: Time-dependent contraction hierarchies and approximation

paper_content:

Time-dependent Contraction Hierarchies provide fast and exact route planning for time-dependent large scale road networks but need lots of space. We solve this problem by the careful use of approximations of piecewise linear functions. This way we need about an order of magnitude less space while preserving exactness and accepting only a little slow down. Moreover, we use these approximations to compute an exact travel time profile for an entire day very efficiently. In a German road network, e.g., we compute exact time-dependent routes in less than 2 ms. Exact travel time profiles need about 33 ms and about 3 ms suffice for an inexact travel time profile that is just 1 % away from the exact result. In particular, time-dependent routing and travel time profiles are now within easy reach of web servers with massive request traffic.
---
paper_title: Contraction hierarchies: faster and simpler hierarchical routing in road networks

paper_content:

We present a route planning technique solely based on the concept of node contraction. The nodes are first ordered by 'importance'. A hierarchy is then generated by iteratively contracting the least important node. Contracting a node υ means replacing shortest paths going through v by shortcuts. We obtain a hierarchical query algorithm using bidirectional shortest-path search. The forward search uses only edges leading to more important nodes and the backward search uses only edges coming from more important nodes. For fastest routes in road networks, the graph remains very sparse throughout the contraction process using rather simple heuristics for ordering the nodes. We have five times lower query times than the best previous hierarchical Dijkstra-based speedup techniques and a negative space overhead, i.e., the data structure for distance computation needs less space than the input graph. CHs can be combined with many other route planning techniques, leading to improved performance for many-to-many routing, transit-node routing, goal-directed routing or mobile and dynamic scenarios.
---
paper_title: Using Multi-level Graphs for Timetable Information in Railway Systems

paper_content:

In many fields of application, shortest path finding problems in very large graphs arise. Scenarios where large numbers of on-line queries for shortest paths have to be processed in real-time appear for example in traffic information systems. In such systems, the techniques considered to speed up the shortest path computation are usually based on precomputed information. One approach proposed often in this context is a space reduction, where precomputed shortest paths are replaced by single edges with weight equal to the length of the corresponding shortest path. In this paper, we give a first systematic experimental study of such a space reduction approach. We introduce the concept of multi-level graph decomposition. For one specific application scenario from the field of timetable information in public transport, we perform a detailed analysis and experimental evaluation of shortest path computations based on multi-level graph decomposition.
---
paper_title: Engineering multilevel overlay graphs for shortest-path queries

paper_content:

An overlay graph of a given graph G = (V, E) on a subset S ⊆ V is a graph with vertex set S and edges corresponding to shortest paths in G. In particular, we consider variations of the multilevel overlay graph used in Schulz et al. [2002] to speed up shortest-path computation. In this work, we follow up and present several vertex selection criteria, along with two general strategies of applying these criteria, to determine a subset S of a graph's vertices. The main contribution is a systematic experimental study where we investigate the impact of selection criteria and strategies on multilevel overlay graphs and the resulting speed-up achieved for shortest-path computation: Depending on selection strategy and graph type, a centrality index criterion, selection based on planar separators, and vertex degree turned out to perform best.
---
paper_title: The exact distance to destination in undirected world

paper_content:

Shortest distance queries are essential not only in graph analysis and graph mining tasks but also in database applications, when a large graph needs to be dealt with. Such shortest distance queries are frequently issued by end-users or requested as a subroutine in real applications. For intensive queries on large graphs, it is impractical to compute shortest distances on-line from scratch, and impractical to materialize all-pairs shortest distances. In the literature, 2-hop distance labeling is proposed to index the all-pairs shortest distances. It assigns distance labels to vertices in a large graph in a pre-computing step off-line and then answers shortest distance queries on-line by making use of such distance labels, which avoids exhaustively traversing the large graph when answering queries. However, the existing algorithms to generate 2-hop distance labels are not scalable to large graphs. Finding an optimal 2-hop distance labeling is NP-hard, and heuristic algorithms may generate large size distance labels while still needing to pre-compute all-pairs shortest paths. In this paper, we propose a multi-hop distance labeling approach, which generates a subset of the 2-hop distance labels as index off-line. We can compute the multi-hop distance labels efficiently by avoiding pre-computing all-pairs shortest paths. In addition, our multi-hop distance labeling is small in size to be stored. To answer a shortest distance query between two vertices, we first generate the query-specific small set of 2-hop distance labels for the two vertices based on our multi-hop distance labels stored and compute the shortest distance between the two vertices based on the 2-hop distance labels generated on-line. We conducted extensive performance studies on large real graphs and confirmed the efficiency of our multi-hop distance labeling scheme.
---
paper_title: Reachability and distance queries via 2-hop labels

paper_content:

Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. We propose a new data structure for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v.Our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. For shortest paths, such a cover is a collection S of shortest paths such that for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from S. We describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. Our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries.We study the proposed data structure using a combination of theoretical and experimental means. We implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. Our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.
---
paper_title: Approximate distance oracles

paper_content:

Let G=(V,E) be an undirected weighted graph with |V|=n and |E|=m . Let k\ge 1 be an integer. We show that G=(V,E) can be preprocessed in O(kmn^{1/k}) expected time, constructing a data structure of size O(kn^{1+1/k}) , such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k-1 , i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1 . We show that a 1963 girth conjecture of Erd{\H{o}}s, implies that &ohgr(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1 . The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name ``oracle''. Previously, data structures that used only O(n^{1+1/k}) space had a query time of &ohgr(n^{1/k}) and a slightly larger, non-optimal, stretch. Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.}
---
paper_title: Dynamic highway-node routing

paper_content:

We introduce a dynamic technique for fast route planning in large road networks. For the first time, it is possible to handle the practically relevant scenarios that arise in present-day navigation systems: When an edge weight changes (e.g., due to a traffic jam), we can update the preprocessed information in 2-40ms allowing subsequent fast queries in about one millisecond on average. When we want to perform only a single query, we can skip the comparatively expensive update step and directly perform a prudent query that automatically takes the changed situation into account. If the overall cost function changes (e.g., due to a different vehicle type), recomputing the preprocessed information takes typically less than two minutes. ::: ::: The foundation of our dynamic method is a new static approach that generalises and combines several previous speedup techniques. It has outstandingly low memory requirements of only a few bytes per node.
---
paper_title: Highway dimension, shortest paths, and provably efficient algorithms

paper_content:

Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the experimental evidence with the first rigorous proofs of efficiency for many of the heuristics suggested over the past decade. We introduce the notion of highway dimension and show how low highway dimension gives a unified explanation for several seemingly different algorithms.
---
paper_title: Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

paper_content:

We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of O(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of O(n5/2) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous O(mn) time when m = Ω(n3/2). Note that the additive error is unavoidable since, even in the static case, an O(n3-δ)-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with O(n5/2+O(1√(log n))) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of O(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.
---
paper_title: An On-Line Edge-Deletion Problem

paper_content:

There is given an undirected graph G -- (V, E) from which edges are deleted one at a time and about which questions of the type, "Are the vertices u and v in the same connected component?" have to be answered "on-line." There is presented an algorithm which maintains a data structure in which each question is answered in constant time and for which the total time involved in answering q questions and maintaining the data structure is O(q + I VI" lED.
---
paper_title: Planar graphs, negative weight edges, shortest paths, and near linear time

paper_content:

In this paper, we present an O(n log3 n) time algorithm for finding shortest paths in an n-node planar graph with real weights. This can be compared to the best previous strongly polynomial time algorithm developed by Lipton, Rose, and Tarjan in 1978 which runs in O(n3/2) time, and the best polynomial time algorithm developed by Henzinger, Klein, Subramanian, and Rao in 1994 which runs in O(n 4/3) time. We also present significantly improved data structures for reporting distances between pairs of nodes and algorithms for updating the data structures when edge weights change.
---
paper_title: A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths

paper_content:

We study dynamic (1 + e)-approximation algorithms for the single-source shortest paths problem in an unweighted undirected n-node m-edge graph under edge deletions. The fastest algorithm for this problem is an algorithm with O(n2+o(1)) total update time and constant query time by Bernstein and Roditty (SODA 2011). In this paper, we improve the total update time to O(n1.8+o(1) + m1+o(1)) while keeping the query time constant. This running time is essentially tight when m = Ω(n1.8) since we need Ω(m) time even in the static setting. For smaller values of m, the running time of our algorithm is subquadratic, and is the first that breaks through the quadratic time barrier. ::: ::: In obtaining this result, we develop a fast algorithm for what we call center cover data structure. We also make non-trivial extensions to our previous techniques called lazy-update and monotone Even-Shiloach trees (ICALP 2013 and FOCS 2013). As by-products of our new techniques, we obtain two new results for the decremental all-pairs shortest-paths problem. Our first result is the first approximation algorithm whose total update time is faster than O(mn) for all values of m. Our second result is a new trade-off between the total update time and the additive approximation guarantee.
---
paper_title: Improved dynamic algorithms for maintaining approximate shortest paths under deletions

paper_content:

We present the first dynamic shortest paths algorithms that make any progress beyond a long-standing O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas). • Given a source s, we present an algorithm that maintains (1 + e)-approximate shortest paths from s with an expected total update time of O(n2+O(1/√log n)) over all deletions (so the amortized time is about O(n2/m)). The worst-case query time is constant. The best previous result goes back three decades to Even and Shiloach [16] and Dinitz [12]. They show how to decrementally maintain an exact shortest path tree with a total update time of O(mn) (amortized update time O(n)). Roditty and Zwick [22] have shown that O(mn) is actually optimal for exact paths (barring a better combinatorial algorithm for boolean matrix multiplication), unless we are willing to settle for a Ω(n) query time. In fact, until now, even approximate dynamic algorithms were not able to go beyond O(mn). • For any fixed integer k ≥ 2, we present an algorithm that decrementally maintains a distance oracle (for all pairs shortest distances) with a total expected update time of O(n2+1/k+O(1/√log n)) (amortized update time about O(n2+1/k/m). The space requirement is only O(m + n1+1/k), the stretch of the returned distances is at most 2k − 1 + e, and the worst-case query time is O(1). The best previous result of Roditty and Zwick [21] had a total update time of O(mn) and a stretch of 2k − 1. Note that our algorithm implicitly solves the decremental all-pairs shortest path problem with the same bounds; the best previous approximation algorithm of Roditty and Zwick [21] returned (1 + e) approximate distances, but used O(n2) space, and required O(mn) total update time. As with the previous problem, our algorithm is the first to make progress beyond the O(mn) total update time barrier while maintaining a small query time. We present a general framework for accelerating decremental algorithms. In particular, our main idea is to run existing decremental algorithms on a sparse subgraph (such as a spanner or emulator) of the graph rather than on the original graph G. Although this is a common approach for static approximate shortest-path problems, it has never been used in a decremental setting because maintaining the subgraph H as edges are being deleted from G might require inserting edges into H, thus ruining the "decrementality" of the setting. We overcome this by presenting an emulator whose maintenance only requires a limited number of well-behaved insertions. In other words, we present a general technique for running decremental algorithms on a sparse subgraph of the graph. Once our framework is in place, applying it to any particular decremental algorithm only requires trivial modifications; most of the work consists of showing that these algorithms as they are still work in our restricted fully dynamic setting, where we encounter not just arbitrary deletions (as in the original setting), but also restricted insertions.
---
paper_title: On the monge property of matrices

paper_content:

Abstract A square matrix A = (aij) over a commutative linearly ordered group (G, ∗, ⩽) is said to have the Monge property if a ii ∗ a kj ⩽ a ij ∗ a ki holds for all i and for all j, k>i. We present an O(n4) algorithm for checking whether the rows and columns of a given matrix can be permuted in such a way that the obtained matrix has the Monge property.
---
paper_title: Finding Fastest Paths on A Road Network with Speed Patterns

paper_content:

This paper proposes and solves the Time-Interval All Fastest Path (allFP) query. Given a user-defined leaving or arrival time interval I, a source node s and an end node e, allFP asks for a set of all fastest paths from s to e, one for each sub-interval of I. Note that the query algorithm should find a partitioning of I into sub-intervals. Existing methods can only be used to solve a very special case of the problem, when the leaving time is a single time instant. A straightforward solution to the allFP query is to run existing methods many times, once for every time instant in I. This paper proposes a solution based on novel extensions to the A* algorithm. Instead of expanding the network many times, we expand once. The travel time on a path is kept as a function of leaving time. Methods to combine travel-time functions are provided to expand a path. A novel lower-bound estimator for travel time is proposed. Performance results reveal that our method is more efficient and more accurate than the discrete-time approach.
---
paper_title: Spatio-temporal network databases and routing algorithms: a summary of results

paper_content:

Spatio-temporal networks are spatial networks whose topology and parameters change with time. These networks are important due to many critical applications such as emergency traffic planning and route finding services and there is an immediate need for models that support the design of efficient algorithms for computing the frequent queries on such networks. This problem is challenging due to potentially conflicting requirements of model simplicity and support for efficient algorithms. Time expanded networks which have been used to model dynamic networks employ replication of the network across time instants, resulting in high storage overhead and algorithms that are computationally expensive. In contrast, proposed time-aggregated graphs do not replicate nodes and edges across time; rather they allow the properties of edges and nodes to be modeled as a time series. Since the model does not replicate the entire graph for every instant of time, it uses less memory and the algorithms for common operations (e.g. connectivity, shortest path) are computationally more efficient than those for time expanded networks. One important query on spatio-temporal networks is the computation of shortest paths. Shortest paths can be computed either for a given start time or to find the start time and the path that leads to least travel time journeys (best start time journeys). Developing efficient algorithms for computing shortest paths in a time varying spatial network is challenging because these journeys do not always display greedy property or optimal substructure, making techniques like dynamic programming inapplicable. In this paper, we propose algorithms for shortest path computations in both contexts. We present the analytical cost models for the algorithms and provide an experimental comparison of performance with existing algorithms.
---
paper_title: Finding time-dependent shortest paths over large graphs

paper_content:

The spatial and temporal databases have been studied widely and intensively over years. In this paper, we study how to answer queries of finding the best departure time that minimizes the total travel time from a place to another, over a road network, where the traffic conditions dynamically change from time to time. We study a generalized form of this problem, called the time-dependent shortest-path problem. A time-dependent graph GT is a graph that has an edge-delay function, wi, j(t), associated with each edge (vi, vj), to be stored in a database. The edge-delay function wi, j(t) specifies how much time it takes to travel from node vi to node vj, if it departs from vi at time t. A user-specified query is to ask the minimum-travel-time path, from a source node, vs, to a destination node, ve, over the time-dependent graph, GT, with the best departure time to be selected from a time interval T. We denote this user query as LTT(vs, ve, T) over GT. The challenge of this problem is the added complexity due to the time dependency in the time-dependent graph. That is, edge delays are not constants, and can vary from time to time. In this paper, we propose a novel algorithm to find the minimum-travel-time path with the best departure time for a LTT(vs, ve, T) query over a large graph GT. Our approach outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice. We will discuss the design of our algorithm, together with its correctness and complexity. We conducted extensive experimental studies over large graphs and will report our findings.
---
paper_title: On the Complexity of Time-Dependent Shortest Paths

paper_content:

We investigate the complexity of shortest paths in time-dependent graphs, in which the costs of edges vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. Our main result is that when the edge cost functions are (polynomial-size) piecewise linear, the shortest path from s to d can change nθ(log n) times, settling a several-year-old conjecture of Dean [Technical Reports, 1999, 2004]. We also show that the complexity is polynomial if the slopes of the linear function come from a restricted class, present an output-sensitive algorithm for the general case, and describe a scheme for a (1 + e)-approximation of the travel time function in near-quadratic space. Finally, despite the fact that the arrival time function may have superpolynomial complexity, we show that a minimum delay path for any departure time interval can be computed in polynomial time.
---
paper_title: Least expected time paths in stochastic, time-varying transportation networks

paper_content:

The authors consider stochastic, time-varying transportation networks, where the arc weights (arc travel times) are random variables with probability distribution functions that vary with time. Efficient procedures are widely available for determining least time paths in deterministic networks. In stochastic but time-invariant networks, least expected time paths can be determined by setting each random arc weight to its expected value and solving an equivalent deterministic problem. This paper addresses the problem of determining least expected time paths in stochastic, time-varying networks. Two procedures are presented. The first procedure determines the a priori least expected time paths from all origins to a single destination for each departure time in the peak period. The second procedure determines lower bounds on the expected times of these a priori least expected time paths. This procedure determines an exact solution for the problem where the driver is permitted to react to revealed travel times on traveled links en route, i.e. in a time-adaptive route choice framework. Modifications to each of these procedures for determining least expected cost (where cost is not necessarily travel time) paths and lower bounds on the expected costs of these paths are given. Extensive numerical tests are conducted to illustrate the algorithms` computational performance as well as the properties of the solution.
---
paper_title: Optimal paths in graphs with stochastic or multidimensional weights

paper_content:

This paper explores computationally tractable formulations of stochastic and multidimensional optimal path problems, each as an extension of the shortest path problem. A single formulation encompassing both problems is considered, in which a utility function defines preference among candidate paths. The result is the ability to state explicit conditions for exact solutions using standard methods, and the applicability of well-understood approximation techniques.
---
paper_title: A Lower Bound for the Shortest Path Problem

paper_content:

We show that the shortest path problem cannot be solved in o(log n) time on an unbounded fan-in PRAM without bit operations using poly(n) processors even when the bit-lengths of the weights on the edges are restricted to be of size O(log/sup 3/ n). This shows that the matrix-based repeated squaring algorithm for the shortest path problem is optimal in the unbounded fan-in PRAM model without bit operations.
---
paper_title: Maximum flows and parametric shortest paths in planar graphs

paper_content:

We observe that the classical maximum flow problem in any directed planar graph G can be reformulated as a parametric shortest path problem in the oriented dual graph G*. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in O(n log n) time. As we continuously increase the parameter, each change in the shortest path tree can be effected in O(log n) time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change Ω(n2) times in the worst case, suggesting that a different method may be required to efficiently compute maximum flows in higher-genus graphs.
---
paper_title: Faster Parametric Shortest Path and Minimum Balance Algorithms

paper_content:

We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum-balance algorithm to obtain a faster minimum-balance algorithm. ::: ::: ::: ::: For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum-balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum-balance algorithm of Schneider and Schneider. ::: ::: ::: ::: An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).
---
paper_title: Vickrey prices and shortest paths: what is an edge worth?

paper_content:

We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auction-based pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path, i.e., the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by N. Nisan and A. Ronen (1999).
---
paper_title: A near-linear-time algorithm for computing replacement paths in planar directed graphs

paper_content:

Let G = (V(G), E(G)) be a weighted directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for every edge e in P, the length of a shortest path from s to t that avoids e. The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in P is removed from the graph in its turn and the distance from s to t in the modified graph is computed. The running time of this algorithm is O (mn + n2 log n), where n = |V(G)| and m = |E(G)|. The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [21, 13] repeatedly computes the replacement paths from s to t. Its running time is O(kn(m + n log n)). Second, the computation of Vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [16] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph. In this paper we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. In particular, the algorithm computes the lengths of the replacement paths in O(n log3 n) time. This result immediately improves the running time of the two applications mentioned above by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [12] that supports multi-source shortest paths queries in planar directed graphs in logarithmic time. Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time O(h), where h is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges.
---
paper_title: A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs

paper_content:

Let G = (V, E) be a directed graph with positive edge weights, let s, t be two specified vertices in this graph, and let π(s, t) be the shortest path between them. In the replacement paths problem we want to compute, for every edge e on π(s, t), the shortest path from s to t that avoids e. The naive solution to this problem would be to remove each edge e, one at a time, and compute the shortest s - t path each time; this yields a running time of O(mn + n2 log n). Gotthilf and Lewenstein [8] recently improved this to O(mn+n2 log log n), but no o(mn) algorithms are known. We present the first approximation algorithm for replacement paths in directed graphs with positive edge weights. Given any e e [0, 1), our algorithm returns (1 + e)-approximate replacement paths in O(e-1 log2 n log(nC/c)(m+n log n)) = O(m log(nC/c)/e) time, where C is the largest edge weight in the graph and c is the smallest weight. We also present an even faster (1 + e) approximate algorithm for the simpler problem of approximating the k shortest simple s - t paths in a directed graph with positive edge weights. That is, our algorithm outputs k different simple s - t paths, where the kth path we output is a (1 + e) approximation to the actual kth shortest simple s - t path. The running time of our algorithm is O(ke-1 log2 n(m + n log n)) = O(km/e). The fastest exact algorithm for this problem has a running time of O(k(mn+n2 log log n)) = O(kmn) [8]. The previous best approximation algorithm was developed by Roditty [15]; it has a stretch of 3/2 and a running time of O(km√n) (it does not work for replacement paths). Note that all of our running times are nearly optimal except for the O (log(nC/c)) factor in the replacements paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges.
---
paper_title: Finding Alternative Shortest Paths in Spatial Networks

paper_content:

Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a single shortest path. For example, one of the common ways to determine the importance (or price) of a vertex or an edge in spatial network is to use Vickrey pricing, which intuitively values the vertex v (or edge e) based on how much harder for travelling from the sources to the destinations without using v (or e). In such cases, the alternative shortest paths without using v (or e) are required. In this article, we propose using a precomputation based approach for both single pair alternative shortest path and all pairs shortest paths processing. To compute the alternative shortest path between a source and a destination efficiently, a naiive way is to precompute and store all alternative shortest paths between every pair of vertices avoiding every possible vertex (or edge), which requires O(n4) space. Currently, the state of the art approach for reducing the storage cost is to choose a subset of the vertices as center points, and only store the single-source alternative shortest paths from those center points. Such approach has the space complexity of O(n2 log n). We propose a storage scheme termed iSPQF, which utilizes shortest path quadtrees by observing the relationships between each avoiding vertex and its corresponding alternative shortest paths. We have reduced the space complexity from the naiive O(n4) (or the state of the art O(n4 log n)) to O(min(γ, L)n1.5) with comparable query performance of O(K), where K is the number of vertices in the returned paths, L is the diameter of the spatial network, and γ is a value that depends on the structure of the spatial network, which is empirically estimated to be 40 for real road networks. Experiments on real road networks have shown that the space cost of the proposed iSPQF is scalable, and both the algorithms based on iSPQF are efficient.
---
paper_title: Efficient query processing on spatial networks

paper_content:

A framework for determining the shortest path and the distance between every pair of vertices on a spatial network is presented. The framework, termed SILC, uses path coherence between the shortest path and the spatial positions of vertices on the spatial network, thereby, resulting in an encoding that is compact in representation and fast in path and distance retrievals. Using this framework, a wide variety of spatial queries such as incremental nearest neighbor searches and spatial distance joins can be shown to work on datasets of locations residing on a spatial network of sufficiently large size. The suggested framework is suitable for both main memory and disk-resident datasets.
---
paper_title: The weighted region problem: finding shortest paths through a weighted planar subdivision

paper_content:

The problem of determining shortest paths through a weighted planar polygonal subdivision with <italic>n</italic> vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a given source point is presented. The output is a partitioning of each edge of the subdivion into intervals of ε-optimality, allowing an ε-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time <italic>O</italic>(<italic>ES</italic>) and requires <italic>O</italic>(<italic>E</italic>) space, where <italic>E</italic> is the number of “events” in our algorithm and <italic>S</italic> is the time it takes to run a numerical search procedure. In the worst case, <italic>E</italic> is bounded above by <italic>O</italic>(<italic>n</italic><supscrpt>4</supscrpt>) (and we give an &OHgr;(<italic>n</><supscrpt>4</supscrpt>) lower bound), but it is likeky that <italic>E</italic> will be much smaller in practice. We also show that <italic>S</italic> is bounded by <italic>O</italic>(<italic>n</italic><supscrpt>4</supscrpt><italic>L</italic>), where <italic>L</italic> is the precision of the problem instance (including the number of bits in the user-specified tolerance ε). Again, the value of <italic>S</italic> should be smaller in practice. The algorithm applies the “continuous Dijkstra” paradigm and exploits the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimaly property of shortest paths that is well known from the analogous optics model. The algorithm generalizes to the multi-source case to compute Voronoi diagrams.
---

Title: A Survey of Shortest-Path Algorithms

Section 1: Introduction
Description 1: This section introduces the shortest-path problem, explains its significance, and discusses the various types of graphs and problem settings involved.

Section 2: Taxonomy
Description 2: This section presents a classification of shortest-path algorithms based on a proposed taxonomy, breaking them down into high-level branches.

Section 3: Related Work
Description 3: This section reviews existing surveys and notable research that address various categories of shortest-path algorithms, including challenges and advancements.

Section 4: Problem Definition
Description 4: This section defines the shortest-path problem, including the input graph and the specific objectives, as well as complexity considerations.

Section 5: Static Shortest-Path Algorithms
Description 5: This section reviews algorithms for single-source and all-pairs shortest-path problems in static graphs, highlighting classical and advanced techniques.

Section 6: Single-Source Shortest-Path (SSSP)
Description 6: This subsection provides details on algorithms that compute shortest paths from a single-source vertex to all other vertices in a graph.

Section 7: All-Pairs Shortest-Path (APSP)
Description 7: This subsection provides details on algorithms that compute shortest paths between all pairs of vertices in a graph.

Section 8: Distance Oracles
Description 8: This section discusses algorithms that preprocess graphs to create data structures or indexes to quickly answer distance queries.

Section 9: Goal-Directed Shortest-Paths
Description 9: This section explains algorithms that use additional information to prune the search space and direct the shortest-path search more effectively.

Section 10: Hierarchical Shortest-Path
Description 10: This section discusses algorithms that use multi-layered hierarchical structures to improve shortest-path computation efficiency.

Section 11: Dynamic Shortest-Path Algorithms
Description 11: This section covers algorithms that handle updates and queries in graphs that change over time.

Section 12: Time-Dependent Shortest-Path Algorithms
Description 12: This section focuses on algorithms designed for graphs with edges whose weights are functions of time.

Section 13: Stochastic Shortest-Path Algorithms
Description 13: This section discusses algorithms that consider uncertainty in edge weights by modeling them as random variables.

Section 14: Parametric Shortest-Path Algorithms
Description 14: This section covers algorithms that compute shortest-paths based on a specific parameter and identify breakpoints where paths tend to change.

Section 15: Replacement Shortest-Path Algorithms
Description 15: This section reviews algorithms that compute shortest-paths while avoiding specific edges or vertices on the shortest path.

Section 16: Alternative Shortest-Path Algorithms
Description 16: This section covers algorithms that find alternative paths avoiding given vertices or edges, reusing previously computed results.

Section 17: Weighted Region Shortest-Path Algorithms
Description 17: This section discusses algorithms that compute shortest paths in planes divided into weighted polygonal regions.

Section 18: Conclusion
Description 18: This section summarizes the paper, restates the importance of the taxonomy, and discusses the key findings and future directions.