Call for Paper - January 2024 Edition
IJCA solicits original research papers for the January 2024 Edition. Last date of manuscript submission is December 20, 2023. Read More
Shortest Path Algorithm using Hashing and Queue
International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 89 - Number 14
Year of Publication: 2014
|
10.5120/15699-4607 |
Shruti Pant and Pooja Khulbe. Article: Shortest Path Algorithm using Hashing and Queue. International Journal of Computer Applications 89(14):17-21, March 2014. Full text available. BibTeX
@article{key:article,
author = {Shruti Pant and Pooja Khulbe},
title = {Article: Shortest Path Algorithm using Hashing and Queue},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {89},
number = {14},
pages = {17-21},
month = {March},
note = {Full text available}
}
Abstract
Finding the shortest path in a graph means selecting the path between source and destination which gives the minimum path length. This problem of finding the shortest path can be solved using Dijkstra algorithm. The time complexity of Dijkstra algorithm is high. Looking at the shortcoming of traditional Dijkstra algorithm, this paper has proposed a new method to improve the time complexity of this algorithm using queue and hashing techniques. The time complexity of the improved algorithm is O(n log n).
References
- Y. Cao, "The Shortest path algorithm in data structures", Yibin University, vol. 6, 2007, pp. 82-84.
- Q. Sun, J. H. Shen, J. Z Gu, "An improved Dijkstra algorithm", Computer Engineering And Applications, vol. 3, 2002, pp. 99-101.
- Jinhao Lu, Chi Dong, Research of the shortest path algorithm based on the data structure [J], IEEE, 2012, pp. 108-12.
- L. B. Chen, R. T Liu, "A dijkstra's shortest path algorithm", Harbin University of Technology, vol 3, 2008,pp. 35-37.
- F. S. XU,C. Tian, "All the Shortest Path Algorithm", Computer Engineering and Science, vol. 12, 2006, pp. 83-84.
- Y. Tang, Y. Zhang, H. Chen, "A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting", in Proc. of IEEE HPCC, pp. 155-161, 2008.
- Fuhao ZHANG, Ageng QIU, Qingyuan LI," Improve on dijkstra shortest path algorithm for huge data", ISPRS, 2009.
- Noto m, Sato h. ," Improved Dijkstra algorithm for network routing" Systems, man and cybermatics, IEEE international conference, vol 3, pp 2316 – 2320, 2000.
- Yizhen Huang, Qingming Yi, Min Shi, "An Improved Dijkstra Shortest Path Algorithm", Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013), pp. 0226-0229, 2013.
- F. S. XU. "Shortest path calculation algorithm". Computer Applications, vol 5, pp. 88-89, 2004.