DIJKSTRA’S SHORTEST-PATH ALGORITHM APPLICATION Farah Husna Ahmad Nasir #1, Mohamed Faidz Mohamed Said #2 # Universiti Teknologi MARA 70300 Seremban, Negeri Sembilan, MALAYSIA 1 farahusna694@gmail.com 2 mohdfaidz@uitm.edu.my Abstract—One of famous topic in study of graph theory is shortest path problem because of its wide application field, outspreading from operational research to the disciplines of computer science, topography, programmed control, and stream of traffic. Researchers in the relevant field have presented many algorithms according to its existing application, but most of the algorithms are only enhancements based on Dijkstra algorithm. The objectives of this research are to improve the efficiency of the shortest path algorithms and to enhance the kinds of it. This paper provided an upgraded calculation method of shortest path using cellular automata model, which is designed to examine the shortest path from one node to another node. This evaluation should be particularly useful to researchers and experts in management science, operations research, transportation, and Geographic Information Systems. Keywords: Dijkstra, Shortest path algorithm, Graph REFERENCES [1] F. B. Zhan and C. E. Noon, "Shortest path algorithms: an evaluation using real road networks," Transportation Science, vol. 32, pp. 65-73, 1998. [2] D. B. Johnson, "A note on Dijkstra's shortest path algorithm," Journal of the ACM (JACM), vol. 20, pp. 385-388, 1973. [3] M. Wang, Y. Qian, and X. Guang, "Improved calculation method of shortest path with cellular automata model," Kybernetes, vol. 41, pp. 508-517, 2012. [4] M. Xu, Y. Liu, Q. Huang, Y. Zhang, and G. Luan, "An improved Dijkstra’s shortest path algorithm for sparse network," Applied Mathematics and Computation, vol. 185, pp. 247-254, 2007. [5] C.-L. Chen, C.-T. Lai, and J.-Y. Lee, "Transshipment model-based linear programming formulation for targeting hybrid power systems with power loss considerations," Energy, vol. 75, pp. 24-30, 2014. [6] Y. Jian, R. Yong, L. Feng, and S. XIU-MING, "Phase transition and collective correlation behavior in the complex computer network," 2001. [7] L. Ji, W. Bing-Hong, J. Pin-Qun, Z. Tao, and W. Wen-Xu, "Growing complex network model with acceleratingly increasing number of nodes," 2006. [8] X.-j. Wu and H.-f. Xue, "Shortest Path Algorithm Based on Cellular Automata Extend Model [J]," Computer Applications, vol. 5, 2004. [9] Y. Wang, "Study for solving the path on the three-dimensional surface based on Cellular Automata method," Modern Applied Science, vol. 4, p. 196, 2010. [10] K. Murota and A. Shioura, "Dijkstra’s algorithm and L-concave function maximization," Mathematical Programming, vol. 145, pp. 163-177, 2014. [11] S. Peyer, D. Rautenbach, and J. Vygen, "A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing," Journal of Discrete Algorithms, vol. 7, pp. 377-390, 2009. [12] C. Gunkel, A. Stepper, A. C. Müller, and C. H. Müller, "Micro crack detection with Dijkstra’s shortest path algorithm," Machine Vision and Applications, vol. 23, pp. 589-601, 2012. [13] S. Mukherjee, "Dijkstra’s algorithm for solving the shortest path problem on networks under intuitionistic fuzzy environment," Journal of Mathematical Modelling and Algorithms, vol. 11, pp. 345-359, 2012. [14] S. M. Nor and S. T. Nadhiah, "Finding a minimum path using Dijkstra's algorithm/Syarifah Teh Nadhiah Syed Mohamad Nor," Universiti Teknologi MARA, 2004. [15] L. Xiong and B. Li, "The energy conservation optimization design of the cutting edges of the twist drill based on Dijkstra’s algorithm," The International Journal of Advanced Manufacturing Technology, vol. 82, pp. 889-900, 2016. [16] D. Li and K. Niu, "Dijkstra's algorithm in AGV," in Industrial Electronics and Applications (ICIEA), 2014 IEEE 9th Conference on, pp. 1867-1871, 2014. [17] L. Verscheure, L. Peyrodie, N. Makni, N. Betrouni, S. Maouche, and M. Vermandel, "Dijkstra's algorithm applied to 3D skeletonization of the brain vascular tree: Evaluation and application to symbolic," in Engineering in Medicine and Biology Society (EMBC), 2010 Annual International Conference of the IEEE, pp. 3081-3084, 2010.