Comparison Analysis of Graph Theory Algorithms for Shortest Path Problem
(1) Informatics Study Program, Faculty of Engineering, Darma Cendika Catholic University
(2) Informatics Study Program, Faculty of Engineering, Darma Cendika Catholic University
(3) Informatics Study Program, Faculty of Engineering, Darma Cendika Catholic University
(*) Corresponding Author
Abstract
The Sumba region, Indonesia, is known for its extraordinary natural beauty and unique cultural richness. There are 19 interesting tourist attractions spread throughout the area, but tourists often face difficulties in planning efficient visiting routes. From this case, it can be solved by applying graph theory in terms of searching for the shortest distance which is completed using the shortest path search algorithm. Then these 19 tourist objects are used to build a weighted graph, where the nodes represent the tourist objects and the edges of the graph describe the distance or travel time between these objects. Therefore, this research aims to compare the shortest path search algorithm with parameters to compare the shortest distance results, algorithm complexity and execution time for tourism in the Sumba area. The results of this research involve a comparison of several shortest path search algorithms, with the aim of finding the shortest distance results, algorithm complexity, and execution time for tourism in the Sumba area. Based on the test results of the five algorithms with the parameters that have been prepared, and the findings show that each algorithm has its own characteristics, the results are as follows: Dijkstra's algorithm can be used to calculate the shortest route for single-source and single-destination types. This resembles the Bellman-Ford algorithm, only the Bellman-Ford algorithm can be used simultaneously on graphs that have negative weight values. Meanwhile, the Floyd-Warshall algorithm is suitable for use on the all-pairs type. Then, the Johnson Algorithm can be used to determine the shortest path from all pairs of paths where the destination node is located in the graph. Finally, the Ant Colony algorithm to compute from a node to each pair of destination nodes.
Keywords
Full Text:
PDFReferences
B. S. N Assistant professor GFGC, “A Study on Graph Coloring,” Int J Sci Eng Res, vol. 8, no. 5, 2017, [Online]. Available: http://www.ijser.org
Tirastittam Pimploi and Waiyawuththanapoom Phutthiwat, “Public Transport Planning System by Dijkstra Algorithm Case Study Bangkok Metropolitan Area,” International Journal of Computer and Information Engineering, vol. 08, 2014.
M. Iqbal, K. Zhang, S. Iqbal, and I. Tariq, “A Fast and Reliable Dijkstra Algorithm for Online Shortest Path,” International Journal of Computer Science and Engineering, vol. 5, no. 12, pp. 24–27, Dec. 2018, doi: 10.14445/23488387/IJCSE-V5I12P106.
Z. Jiang, V. Sahasrabudhe, A. Mohamed, H. Grebel, and R. Rojas-Cessa, “Greedy algorithm for minimizing the cost of routing power on a digital microgrid,” Energies (Basel), vol. 12, no. 16, Aug. 2019, doi: 10.3390/en12163076.
A. Kejriwal and A. Temrikar, “Graph Theory and Dijkstra’s Algorithm:A solution for Mumbai’s BEST buses,” The International Journal of Engineering and Science (IJES) ||, pp. 23–42, 2019, doi: 10.9790/1813-0810014047www.theijes.com.
Umamaheswari K., Pavithra A., Srinivashini S., and Subipriya S., “Tackling a Shortest Path Having a Negative Cycle by using Johnson_s Calculation,” TEST Engineering & Management, vol. 81, 2019.
M. Okwu and I. Emovon, “Application of Johnson’s algorithm in processing jobs through two-machine system,” Journal of Mechanical and Energy Engineering, vol. 4, no. 1, pp. 33–38, Aug. 2020, doi: 10.30464/jmee.2020.4.1.33.
M. Redi and M. Ikram, “Dimension Reduction and Relaxation of Johnson’s Method for Two Machines Flow Shop Scheduling Problem,” Sultan Qaboos University Journal for Science [SQUJS], vol. 25, no. 1, p. 26, Jun. 2020, doi: 10.24200/squjs.vol25iss1pp26-47.
C. Dalfó and M. À. Fiol, “Graphs, friends and acquaintances,” Electronic Journal of Graph Theory and Applications, vol. 6, no. 2, pp. 282–305, 2018, doi: 10.5614/ejgta.2018.6.2.8.
X. Z. Wang, “The Comparison of Three Algorithms in Shortest Path Issue,” in Journal of Physics: Conference Series, Institute of Physics Publishing, Oct. 2018. doi: 10.1088/1742-6596/1087/2/022011.
A. A. B. A. Homaid, A. R. A. Alsewari, K. Z. Zamli, and Y. A. Alsariera, “Adapting the elitism on greedy algorithm for variable strength combinatorial test cases generation,” IET Software, vol. 13, no. 4, pp. 286–294, Aug. 2019, doi: 10.1049/iet-sen.2018.5005.
A. M. Benjamin, S. A. Rahman, E. M. Nazri, and E. A. Bakar, “Developing A Comprehensive Tour Package Using An Improved Greedy Algorithm With Tourist Preferences,” 2019. [Online]. Available: https://www.researchgate.net/publication/335541687
M. Elizabeth, B. Gani, M. A. Safitri, C. Lusiana, and M. Dewi, “Real Time Public Transportation Navigator System in Jakarta by Using Greedy Best First Search Algorithm,” 2018, [Online]. Available: http://www.emarketer.com/Article/Asia-Pacific-
S. Orhani, “Finding the Shortest Route for Kosovo Cities Through Dijkstra’s Algorithm,” Middle European Scientific Bulletin, vol. 25, 2022, [Online]. Available: https://www.researchgate.net/publication/361443814
R. Chen, “Dijkstra’s Shortest Path Algorithm and Its Application on Bus Routing,” 2022.
V. Sakharov, S. Chernyi, S. Saburov, and A. Chertkov, “Automatization Search for the Shortest Routes in the Transport Network Using the Floyd-warshell Algorithm,” in Transportation Research Procedia, Elsevier B.V., 2021, pp. 1–11. doi: 10.1016/j.trpro.2021.02.041.
N. Syuhada, M. Pazil, N. Mahmud, S. H. Jamaluddin, N. Farasyaqirra, and B. Mustafa, “Shortest Path from Bandar Tun Razak to Berjaya Times Square using Dijkstra Algorithm,” 2020. [Online]. Available: https://jcrinn.com
G. Deepa, P. Kumar, A. Manimaran, K. Rajakumar, and V. Krishnamoorthy, “Dijkstra Algorithm Application: Shortest Distance between Buildings,” International Journal of Engineering & Technology, vol. 7, no. 4.10, p. 974, Oct. 2018, doi: 10.14419/ijet.v7i4.10.26638.
Sari I. P., Fahroza M. F., Mufit M. I., and Qathrunad I. F., “Implementation of Dijkstra’s Algorithm to Determine the Shortest Route in a City,” Journal of Computer Science, Information Technologi and Telecommunication Engineering, vol. 02, pp. 134–138, Mar. 2021, doi: 10.30596/jcositte.v2i1.6503.
O. Khaing, H. Htight Wai, and E. Ei Myat, “Using Dijkstra’s Algorithm for Public Transportation System in Yangon Based on GIS,” 2018. [Online]. Available: www.ijsea.com442
T. Sari, A. S. Zain, and A. N. Handayani, “Application Of DIJKSTRA Algorithm For Network Troubleshooting In SMK Telkom Malang,” 2019.
O. K. Sulaiman, A. M. Siregar, K. Nasution, and T. Haramaini, “Bellman Ford algorithm - In Routing Information Protocol (RIP),” in Journal of Physics: Conference Series, Institute of Physics Publishing, Apr. 2018. doi: 10.1088/1742-6596/1007/1/012009.
P. Gupta and V. Pathak, “A Minimum Spanning Tree-based Routing Technique of FAT Tree for Efficient Data Center Networking,” Mathematical Statistician and Engineering Applications, vol. 71, no. 1, Jan. 2022, doi: 10.17762/msea.v71i1.44.
F. Mukhlif and A. Saif, “Comparative Study On Bellman-Ford And Dijkstra Algorithms,” 2020. [Online]. Available: https://www.researchgate.net/publication/340790429
Botsis D. and Panagiotopoulos E., “Determination of the shortest path in the university campus of Serres using the Dijkstra and Bellman‐Ford algorithms,” 2020.
A. Manan, S. Imran, and A. Lakyari, “Single source shortest path algorithm Dijkstra and Bellman-Ford Algorithms: A Comparative study,” INTERNATIONAL JOURNAL OF COMPUTER SCIENCE AND EMERGING TECHNOLOGIES (IJCET), vol. 3, no. 2, pp. 25–28, 2019, [Online]. Available: https://ijcet.salu.edu.pk
S. W. G. Abusalim, R. Ibrahim, M. Zainuri Saringat, S. Jamel, and J. Abdul Wahab, “Comparative Analysis between Dijkstra and Bellman-Ford Algorithms in Shortest Path Optimization,” in IOP Conference Series: Materials Science and Engineering, IOP Publishing Ltd, Sep. 2020. doi: 10.1088/1757-899X/917/1/012077.
O. Yu Lavlinskaya, T. V. Kurchenkova, and O. V. Kuripta, “Shortest path algorithm for graphs in instances of semantic optimization,” in Journal of Physics: Conference Series, Institute of Physics Publishing, May 2020. doi: 10.1088/1742-6596/1479/1/012036.
Rachmad A., Syarief M., Rochman E. M. S., and R. G. Husni, “Ant colony optimization model for determining the shortest route in Madura-Indonesia tourism places,” Journal of Mathematical and Computational Science, 2021, doi: 10.28919/jmcs/7078.
D. R. Anamisa, A. Rachmad, and E. M. S. Rochman, “Ant Colony System Based Ant Adaptive for Search of the Fastest Route of Tourism Object Jember, East Java,” in Journal of Physics: Conference Series, Institute of Physics Publishing, 2020. doi: 10.1088/1742-6596/1477/5/052053.
T. Herianto, “Implementation of the Ant Colony System Algorithm in the Lecture Scheduling Process,” Instal : Jurnal Komputer, vol. 12, 2020.
I. G. Ivanov, G. V. Hristov, and V. D. Stoykova, “Algorithms for optimizing packet propagation latency in software-defined networks,” in IOP Conference Series: Materials Science and Engineering, IOP Publishing Ltd, Feb. 2021. doi: 10.1088/1757-899X/1031/1/012072.
DOI: https://doi.org/10.32736/sisfokom.v12i3.1756
Refbacks
- There are currently no refbacks.
Indexed By:
