Penentuan Rute Terpendek antara Stasiun Kereta Api Medan dan Universitas Sumatera Utara dengan Algoritma Greedy dan Floyd-Warshall

Abstract

Transportation is an important factor in supporting community mobility, especially in dense areas such as Medan City. The route between Medan Railway Station and the University of North Sumatra (USU) is one of the strategic routes with high traffic levels. This research aims to determine the shortest route between the two points by comparing two pathfinding algorithms, namely Greedy and Floyd-Warshall, which are implemented through a weighted graph theory approach manually and using the Python programming language. A road network graph was constructed based on distance estimation data from Google Maps, and the shortest route was calculated using both algorithms. The results of the study show that the Floyd-Warshall algorithm produces a route with a total distance of 4,9 km and a length of 7, while the Greedy algorithm produces a route with a total distance of 7,65 km and a length of 9. In terms of programming time, the Greedy algorithm requires a shorter programming time of 0,000052 seconds, while Floyd-Warshall takes 0,005799 seconds. Therefore, it can be said that in this study the Greedy algorithm requires a shorter programming time, while the Floyd-Warshall algorithm produces a shorter route.