A Fast and Reliable Dijkstra Algorithm for Online Shortest Path

International Journal of Computer Science and Engineering

© 2018 by SSRG - IJCSE Journal

Volume 5 Issue 12

Year of Publication : 2018

Authors : Mazhar Iqbal, Kun Zhang, Sami Iqbal, Irfan Tariq

10.14445/23488387/IJCSE-V5I12P106

How to Cite?

Mazhar Iqbal, Kun Zhang, Sami Iqbal, Irfan Tariq, "A Fast and Reliable Dijkstra Algorithm for Online Shortest Path," SSRG International Journal of Computer Science and Engineering , vol. 5,  no. 12, pp. 24-27, 2018. Crossref, https://doi.org/10.14445/23488387/IJCSE-V5I12P106

Abstract:

The shortest path problem exists in a variety of areas. A well-known shortest path algorithm is Dijkstra's algorithm. In this paper, the concepts of network analysis with traffic issues are recognized. The condition of traffic in a city changes sometimes and there are usually large amounts of requests happen, it needs to be solved rapidly. The algorithm is developed by considering the various problems present in the existing modified Dijkstra’s shortest path algorithms. In this MDSP algorithm, instead of a single parameter, multiple parameters were included to find the valid shortest path for road networks. The proposed algorithm is compared with the different existing algorithm which shows that proposed algorithm has better accuracy.

Keywords:

Dijkstra’s Algorithm, Shortest path, Alternative path, Traffic condition.

References:

[1] Brunel, E., Delling, D., Gemsa, A., and Wagner, D., “Space-efficient SHARC-routing”, 9th International Symposium on Experimental Algorithms (SEA). 2012, 47-5858. 
[2] Bauer, R. and Delling, D. 2009., “SHARC: Fast and robust unidirectional routing”, ACM Journal of Experimental Algorithmics 14. Announced at ALENEX 2008. 
[3] Bauer, R., Delling, D., Sanders, P., Schieferdecker, D., Schultes, D., and Wagner, D.,” Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm”, ACM Journal of Experimental Algorithmics, 2010, pp 34-42. 
[4] Thomas H. Cormen, Charles E. Lieserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, Prentice Hall of India, 2009. 
[5] Anany Levitin, “Introduction to the design & analysis of algorithms”, Pearson Education, Second Edition, 2009. 
[6] D.Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning. In SEA, pages 376-387, 2011. 
[7] D.Delling, A. V. Goldberg, and R. F. Werneck,” Hub label compression”, SEA, pages 18-29, 2013. 
[8] M. Hilger, E. Kohler, R. H. Mohring, and H. Schilling, “Fast point-to-point shortest path computations with arc- ags. The Shortest Path Problem”, Ninth DIMACS Implementation Challenge, 74:41-72, 2009. 
[9] Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck, “A hub-based labeling algorithm for shortest paths in road networks”, SEA, pages 230-241, 2011. 
[10] Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck, “Hierarchical hub labelings for shortest paths”, ESA, pages 24-35, 2012.