ACM Journal of Experimental Algorithmics · 2005 · 88 citations · 30 references
ComputingComputer ScienceAlgorithmsData StructuresTransportation EngineeringGeometric Data StructuresGraph AlgorithmsGraph Layout AlgorithmsRouting AlgorithmsShortest Path AlgorithmsTransportation NetworksContainersDynamic Shortest PathsGeometric RoutingPath ComputationRoad Traffic NetworksShortest Path ProblemsShortest Paths
A fundamental approach in finding efficiently best routes or optimal itineraries in traffic information systems is to reduce the search space (part of graph visited) of the most commonly used shortest path routine (Dijkstra's algorithm) on a suitably defined graph. We investigate reduction of the search space while simultaneously retaining data structures, created during a preprocessing phase, of size linear (i.e., optimal) to the size of the graph. We show that the search space of Dijkstra's algorithm can be significantly reduced by extracting geometric information from a given layout of the graph and by encapsulating precomputed shortest-path information in resulted geometric objects (containers). We present an extensive experimental study comparing the impact of different types of geometric containers using test data from real-world traffic networks. We also present new algorithms as well as an empirical study for the dynamic case of this problem, where edge weights are subject to change and the geometric containers have to be updated and show that our new methods are two to three times faster than recomputing everything from scratch. Finally, in an appendix, we discuss the software framework that we developed to realize the implementations of all of our variants of Dijkstra's algorithm. Such a framework is not trivial to achieve as our goal was to maintain a common code base that is, at the same time, small, efficient, and flexible, as we wanted to enhance and combine several variants in any possible way.
30
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Efficient Algorithms for Shortest Paths in Sparse Networks
D. Barton Johnson · Journal of the ACM · 1977 · 1K citations · Full text
Gilad Bracha, William R. Cook · 1990 · 811 citations
Engineering, Systems Engineering, Knowledge Representation +13
Solving geometric problems with the rotating calipers
Godfried T. Toussaint · 1983 · 508 citations