CFP last date
20 June 2024
Reseach Article

Shortest Path Algorithm using Hashing and Queue

by Shruti Pant, Pooja Khulbe
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 89 - Number 14
Year of Publication: 2014
Authors: Shruti Pant, Pooja Khulbe
10.5120/15699-4607

Shruti Pant, Pooja Khulbe . Shortest Path Algorithm using Hashing and Queue. International Journal of Computer Applications. 89, 14 ( March 2014), 17-21. DOI=10.5120/15699-4607

@article{ 10.5120/15699-4607,
author = { Shruti Pant, Pooja Khulbe },
title = { Shortest Path Algorithm using Hashing and Queue },
journal = { International Journal of Computer Applications },
issue_date = { March 2014 },
volume = { 89 },
number = { 14 },
month = { March },
year = { 2014 },
issn = { 0975-8887 },
pages = { 17-21 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume89/number14/15699-4607/ },
doi = { 10.5120/15699-4607 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:09:14.413498+05:30
%A Shruti Pant
%A Pooja Khulbe
%T Shortest Path Algorithm using Hashing and Queue
%J International Journal of Computer Applications
%@ 0975-8887
%V 89
%N 14
%P 17-21
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Y. Cao, "The Shortest path algorithm in data structures", Yibin University, vol. 6, 2007, pp. 82-84.
  2. Q. Sun, J. H. Shen, J. Z Gu, "An improved Dijkstra algorithm", Computer Engineering And Applications, vol. 3, 2002, pp. 99-101.
  3. Jinhao Lu, Chi Dong, Research of the shortest path algorithm based on the data structure [J], IEEE, 2012, pp. 108-12.
  4. L. B. Chen, R. T Liu, "A dijkstra's shortest path algorithm", Harbin University of Technology, vol 3, 2008,pp. 35-37.
  5. F. S. XU,C. Tian, "All the Shortest Path Algorithm", Computer Engineering and Science, vol. 12, 2006, pp. 83-84.
  6. 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.
  7. Fuhao ZHANG, Ageng QIU, Qingyuan LI," Improve on dijkstra shortest path algorithm for huge data", ISPRS, 2009.
  8. Noto m, Sato h. ," Improved Dijkstra algorithm for network routing" Systems, man and cybermatics, IEEE international conference, vol 3, pp 2316 – 2320, 2000.
  9. 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.
  10. F. S. XU. "Shortest path calculation algorithm". Computer Applications, vol 5, pp. 88-89, 2004.
Index Terms

Computer Science
Information Sciences

Keywords

Shortest path Dijkstra algorithm Queue Hashing Stack.