We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in @math time on connected geometric graphs having @math vertices and @math pairwise crossings, where @math is smaller than @math by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having @math segments and @math crossings in linear time, for the case when @math is sublinear in @math by an iterated logarithmic factor.
We propose shortest path algorithms that use A* search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. Our algorithms compute optimal shortest paths and work on any directed graph. We give experimental results showing that the most efficient of our new algorithms outperforms previous algorithms, in particular A* search with Euclidean bounds, by a wide margin on road networks and on some synthetic problem families.  The computation of shortest paths between different locations on a road network appears to be a key problem in many applications. Often, a shortest path is required in a very short time. In this article, we try to find an answer to the question of which shortest path algorithm for the one-to-one shortest path problem runs fastest on a large real-road network. An extensive computational study is presented, in which six existing algorithms and a new label correcting algorithm are implemented in several variants and compared on the real-road network of The Netherlands. In total, 168 versions are implemented, of which 18 versions are variants of the new algorithm and 60 versions are new by the application of bidirectional search. In the first part of the article we present a mathematical framework and a review of existing algorithms. We then describe combinations of existing algorithms with bidirectional search and heuristic-estimate techniques based on Euclidean distance and landmarks. We also present some useful static reduction techniques. In the final part of the article we present results from computational tests on The Netherlands road network. The new algorithm, which combines concepts from previous work on buckets and label-correcting techniques, has generally the shortest running times of any of the tested algorithms. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 182–194 2006This research is part of a Ph.D. project of the second author and a Master's project of the first author, at Delft University of Technology, Department of Electrical Engineering, Mathematics and Computer Science. We present a new speedup technique for route planning that exploits the hierarchy inherent in real world road networks. Our algorithm preprocesses the eight digit number of nodes needed for maps of the USA or Western Europe in a few hours using linear space. Shortest (i.e. fastest) path queries then take around eight milliseconds to produce exact shortest paths. This is about 2 000 times faster than using Dijkstra’s algorithm. 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. The classic problem of finding the shortest path over a network has been the target of many research efforts over the years. These research efforts have resulted in a number of different algorithms and a considerable amount of empirical findings with respect to performance. Unfortunately, prior research does not provide a clear direction for choosing an algorithm when one faces the problem of computing shortest paths on real road networks. Most of the computational testing on shortest path algorithms has been based on randomly generated networks, which may not have the characteristics of real road networks. In this paper, we provide an objective evaluation of 15 shortest path algorithms using a variety of real road networks. Based on the evaluation, a set of recommended algorithms for computing shortest paths on real road networks is identified. This evaluation should be particularly useful to researchers and practitioners in operations research, management science, transportation, and Geographic Information Systems.