Algoritma Dijkstra
Perencana rute Anda tahu jalan tercepat dari pintu rumah ke hampir mana saja. Inti gagasan itu adalah algoritma yang dirumuskan Edsger Dijkstra dalam sekitar dua puluh menit pada tahun 1956: meluas dari awal, dan selalu selesaikan tempat terdekat lebih dulu.
Gagasannya
Bayangkan kota-kota yang dihubungkan jalan dengan panjang berbeda. Pertanyaannya: apa jalan terpendek dari kota saya ke setiap kota lain? BFS menjawabnya jika setiap jalan dihitung sama, tetapi di sini rute dengan lebih banyak jalan bisa lebih pendek. Algoritma Dijkstra menyimpan, untuk tiap kota, jarak terpendek yang ditemukan sejauh ini, dan memperluas wilayah kota yang jaraknya sudah pasti, selalu menambahkan kota terdekat yang belum pasti.
Langkah demi langkah
Beri awal jarak 0 dan setiap simpul lain tak hingga. Masukkan awal ke antrean prioritas, yaitu antrean yang selalu memberikan simpul dengan jarak terkecil. Ambil simpul itu; jaraknya kini final. Untuk tiap tetangga yang belum final, hitung jarak lewat simpul ini: jaraknya ditambah panjang sisi. Jika itu lebih pendek dari jarak tetangga sejauh ini, turunkan jaraknya, ingat simpul ini sebagai jalan ke sana, dan masukkan tetangga ke antrean. Ini disebut merelaksasi sisi. Ulangi sampai antrean kosong, atau sampai tujuan diambil darinya.
Contoh
Ambil sisi A–B dengan panjang 4, A–C 1, B–C 2, B–D 1, C–D 5, dan D–E 3, lalu mulai dari A. Mengambil A memberi B jarak 4 dan C jarak 1. C terdekat, jadi C final di 1; lewat C, B turun ke 1 + 2 = 3 dan D mendapat 1 + 5 = 6. Sekarang B terdekat, final di 3, dan lewat B, D turun ke 3 + 1 = 4. D final di 4 dan memberi E 4 + 3 = 7. Jadi jalan terpendek dari A ke E adalah A → C → B → D → E, panjang 7, meskipun A → B → D → E memakai lebih sedikit sisi dan panjangnya 8.
Mengapa algoritma ini benar
Misalkan simpul X adalah yang terdekat dalam antrean, pada jarak d. Setiap jalan lain dari awal ke X harus keluar dari wilayah simpul final di suatu titik, dan simpul pertama yang dicapainya di luar wilayah itu ada dalam antrean, jadi sudah setidaknya sejauh d. Sisa jalannya tidak bisa membuatnya lebih pendek, karena tidak ada sisi negatif. Jadi d adalah jarak terpendek ke X. Dengan sisi negatif, argumen itu gagal; sebagai gantinya dipakai algoritma Bellman–Ford, yang merelaksasi setiap sisi berulang kali.
Sejarah dan kegunaan
Edsger W. Dijkstra merancang algoritma ini pada tahun 1956 untuk memamerkan komputer baru, ARMAC di Amsterdam, dengan mencari rute antarkota di Belanda, dan menerbitkannya pada tahun 1959. Gagasan yang sama, dengan antrean yang lebih cerdas, berjalan di perencana rute dan di protokol routing internet seperti OSPF dan IS-IS, yang menghitung jalan terpendek bagi data untuk berpindah antar-router. Pencarian A* menambahkan perkiraan jarak yang masih tersisa, sehingga bisa mengarah ke tujuan dan memeriksa lebih sedikit simpul.
Jelajahi
Buka aplikasi dan tekan Langkah. Angka di sisi adalah panjangnya, dan angka di tiap simpul adalah jaraknya sejauh ini. Simpul dalam antrean berwarna biru, simpul final hijau, dan antrean di bawah graf mencantumkannya dari yang terdekat, beserta jaraknya. Perhatikan saat jarak turun karena rute yang tampak lebih panjang ternyata lebih pendek, dan pilih tujuan untuk melihat pencarian berhenti begitu tujuan final.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu algoritma Dijkstra?
Tergantung antrean prioritasnya. Dengan daftar sederhana, O(V²) untuk V simpul; dengan binary heap, O((V + E) log V) untuk E sisi; dengan Fibonacci heap, O(E + V log V), seperti ditunjukkan Michael Fredman dan Robert Tarjan pada tahun 1984.
Bisakah algoritma Dijkstra menangani bobot sisi negatif?
Tidak. Algoritma ini menganggap jarak simpul tidak bisa membaik lagi begitu simpul itu menjadi yang terdekat dalam antrean, dan sisi negatif bisa mematahkan anggapan itu. Pakai algoritma Bellman–Ford untuk graf dengan sisi negatif.
Apakah algoritma Dijkstra menemukan jalur ke setiap simpul?
Ya. Jika dijalankan sampai akhir, algoritma ini memberikan jarak terpendek dari awal ke setiap simpul yang bisa dicapai, dan simpul-simpul yang diingat membentuk pohon jalur terpendek. Berhenti lebih awal saat tujuan final menghemat kerja jika hanya satu jalur yang dibutuhkan.
Apa hubungan algoritma Dijkstra dengan A*?
Pencarian A* adalah algoritma Dijkstra dengan petunjuk: A* mengurutkan antrean berdasarkan jarak sejauh ini ditambah perkiraan jarak yang masih tersisa, seperti jarak garis lurus di peta. Dengan perkiraan yang baik, A* menemukan jalur terpendek yang sama sambil memeriksa jauh lebih sedikit simpul.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba algoritma Dijkstra