Tytuł artykułu
Treść / Zawartość
Pełne teksty:
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
In this paper, we present a case study, showing step by step, how to speed up Dijkstra’s method by parallelizing its computation and using different data structures. We compare basic algorithm with its bidirectional version and investigate two-and-multi-thread implementations based on Fibonacci heaps and regular priority queues. Experimental results obtained for artificially generated graphs as well as real-world road network data are presented and described.
Czasopismo
Rocznik
Tom
Strony
3--7
Opis fizyczny
Bibliogr. 9 poz.
Twórcy
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Control Systems and Mechatronics, ul. Janiczewskiego 11/17, 50-372 Wrocław, Poland
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland
autor
- Wrocław University of Technology, Faculty of Electronics, Department of Computer Engineering, Janiszewskiego 11/17, 50-372 Wrocław, Poland
Bibliografia
- [1] BAST, H., et al.: Route Planning in Transportation Networks, Technical Report of Microsoft Research, January 2014.
- [2] CRAUSER, A., et al.: A Parallelization of Dijkstra’s Shortest Path Algorithm, in MFCS’98, LNCS 1450, pp. 722-731, Springer-Verlag 1998.
- [3] DELLING, D., WAGNER, D.: Time-dependent route planning, in Robust and Online Large-Scale Optimization, LNCS 5868, pp. 207–230, Springer 2009.
- [4] DELLING D., et al.: Engineering Route Planning Algorithms in: Algorithmics, LNCS 5515, pp. 117–139, Springer-Verlag 2009.
- [5] DUDEK, R.: Analysis and evaluation of a set of shortest paths of passing on traffic control system, Thesis, Wroclaw University of Technology 2014.
- [6] JASIKA, N., et al.: Dijkstra’s shortest path algorithm serial and parallel execution performance analysis, MIPRO 2012, May 21-25, Croatia 2012.
- [7] KARLSSON, B.: Beyond the C++ Standard Library: An Introduction to Boost, Addison-Wesley 2006.
- [8] LEDA Homepage: http://www.algorithmic-solutions.com/leda/index.htm, [date of access: 05.01.2016].
- [9] Open Street Map Homepage: https://www.openstreetmap.org, [date of access: 05.01.2016].
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-43442b5e-ab72-401b-85b3-baabba19a5ad