Rolf H. Möhring
Abstract
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.
- Agrawal, R. and Jagadish, H. V. 1994. Algorithms for searching massive graphs. IEEE Transactions on Knowledge and Data Engeneering 6, 2, 225--238. Google Scholar
- Battista, G. D. and Zwick, U., Eds. 2003. Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science, vol. 2832. Springer, New York.Google Scholar
- Car, A. and Frank, A. U. 1994. Modelling a hierarchy of space applied to large road networks. In IGIS '94: Geographic Information Systems, International Workshop on Advanced Information Systems, J, Nievergelt, T. Roos, H.-J. Schek, and P. Widmayer, Eds. Lecture Notes in Computer Science, vol. 884. Springer, Heidelberg, 15--24. Google Scholar
- Chou, Y.-L., Romeijn, H. E., and Smith, R. L. 1998. Approximating shortest paths in large-scale networks with an application to intelligent transportation systems. INFORMS Journal on Computing 10, 2, 163--179. Google Scholar
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms. The MIT Press, Cambridge, MA. Google Scholar
- Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. In Numerische Mathematik. Vol. 1. Mathematisch Centrum, Amsterdam, The Netherlands, 269--271.Google Scholar
- Frederikson, G. N. 1987. Fast algorithms for shortest paths in planar graphs with applications. SIAM Journal on Computing 16, 6, 1004--1022. Google Scholar
- Fredman, M. L. and Tarjan, R. E. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the Association for Computing Machinery 34, 3, 596--615. Google Scholar
- Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, A. Buchsbaum, Ed. SIAM, Philadelphia, PA, USA, 156--165. Google Scholar
- Gutman, R. J. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, L. Arge, G. F. Italiano, and R. Sedgewick, Eds. SIAM, Philadelphia, PA, USA, 100--111.Google Scholar
- Holzer, M. 2003. Hierarchical speedup techniques for shortest path algorithms. Tech. rep., Dept. of Informatics, University of Konstanz, Germany.Google Scholar
- Holzer, M., Schulz, F., and Willhalm, T. 2004. Combining speedup techniques for shortest-path computations. In Experimental and Efficient Algorithms, Third International Workshop, C. C. Ribeiro and S. L. Martins, Eds. Lecture Notes in Computer Science, vol. 3059. Springer, Heidelberg, 269--284.)Google Scholar
- Johnson, D. B. 1977. Efficient algorithms for shortest paths in sparse networks. Journal of the Association for Computing Machinery 24, 1, 1--13. Google Scholar
- Jung, S. and Pramanik, S. 1996. Hiti graph model of topographical roadmaps in navigation systems. In Proceedings of the Twelfth International Conference on Data Engineering, S. Y. W. Su, Ed. IEEE Computer Society, Tokyo, 76--84. Google Scholar
- Karypis, G. 1995. METIS: Family of multilevel partitioning algorithms. http://www-users.cs.umn.edu/~karypis/metis/.Google Scholar
- Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 1 (Aug.), 359--392. Google Scholar
- Köhler, E., Möhring, R. H., and Schilling, H. 2005. Acceleration of shortest path and constrained shortest path computation. In Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, S. E. Nikoletseas, Ed. Lecture Notes in Computer Science, vol. 3503. Springer, Heidelberg, 126--138. Google Scholar
- Kranakis, E., Krizanc, D., and Urrutia, J. 1995. Implicit routing and shortest path information (extended abstract). In SIROCCO, L. M. Kirousis and C. Kaklamanis, Eds. Proceedings in Informatics, vol. 2. Carleton Scientific, 101--112.Google Scholar
- Lauther, U. 1997. Slow preprocessing of graphs for extremely fast shortest path calculations. Lecture at the Workshop on Computational Integer Programming at ZIB.Google Scholar
- Lauther, U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität---von der Forschung zur praktischen Anwendung, M. Raubal, A. Sliwinski, and W. Kuhn, Eds. IfGI prints, vol. 22. Institut für Geoinformatik, Westfälische Wilhelms-Universität, Münster, 219--230.Google Scholar
- Mehlhorn, K. and Näher, S. 1999. LEDA, A platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge. Google Scholar
- Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Algorithms---ESA 2005, 13th Annual European Symposium, G. S. Brodal and S. Leonardi, Eds. Lecture Notes in Computer Science, vol. 3669. Springer, 568--579. Google Scholar
- Schulz, F. 2005. Timetable information and shortest paths. Ph.D. thesis, Faculty of Informatics, University of Karlsruhe.Google Scholar
- Schulz, F., Wagner, D., and Weihe, K. 2000. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. ACM Journal of Experimental Algorithms 5, 12. Google Scholar
- Wagner, D. and Willhalm, T. 2003. Geometric speedup techniques for finding shortest paths in large sparse graphs. (See Battista and Zwick {2003}, 776--787.)Google Scholar
- Wagner, D. and Willhalm, T. 2005. Drawing graphs to speed up shortest-path computations. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, C. Demetrescu, R. Sedgewick, and R. Tamassia, Eds. SIAM, Philadelphia, PA, USA, 17--25.Google Scholar
- Wagner, D., Willhalm, T., and Zaroliagis, C. 2005. Geometric containers for efficient shortest path computation. ACM Journal of Experimental Algorithms 10. Google Scholar
- Willhalm, T. 2005. Engineering shortest paths and layout algorithms for large graphs. Ph.D. thesis, Faculty of Informatics, University of Karlsruhe.Google Scholar
Index Terms
- Partitioning graphs to speedup Dijkstra's algorithm
Recommendations
A Shortest Path Algorithm for Real-Weighted Undirected Graphs
We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm creates a linear-size structure that facilitates single-source ...
Approximating Shortest Path in Large-Scale Road Networks with Turn Prohibitions Using Multi-constrained Path Algorithm
CIMSIM '13: Proceedings of the 2013 Fifth International Conference on Computational Intelligence, Modelling and SimulationMulti-Constrained Path (MCP) algorithms are path finding algorithms, unlike conventional routing algorithms, they not only give a path between source and destination, also verifies whether the path satisfies the given constraints (Right turn, Left turn ...
Dijkstra's algorithm to find the nearest vaccine location
AbstractSince the start of Covid-19 pandemic has made many people look for vaccine locations. In general, Dijkstra algorithm is used to find the shortest path. The shortest path problem concentrates on finding the path with the minimum distance. The ...
Reviews
Richard Y. Sun
Finding a shortest path between two nodes in a graph is a very common optimization problem in many practical applications. A shortest path usually directly reflects the cheapest cost and the minimum delay from one node to another. Dijkstra’s shortest path algorithm is the well-known algorithm that solves this problem in polynomial time. However, the time complexity of this algorithm is not low enough for applications where a large and sparse graph with, say, one million nodes is used. There have been many efforts to accelerate Dijkstra’s algorithm, enabling the applicability of this algorithm to those gigantic problem instances. Results with substantial speedup factors have also been reported compared to Dijkstra’s original algorithm. This paper examines a specific acceleration method called the arc-flag approach. The idea of this approach is to use preprocessing to prepare important information, which is used to prune an unnecessary path search. During the preprocessing, the graph is divided into regions and information is gathered on whether an arc is on a shortest path into a given region. Using this arc-flag information, combined with bidirected search and an appropriate graph partitioning, a speedup factor of more than 500 is achieved, compared to Dijkstra’s original algorithm. The main contribution of this paper is the study of the impact of different graph partitioning methods on the speedup factor. The authors conducted experiments to evaluate which partitions are best suited for the arc-flag method. Their results show the best speedup results are achieved by the arc-flag method combined with a bidirected search, accelerated in both directions with kd-tree or METIS partitions. The second contribution is the authors’ idea of using multiple levels of partitions in this arc-flag acceleration method. This can be seen as a compression of the pre-computer arc-flag data. It gives the benefit of a reduced space requirement to store arc-flags while achieving the same speedup factor. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments