CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Shortest Path Algorithm using Hashing and Queue

by Shruti Pant, Pooja Khulbe
journal cover thumbnail

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.

Powered by PhDFocusTM