Penerapan Algoritma A* untuk Penentuan Jalur Terpendek dari Kecamatan Medan Selayang ke Deli Park Mall, Medan

Penentuan jalur terpendek merupakan aspek krusial dalam sistem navigasi modern, khususnya di kota besar dengan tingkat kepadatan lalu lintas tinggi seperti Medan. Penelitian ini bertujuan untuk menerapkan algoritma A* dalam menentukan rute tercepat dari Kecamatan Medan Selayang ke Deli Park Mall, Medan, dengan menggunakan data jaringan jalan aktual yang diperoleh secara manual dari Google Maps. Pendekatan graf manual ini merupakan fitur pembeda penting dari penelitian ini karena memberikan kontrol penuh terhadap struktur graf dan memastikan akurasi data lokal yang tidak tersedia dalam dataset otomatis seperti OpenStreetMap, sehingga lebih sesuai untuk konteks geografis spesifik Medan. Graf jaringan jalan dimodelkan sebagai graf berbobot menggunakan bahasa pemrograman Python, di mana simpul merepresentasikan titik lokasi dan sisi merepresentasikan jarak antar titik. Algoritma A* dipilih karena kemampuannya menggabungkan biaya aktual (g(n)) dan estimasi heuristik (h(n)) sehingga pencarian menjadi lebih efisien dibandingkan algoritma konvensional. Hasil penelitian menunjukkan bahwa algoritma A* berhasil menentukan rute optimal sepanjang 8,9 km melalui jalur A-B-C-D-E-F-G-H-I-J-K-L, dan dieksekusi dalam waktu lebih cepat dibanding algoritma Dijkstra dengan selisih waktu 0,05 detik. Rute tersebut divisualisasikan menggunakan graf untuk mendukung analisis spasial. Penelitian ini diharapkan dapat menjadi dasar pengembangan sistem navigasi berbasis graf pada konteks lokal dengan pendekatan metodologi yang dapat direplikasi untuk kota-kota besar lainnya di Indonesia.