Mario Miler
Faculty of geodesy, University of Zagreb
Damir Medak
Faculty of geodesy, University of Zagreb
Dražen Odobašić
Faculty of geodesy, University of Zagreb
In the field of geoinformation and transportation science, the shortest path is calculated on graph data mostly found in road and transportation networks. This data is often stored in various database systems. Many applications dealing with transportation network require calculation of the shortest path. The objective of this research is to compare the performance of Dijkstra shortest path calculation in PostgreSQL (with pgRouting) and Neo4j graph database for the purpose of determining if there is any difference regarding the speed of the calculation. Benchmarking was done on commodity hardware using OpenStreetMap road network. The first assumption is that Neo4j graph database would be well suited for the shortest path calculation on transportation networks but this does not come without some cost. Memory proved to be an issue in Neo4j setup when dealing with larger transportation networks.
Dreyfus SE. An Appraisal of Some Shortest-Path Algorithms. Operations Research. 1969 May 1;17(3):395–412.
Golden BL. Shortest Path Algorithms: A Comparison. Massachusetts Institute of Technology, Operations Research Center; 1975.
Cherkassky B V., Goldberg A V., Radzik T. Shortest paths algorithms: theory and experimental evaluation. 1994 Jan 23;516–25.
Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, Third Edition. BOOK. The MIT Press; 2009. p. 1312.
Zlatanova S, Baharin SSK. Optimal Navigation of First Responders Using DBMS. 3rd International Conference on Information Systems for Crisis Response and Management 4th International Symposium on GeoInformation for Disaster Management. 2008;541–54 606.
Tuot C, Obradovic D, Fichter F, Dengel A. CRUV - A Collaborative Route-Planning System for Utility Vehicles. 2010;
Innerebner M, Böhlen M, Gamper J. ISOGA: a system for geographical reachability analysis. Liang SHL, Wang X, Claramunt C, editors. B
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Marko Matulin, PhD, Dario Babić, PhD, Marko Ševrović, PhD
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
