Finding The Shortest Route Between East Oku's Islamic Boarding Schools Using The Dijkstra Algorithm

Abstract

This study aims to measure the distance between Islamic boarding schools in East Oku, using the Dijkstra Algorithm method to make it easier to determine the shortest route from the point of the Nurul Huda Sukaraja Islamic Boarding School to the Subulussalam Sriwangi Islamic Boarding School. In previous research, namely determining the shortest route when distributing from vegetable gardens to warehouses between toll and non-toll routes to minimize costs. In graph theory, the Dijkstra algorithm efficiently calculates the shortest path between any pair of nodes in a weighted graph, both positive and negative. This algorithm works with the principle of dynamic programming and can overcome graphs with a negative weight as long as there are no negative cycles. In its implementation, the Dijkstra algorithm iteratively updates the shortest distance between nodes by directly comparing paths with paths passing through other nodes. The advantage of this algorithm lies in its simplicity and ability to calculate the shortest distance between all pairs of nodes in a single process. The study results show that the Dijkstra Algorithm can show the fastest and most efficient alternative routes compared to conventional routes. Calculations using the Dijkstra Algorithm method produce the shortest trajectory starting from point 1-4-5 with a distance of 48 km, the most optimal route between the location and destination points.