Perbandingan Algoritma Dijkstra dan A* Dalam Penentuan Jalur Light Rail Transit di Kota Medan

Abstract

The significant economic growth and population increase in the city of Medan have led to a rise in mobility demand, thereby triggering traffic congestion issues. A solution to this problem lies in the development of a Light Rail Transit (LRT) system. In this process, determining potential locations for LRT stations is crucial. The selected locations must satisfy four key aspects: environmental, economic, accessibility, and operational aspects. From the identified potential locations, two route recommendations for LRT development were provided, using the shortest path algorithm. This study focuses on the comparison between Dijkstra's algorithm and the A* algorithm, measured based on each algorithm's complexity, the number of station points, the total distance of the route produced by each algorithm, and the time required by each algorithm to find the shortest path. Both algorithms employ a greedy approach, selecting the path deemed shortest at each step. Dijkstra's algorithm finds the shortest path by exploring all possible pairs of points, while A* finds the shortest path using a heuristic value. This study found that for the first route recommendation, Dijkstra's algorithm and the A* algorithm yielded the same shortest path, with the same number of points and total distance. However, for the second route recommendation, Dijkstra's algorithm found a shorter total distance compared to the distance produced by the A* algorithm. In terms of time, the A* algorithm was faster than Dijkstra's algorithm. This research provides a reference for determining the shortest path and selecting optimal LRT station locations