Comparison of the Exhaustive Algorithm and Johnson’s Algorithm in Determining the Shortest Path to Sipiso Piso Tourism

Abstract

Determining the shortest route to a tourist destination is an important aspect of travel planning and tourism management, especially for locations with many alternative routes like Sipiso-Piso Tourism. This study aims to compare the performance of two algorithms in determining the shortest path, namely the Exhaustive algorithm and Johnson’s Algorithm. The Exhaustive method evaluates all possible routes to find the optimal path, while Johnson’s Algorithm combines a weighted directed graph approach for efficient shortest path calculations on a complete graph. Research data were collected through route mapping and distance weighting between travel points to the Sipiso-Piso tourist destination, and then processed using both algorithms. The analysis results show that the Exhaustive Algorithm is capable of finding the shortest path with high accuracy, but its computation time significantly increases as the number of travel points increases. Meanwhile, Johnson’s Algorithm offers better time efficiency while still being able to produce the shortest path with a competitive level of accuracy. These findings have practical implications for the development of algorithm-based tourism navigation systems that prioritise a balance between accuracy and computational efficiency.