Parallel algorithms for shortest path problem on time dependent graphs

Abstract

Shortest path problem in time dependent graphs has become a popular problem in recent years. Ever since the smart phones became an inseparable part of our lives, the applications on those devices started to provide many functionalities which make human life much easier. Navigation applications are one of them. State of the art navigation applications bene t from real time tra c data besides the map data. Therefore, it becomes a necessity to solve the problem of shortest path with real time data, i.e., on time dependent graphs. Various sequential algorithms for the shortest path problem in time dependent graphs are appearing in the literature. However, these algorithms mostly su er from the following two problems: long running times or huge memory requirements. These problems of the previously proposed algorithms are making them unsuitable for navigation applications which run on real time data and which need fast response times. In order to speed-up the running time of the sequential algorithm, without requiring much more memory, for shortest path problem with time dependent ow speed model, we propose parallel algorithms based on Modi ed Dijkstra algorithm. We develop three di erent parallel implementations by using Cuda and OpenMP: These are (i) a Cuda based version, (ii) an OpenMP based version and (iii) a hybrid Cuda and OpenMP based version. We get up to 10-fold speedup in the OpenMP version, and 17-fold speed up in the other two versions.