Penentuan Rute Terpendek di Wilayah Kecamatan Teluk Mutiara Menggunakan Algoritma Floyd-Warshall

Abstract

Shortest route search is a problem that can be solved by using the concept of shortest path in Graph theory. In Teluk Mutiara sub-district, there are many alternative paths that can be taken to reach the destination, thus allowing errors in the selection of the right path, which can cause waste of time and money. The Floyd-Warshall algorithm is used to calculate the shortest route by connecting all points to the destination, by starting from the starting point and iteratively extending the path to reach the destination point with the minimum weight. This research uses observation and documentation data from Google Maps and Google Earth, as well as field validation to obtain data on road intersection points and the length of roads connecting them. The data is then represented in the form of a weighted graph, with 16 road intersection points as vertices and 22 roads as edges, and the distance between points as edge weights. The results of the Floyd-Warshall algorithm calculation show the minimum distance between each road intersection point and its route.