STUDI PERBANDINGAN EFISIENSI ALGORITMA DIJKSTRA DAN GREEDY PADA PENCARIAN JALUR TERPENDEK DALAM GRAF DINAMIS

Abstrak

Studi ini bertujuan membandingkan efisiensi dan akurasi algoritma Dijkstra dan Greedy dalam pencarian jalur terpendek pada grafik dinamis. Grafik dinamis, yang bobot tepinya berubah secara real-time, menuntut algoritma yang adaptif dan efisien (Demetrescu & Italiano, 2004). Eksperimen dilakukan pada grafik sintetis dengan berbagai ukuran dan tingkat perubahan bobot tepi. Hasil menunjukkan bahwa algoritma Greedy berjalan lebih cepat pada grafik kecil hingga sedang tetapi sering kali menghasilkan jalur yang kurang optimal (Cormen et al., 2009). Sebaliknya, Dijkstra secara konsisten menghasilkan jalur terpendek yang optimal, meskipun dengan waktu eksekusi yang lebih lama, terutama pada grafik besar atau grafik dengan perubahan bobot yang signifikan (Dijkstra, 1959; Zhan & Noon, 1996). Studi ini menyarankan pengembangan algoritma hibrida sebagai arah penelitian masa depan untuk menggabungkan kecepatan Greedy dengan akurasi Dijkstra (Likhachev et al., 2005). Pekerjaan ini sangat relevan untuk aplikasi dunia nyata seperti navigasi kendaraan otonom dan robotika (Thrun et al., 2005).

This study is intended to compare the efficiency and accuracy of Dijkstra and Greedy algorithms in shortest path search on dynamic graphs. Dynamic graphs, whose edge weights change in real-time, demand adaptive and efficient algorithms (Demetrescu & Italiano, 2004). Experiments were conducted on synthetic graphs of varying sizes and edge weight change levels. Results indicate that the Greedy algorithm executes faster on small to medium graphs but often yields suboptimal paths (Cormen et al., 2009). In contrast, Dijkstra consistently produces optimal shortest paths, albeit with longer execution times, especially in large graphs or those with significant weight changes (Dijkstra, 1959; Zhan & Noon, 1996). The study suggests hybrid algorithm development as a future research direction to combine Greedy's speed with Dijkstra's accuracy (Likhachev et al., 2005). This work is highly relevant for real-world applications such as autonomous vehicle navigation and robotics (Thrun et al., 2005).