PERBANDINGAN KINERJA DAN KOMPLEKSITAS ALGORITMA FLOYD-WARSHALL DAN GREEDY PADA RUTE EVAKUASI BANJIR

Abstract

Widang Subdistrict in Tuban Regency is prone to flooding due to the overflow of the Bengawan Solo River, making the development of efficient evacuation routes critically important. This study compares the performance and time complexity of the Floyd–Warshall and Greedy algorithms in determining the shortest evacuation routes from twelve flood-prone locations to a single evacuation post. The road network is modeled as a weighted graph representing flood points, alternative routes, and the evacuation post. Floyd–Warshall employs dynamic programming with a time complexity of O(n³) to compute global shortest paths, while Greedy selects routes based on locally optimal decisions with a complexity of O (V + E). The results show that both algorithms produce identical routes and distances for nine locations. For the other three locations, Floyd–Warshall provides a more optimal solution with a maximum distance difference of 0.2 km. Complexity analysis reveals that Greedy is computationally more efficient for large-scale graphs, whereas Floyd–Warshall guarantees global optimality even though its processing time increases as the number of vertices grows. Therefore, Greedy is more suitable for emergency response scenarios, while Floyd–Warshall is better suited for pre-disaster evacuation planning.