Implementasi Algoritma Dijkstra Menentukan Rute Terpendek Dari Unika St. Thomas Menuju Kantor dinas kependudukan Kota Medan

Abstrak

Studi ini meneliti penerapan metode algoritma Dijkstra dalam menentukan jalur terpendek yang menghubungkan Universitas Katolik Santo Thomas (Unika St. Thomas) dengan Kantor Dinas Kependudukan dan Pencatatan Sipil di Medan. Pemilihan algoritma Dijkstra didasarkan pada keunggulan efektivitasnya dalam menemukan lintasan optimal pada struktur graf yang memiliki bobot dengan tingkat kompleksitas waktu O((V + E) log V). Metodologi penelitian melibatkan pengumpulan data geografis dari Google Maps untuk membangun representasi graf berbobot dari jaringan jalan, yang terdiri dari 13 node dan 13 edge dengan densitas graf 0,166. Algoritma diimplementasikan dan diuji pada struktur graf sparse ini untuk mengidentifikasi rute optimal. Hasil penelitian menunjukkan bahwa algoritma Dijkstra berhasil mengidentifikasi jalur terpendek dengan jarak total 7,345 km melalui rute: A → B → C → E → G → I → K → L → M, yang merepresentasikan jalur via Jl. Setia Budi - Jl. Sunggal - Jl. Sri Batang Hari - Jl. Gajah Mada - Jl. K.H. Wahis Hasyim - Jl. Jend. D.I Panjaitan - Jl. Sei Babalan. Algoritma mencapai akurasi 99,3% dibandingkan dengan referensi Google Maps dan menunjukkan efisiensi komputasi dengan waktu eksekusi kurang dari 1 milidetik. Solusi ini memberikan perbaikan optimasi jarak sebesar 6,25% dibandingkan rute alternatif, menawarkan kerangka navigasi yang efektif untuk sistem transportasi urban.