Algoritma Dijkstra
- Diperkenalkan oleh
- Edsger W. Dijkstra
- Tahun
- 1956
- Jenis
- algorithm
- Keluarga
- Graph Algorithms
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Dijkstra, diperkenalkan oleh Edsger W. Dijkstra pada tahun 1956, adalah salah satu algoritma paling fundamental dalam ilmu komputer untuk menyelesaikan masalah lintasan terpendek dari sumber tunggal. Algoritma ini menemukan lintasan terpendek dari sebuah simpul awal ke semua simpul lain dalam graf berbobot dengan bobot sisi non-negatif.
Intuisi di balik metode
Algoritma ini memelihara sekumpulan simpul yang jarak terpendeknya dari sumber sudah diketahui, dan secara iteratif memperluas kumpulan ini dengan memilih simpul yang belum diproses terdekat dan memperbarui jarak ke tetangganya. Wawasan kuncinya adalah sifat serakah (greedy): setelah sebuah simpul dipilih, jaraknya dari sumber adalah final karena semua bobot sisi non-negatif, sehingga lintasan yang lebih panjang melalui simpul yang belum dikunjungi tidak mungkin lebih pendek. Ini menjamin kebenaran dan optimalitas.
Sejarah
Edsger W. Dijkstra menerbitkan algoritmanya pada tahun 1959 dalam sebuah makalah tiga halaman yang kemudian menjadi salah satu karya yang paling banyak dikutip dalam ilmu komputer. Algoritma ini muncul dari pekerjaan Dijkstra pada komputer ARMAC di Amsterdam. Selama beberapa dekade, berbagai perbaikan telah dilakukan, termasuk struktur data yang lebih baik (Fibonacci heaps yang mencapai kompleksitas O(E+VlogV)) dan varian dua arah. Algoritma ini tetap menjadi pusat protokol perutean modern seperti OSPF dalam jaringan.
Kapan digunakan
Terapkan algoritma Dijkstra saat mencari lintasan terpendek dalam graf dengan bobot sisi non-negatif. Algoritma ini ideal untuk sistem navigasi, perutean jaringan, dan masalah graf apa pun yang memerlukan lintasan optimal. Gunakan untuk lintasan terpendek dari sumber tunggal ke semua simpul. Untuk graf dengan bobot negatif, gunakan Bellman-Ford sebagai gantinya. Untuk pencarian dua arah atau panduan heuristik, pertimbangkan algoritma A*.
Batasan dan pertimbangan
- Tidak dapat menangani graf dengan bobot sisi negatif
- Menghitung lintasan terpendek ke semua simpul, bukan hanya satu tujuan (meskipun dapat berhenti lebih awal)
- Kurang efisien dibandingkan A* ketika informasi heuristik tersedia
- Membutuhkan semua simpul untuk ditemukan; tidak efisien untuk konektivitas yang sangat jarang
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Mudah dipahami dan diimplementasikan dengan jaminan kebenaran yang jelas
- Efisien dengan struktur data yang tepat: O((V+E)logV) dengan tumpukan biner (binary heap), O(V²) dengan larik (array)
- Optimal untuk graf berbobot non-negatif; membuktikan optimalitas lintasan yang dihitung
- Bekerja pada graf berarah maupun tak berarah
- Dasar untuk berbagai ekstensi dan algoritma terkait
Penerapan
- Sistem GPS dan navigasi: mencari rute terpendek untuk kendaraan dan pejalan kaki
- Protokol perutean jaringan: menentukan lintasan optimal untuk paket data dalam jaringan komputer
- Jaringan sosial: mencari lintasan koneksi terpendek antara pengguna atau pemberi pengaruh
- Pengembangan game: pencarian lintasan (pathfinding) untuk kecerdasan buatan dan pergerakan karakter non-pemain
- Perencanaan gerak robot: menghitung lintasan optimal untuk sistem robotik
- Telekomunikasi: mengoptimalkan perutean panggilan dan lintasan propagasi sinyal
Cara kerjanya
Cara kerjanya
Tetapkan jarak ke sumber sebagai nol dan semua jarak lain sebagai tak terhingga. Tandai semua simpul sebagai belum dikunjungi dan buat antrean prioritas.
Pilih simpul yang belum dikunjungi dengan jarak minimum dari sumber menggunakan antrean prioritas.
Untuk setiap tetangga dari simpul yang dipilih, jika lintasan melalui simpul yang dipilih menawarkan jarak yang lebih pendek, perbarui jarak tetangga dan tambahkan ke antrean prioritas.
Kesalahan umum
- Menggunakan algoritma pada graf dengan bobot negatif, yang menghasilkan lintasan terpendek yang salah
- Implementasi yang tidak efisien dengan operasi ekstraksi-minimum waktu linier, yang menyebabkan kinerja buruk
- Gagal memperbarui jarak dengan benar ketika tetangga dikunjungi kembali melalui lintasan yang berbeda
Pertanyaan yang sering diajukan
Mengapa algoritma Dijkstra gagal pada bobot negatif?
Algoritma ini mengasumsikan bahwa setelah sebuah simpul difinalisasi, tidak ada lintasan yang lebih pendek yang dapat ditemukan melalui simpul yang belum dikunjungi. Dengan bobot negatif, lintasan yang lebih panjang mungkin kemudian membaik ketika sisi negatif digunakan, yang melanggar asumsi ini.
Struktur data apa yang harus digunakan untuk antrean prioritas?
Tumpukan biner (binary heaps) menyediakan operasi O(logV) untuk penyisipan dan ekstraksi, menghasilkan kompleksitas total O((V+E)logV). Fibonacci heaps mencapai O(E+VlogV) tetapi memiliki faktor konstanta yang besar. Larik (arrays) bekerja dengan baik untuk graf kecil.
Bagaimana algoritma Dijkstra dapat menemukan lintasan ke satu tujuan tertentu?
Hentikan algoritma segera setelah simpul tujuan dipilih (jaraknya difinalisasi), hindari komputasi yang tidak perlu. Alternatifnya, rekonstruksi lintasan dengan memelihara penunjuk induk (parent pointers) selama eksekusi.
Bisakah algoritma Dijkstra digunakan dalam graf tak berarah?
Ya, graf tak berarah dapat direpresentasikan sebagai graf berarah dengan sisi ke kedua arah untuk setiap sisi tak berarah, masing-masing dengan bobot yang sama. Algoritma bekerja secara identik pada representasi dua arah tersebut.
Metode terkait
Sumber
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Buka referensi DOIDisalin.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Disalin.