Comparison Analysis of Graph Theory Algorithms for Shortest Path Problem

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

• dijkstra algorithm
• bellman-ford algorithm
• floyd-warshall algorithm
• johnson algorithm
• ant colony algorithm