Algoritma Dijkstra dan A*: Mencari Rute Terpendek

Algoritma Dijkstra dan A*: Mencari Rute Terpendek

Algoritma Dijkstra dan A*: Mencari Rute Terpendek
6 menit baca

Dijkstra dan A* (A-star) adalah dua algoritma yang paling dikenal untuk mencari rute terpendek pada graf berbobot, misalnya jaringan jalan. Keduanya sering dipakai pada aplikasi navigasi, game, dan penentuan rute pengiriman.

Algoritma Dijkstra

Algoritma ini dikembangkan oleh Edsger W. Dijkstra pada 1956 (dipublikasikan 1959). Dijkstra mencari jarak terpendek dari satu simpul asal ke semua simpul lain, dengan syarat bobot sisi tidak boleh negatif.

Langkah-langkah

  • Beri jarak 0 pada simpul asal dan tak hingga pada simpul lain. Semua simpul ditandai belum dikunjungi.

  • Pilih simpul belum dikunjungi dengan jarak sementara terkecil, lalu tandai sebagai dikunjungi.

  • Untuk setiap tetangganya, hitung jarak baru melalui simpul ini. Jika lebih kecil dari jarak sementara, perbarui jarak dan catat simpul pendahulunya.

  • Ulangi sampai simpul tujuan dikunjungi atau semua simpul selesai diproses.

  • Telusuri pendahulu dari tujuan ke asal untuk mendapatkan rutenya.

Contoh Dijkstra

Graf dengan sisi: A-B = 4, A-C = 2, C-B = 1, B-D = 5, C-D = 8. Cari rute terpendek dari A ke D.

  • Mulai: A = 0. Dari A: B = 4, C = 2.

  • Pilih C (2). Lewat C: B = 2 + 1 = 3 (lebih kecil dari 4, jadi diperbarui), D = 2 + 8 = 10.

  • Pilih B (3). Lewat B: D = 3 + 5 = 8 (lebih kecil dari 10, diperbarui).

  • Pilih D (8), selesai.

Rute terpendek adalah A → C → B → D dengan total jarak 8.

Algoritma A* (A-star)

A* diperkenalkan oleh Hart, Nilsson, dan Raphael pada 1968. Algoritma ini mengembangkan Dijkstra dengan menambahkan heuristik agar pencarian terarah ke tujuan. Setiap simpul dinilai dengan:

f(n) = g(n) + h(n)

  • g(n): biaya sebenarnya dari simpul asal ke simpul n.

  • h(n): perkiraan biaya dari n ke tujuan, misalnya jarak garis lurus (Euclidean) atau jarak Manhattan pada grid.

A* selalu memperluas simpul dengan f(n) terkecil, memakai daftar open (kandidat) dan closed (sudah diperiksa). Agar hasilnya optimal, heuristik harus admissible, yaitu tidak pernah melebihi biaya sebenarnya ke tujuan. Jika heuristik juga konsisten, simpul tidak perlu diperiksa ulang.

Perbedaan Dijkstra dan A*

  • Dijkstra memperluas simpul hanya berdasarkan g(n) sehingga menyebar ke segala arah. A* memakai g(n) + h(n) sehingga lebih terarah ke tujuan.

  • Dijkstra menghasilkan jarak ke semua simpul, A* fokus pada satu pasangan asal dan tujuan.

  • Jika h(n) = 0 untuk semua simpul, A* berperilaku sama seperti Dijkstra.

  • A* umumnya memeriksa lebih sedikit simpul jika heuristiknya baik, tetapi butuh heuristik yang sesuai.

Kelebihan dan kekurangan

  • Dijkstra: pasti optimal untuk bobot non-negatif dan mudah diimplementasikan, tetapi bisa lambat pada graf besar karena menjelajah ke segala arah. Dengan priority queue, kompleksitasnya sekitar O((V + E) log V).

  • A*: lebih cepat jika heuristik baik dan optimal jika heuristik admissible, tetapi membutuhkan memori lebih besar dan kualitasnya bergantung pada desain heuristik.

  • Keduanya tidak menangani bobot negatif (gunakan Bellman-Ford untuk itu).

Penerapan

Kedua algoritma dipakai untuk navigasi peta, pathfinding pada game, routing jaringan, dan optimasi rute logistik. Untuk skripsi, kamu dapat membandingkan jumlah simpul yang diperiksa dan waktu eksekusi keduanya pada peta yang sama.

Kesimpulan

Dijkstra cocok untuk menemukan jarak terpendek ke banyak tujuan, sedangkan A* lebih efisien untuk satu tujuan dengan heuristik yang baik. Pilih sesuai kebutuhan dan jelaskan heuristik yang digunakan.

Bagikan:

Rekomendasi untuk Anda