Header menu link for other important links
X
Comparative analysis of parallelised shortest path algorithms using Open MP
Uditi,
Published in IEEE
2017
Pages: 369 - 377
Abstract
This paper presents parallel implementations and includes performance analysis of three prominent graph algorithms (i.e., Bellman Ford, Floyd-Warshall and Dijkstra) used for finding the all-pairs of shortest paths. The algorithm implementations were parallelized using Open MP (Open Multi-Processing). Their performances were measured on 4 different configurations i.e. dual core i3, quad core i5, quad core i7 and 8 core processors. This paper also presents a comparative study of serial and parallel implementations of these algorithms keeping execution time and number of graph nodes as the parameter. Finally, the results show that, execution time can be reduced using parallel implementation for larger number of graph nodes. Also, the conclusions are drawn for the best algorithm to be used which works for all the graph nodes with less execution time. © 2017 IEEE.
About the journal
JournalData powered by Typeset2017 Third International Conference on Sensing, Signal Processing and Security (ICSSS)
PublisherData powered by TypesetIEEE
Open AccessNo