Research Article
Shortest Path Algorithm using Hashing and Queue
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 89 - Issue 14 |
| Published: March 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 },
year = { 2014 },
volume = { 89 },
number = { 14 },
pages = { 17-21 },
doi = { 10.5120/15699-4607 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Shruti Pant
%A Pooja Khulbe
%T Shortest Path Algorithm using Hashing and Queue%T
%J International Journal of Computer Applications
%V 89
%N 14
%P 17-21
%R 10.5120/15699-4607
%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
- 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.
Index Terms
Keywords