AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

An Effect of using a Storage Medium in Dijkstra Algorithm Performance for Ideal Implicit Path Cost


Affiliations
1 Department of Computer Sciences, Sebha University, Sebha, Libya
 

The graph model is used widely for representing connected objects within a specific area. These objects are defined as nodes; where the connection is represented as arc called edges. The shortest path between two nodes is one of the most focus researchers’ attentions. Many algorithms are developed with different structured approach for reducing the shortest path cost. The most widely used algorithm is Dijkstra algorithm. This algorithm has been represented with various structural developments in order to reduce the shortest path cost. This paper highlights the idea of using a storage medium to store the solution path from Dijkstra algorithm, then, uses it to find the implicit path in an ideal time cost. The performance of Dijkstra algorithm using an appropriate data structure is improved. Our results emphasize that the searching time through the given data structure is reduced within different graphs models.

Keywords

Dijkstra Algorithm, Data Structure, Time Complexity, Implicit Path, Graphs.
User
Notifications
Font Size

  • Arman, N., & Khamayseh, F., (2015) "A Path-Compression Approach for Improving Shortest-Path Algorithms," International Journal of Electrical and Computer Engineering, vol. 5, p. 772,.

  • Broumi, S., Bakal, A., Talea, M., Smarandache, F., & Vladareanu, L., "Applying Dijkstra algorithm for solving neutrosophic shortest path problem," International Conference on Advanced Mechatronic Systems (ICAMechS), 2016, pp. 412-416.

  • Gao, J., Zhao, Q., Ren, W., Swami, A., Ramanathan, R., & Bar-Noy, A., (2015) "Dynamic shortest path algorithms for hypergraphs," IEEE/ACM Transactions on Networking, vol. 23, pp. 1805-1817.

  • Gutenschwager, K., Völker, S., Radtke, A., & Zeller, G., "The shortest path: Comparison of different approaches and implementations for the automatic routing of vehicles," in Simulation Conference (WSC), Proceedings of the 2012 Winter, 2012, pp. 1-12.

  • Khamayseh, F., & Arman, N., (2015) "Improvement of Shortest-Path Algorithms Using Subgraph’s Heuristics”. Journal of Theoretical & Applied Information Technology, vol. 76.

  • Niemeyer, K., E., & Sung, C.-J., (2016) "On the importance of graph search algorithms for DRGEP-based mechanism reduction methods," Combustion and Flame, vol. 158, pp. 1439-1443.

  • Shu-Xi, W., (2012) "The improved dijkstra's shortest path algorithm and its application," Procedia Engineering, vol. 29, pp. 1186-1190.

  • Douglas,W., B., (2001) Introduction to Graph Theory, Pernice Hall.

  • Chandra, "Shortest Path Problem for Public Transportation Using GPS and Map Service," 2012.

  • Saab, Y., & VanPutte, M., (1999) "Shortest path planning on topographical maps," IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, vol. 29, pp. 139-150.

  • Xing, S., & Shahabi, C., "Scalable shortest paths browsing on land surface," in Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010, pp. 89-98.

  • Faro, A., & Giordano, D., (2016) "Algorithms to find shortest and alternative paths in free flow and congested traffic regimes," Transportation Research Part C: Emerging Technologies, vol. 73, pp. 1-29.

  • Dijkstra., E., W., (1959) “A note on Two Problems in Connexion with graphs”, Numerische Mathematik, 1, 269-271.

  • Thorat, S., & Rahane, S., (2016) “Review of Shortest Path Algorithm”, IRJET, vol 3, issue 8.

  • Yao, B., Yin, J., Zhou, H., & Wu, W., (2016) "Path Optimization Algorithms Based on Graph Theory," International Journal of Grid and Distributed Computing, vol. 9, pp. 137-148.

  • Cormen, T., Leiserson, C., Rivest, R., & Stein, C., (2009) Introduction to Algorithms, 3rd. ed., MIT Press, London.

  • Levitin, A., (2012) Introduction to the Design and Analysis of Algorithms, 3rd ed., Pearson Education, Inc., Addison-Wesley.

  • Jain, A., Datta, U., & Joshi, N., (2016) "Implemented modification in Dijkstra‟ s Algorithm to find the shortest path for N nodes with constraint," International Journal of Scientific Engineering and Applied Science, vol. 2, pp. 420-426.

  • Xie, D., Zhu, H., Yan, L., Yuan, S., & Zhang, J., "An improved Dijkstra algorithm in GIS application," in World Automation Congress (WAC), 2012, pp. 167-169.

  • Lu, J., & Dong, C., "Research of shortest path algorithm based on the data structure," in the 3rd International Conference of Software Engineering and Service Science (ICSESS), 2012 IEEE, 2012, pp. 108-110.

  • Kong, D., Liang, Y., Ma, X., & Zhang, L., "Improvement and Realization of Dijkstra Algorithm in GIS of Depot," in the International Conference on Control, Automation and Systems Engineering (CASE), 2011, 2011, pp. 1-4.

  • Deng, Y., Chen, Y., Zhang, Y., & Mahadevan, S., (2012) "Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment," Applied Soft Computing, vol. 12, pp. 1231-1237


Abstract Views: 277

PDF Views: 125




  • An Effect of using a Storage Medium in Dijkstra Algorithm Performance for Ideal Implicit Path Cost

Abstract Views: 277  |  PDF Views: 125

Authors

Ibtusam Alashoury
Department of Computer Sciences, Sebha University, Sebha, Libya
Mabroukah Amarif
Department of Computer Sciences, Sebha University, Sebha, Libya

Abstract


The graph model is used widely for representing connected objects within a specific area. These objects are defined as nodes; where the connection is represented as arc called edges. The shortest path between two nodes is one of the most focus researchers’ attentions. Many algorithms are developed with different structured approach for reducing the shortest path cost. The most widely used algorithm is Dijkstra algorithm. This algorithm has been represented with various structural developments in order to reduce the shortest path cost. This paper highlights the idea of using a storage medium to store the solution path from Dijkstra algorithm, then, uses it to find the implicit path in an ideal time cost. The performance of Dijkstra algorithm using an appropriate data structure is improved. Our results emphasize that the searching time through the given data structure is reduced within different graphs models.

Keywords


Dijkstra Algorithm, Data Structure, Time Complexity, Implicit Path, Graphs.

References