Implementasi Algoritma Shortest Path untuk Optimasi Rute pada Sistem Navigasi Lokasi - Sirlia Sahid; Maissy Angelica Pakpahan; Rifqi Putra Winanda; Muhammad Raihansyah Lubis; Adidtya Perdana (Bridge : Jurnal Publikasi Sistem Informasi dan Telekomunikasi, 2026)
The increasing complexity of urban road networks demands intelligent navigation systems capable of determining optimal routes efficiently. This research implements the Dijkstra Shortest Path algorithm to optimize route search on a location navigation system in Medan City. The system models a road network as a weighted graph comprising 57 strategic locations and over 90 road connections, represented using adjacency list data structures. The Dijkstra algorithm, implemented in Python using the heapq module for priority queue management, achieves an optimal time complexity of O((V+E) log V). The system features five main functions: shortest route search, popular routes, location listing, dynamic location addition, and dynamic road connection addition. System testing using a case study from Kualanamu Airport to the University of North Sumatra (USU) yielded an optimal route of 16.5 km through 4 road segments. Results demonstrate that the system successfully determines the most efficient route, provides accurate distance and travel time information for multiple transport modes (motorcycle, car, walking), and presents step-by-step journey guidance. This research contributes as a practical reference for applying shortest path algorithms in urban areas and serves as a foundation for developing more complex navigation applications in the future.