Implementasi Algoritma Dijkstra dalam Menentukan Rute Terpendek Evakuasi Medis Bencana

Abstract

Effective disaster response requires a fast and accurate medical evacuation system, especially in high-risk areas such as Jember Regency. One of the critical issues in medical evacuation is determining the shortest route from evacuation points to the nearest healthcare facilities. This research aims to implement the Dijkstra algorithm to determine the shortest medical evacuation route and to develop a web based system capable of visualizing this route interactively. The methodology used follows the Waterfall software development model, involving literature studies, requirement analysis, design system, geographic data collection (evacuation points, hospitals, clinics), graph design, Dijkstra algorithm implementation, and system testing using the Black Box method. Route weights between nodes were determined using the Analytical Hierarchy Process (AHP) with a time-priority approach, which integrates both distance and estimated travel time (with weights α = 0.33 and β = 0.67). The results show that the Dijkstra algorithm successfully determines optimal evacuation routes. A case study from evacuation point TP1 to R4 produced the minimum total weight of 96.68. In addition, five test scenarios based on real locations in Jember were conducted to compare manually chosen routes with algorithm-generated routes. The results consistently demonstrate that the Dijkstra algorithm produces shorter paths and faster travel times. The system was successfully developed using PHP with Laravel framework, MySQL as the database, and Google Maps API to visualize the shortest path. Testing results confirm that the system functions as expected and that the algorithm’s output aligns with manual calculations, demonstrating high accuracy and reliability