Apa Itu Algoritme Dijkstra?
Algoritme Dijkstra adalah salah satu algoritma graf yang paling fundamental dan banyak digunakan dalam ilmu komputer dan teori graf. Dikembangkan oleh ilmuwan komputer Belanda Edsger W. Dijkstra pada tahun 1956, algoritma ini dirancang khusus untuk menemukan jalur terpendek (shortest path) antara sebuah node awal (sumber) ke semua node lain dalam sebuah graf berbobot (weighted graph).
Kunci utama dari algoritme ini adalah bahwa semua bobot tepi (weight of the edges) harus bernilai non-negatif. Jika graf mengandung bobot negatif, maka algoritme yang lebih sesuai adalah algoritme Bellman-Ford.
Prinsip Kerja Algoritme Dijkstra
Dijkstra bekerja dengan pendekatan "greedy", yaitu selalu memilih solusi yang terlihat paling optimal pada saat itu. Algoritma ini mempertahankan sekumpulan node yang sudah dikunjungi (diketahui jarak terpendeknya dari sumber) dan secara iteratif memperbarui perkiraan jarak ke node yang belum dikunjungi.
Langkah-langkah Utama:
- Inisialisasi: Tetapkan jarak dari node sumber ke dirinya sendiri adalah 0, dan jarak ke semua node lain adalah tak terhingga (infinity).
- Penandaan: Semua node ditandai belum dikunjungi, kecuali node sumber.
- Iterasi: Pilih node U yang belum dikunjungi dan memiliki jarak terpendek saat ini dari sumber.
- Relaksasi (Relaxation): Untuk setiap tetangga V dari node U, hitung jarak baru melalui U. Jika jarak baru ini lebih pendek daripada jarak V yang tercatat saat ini, perbarui jarak V dan catat U sebagai prekursornya.
- Penandaan Selesai: Tandai node U sebagai telah dikunjungi.
- Pengulangan: Ulangi langkah 3 hingga 5 sampai semua node telah dikunjungi, atau sampai node tujuan telah dikunjungi.
Penggunaan struktur data Priority Queue (Antrian Prioritas) sangat penting untuk efisiensi algoritme ini, karena memungkinkan pemilihan node dengan jarak terpendek berikutnya secara cepat.
Contoh Implementasi Konseptual
Misalkan kita ingin mencari jalur terpendek dari Node A ke Node D pada graf di atas. Bobot merepresentasikan waktu atau biaya perjalanan.
- Mulai di A: Jarak A=0, B=∞, C=∞, D=∞, E=∞.
- Pilih A (0): Perbarui tetangga (B dan E). Jarak B menjadi 5, E menjadi 10.
- Pilih B (5): Perbarui tetangga (C). Jarak C dari A-B-C adalah 5+3 = 8. (Jarak C saat ini adalah ∞).
- Pilih C (8): Perbarui tetangga (D dan E).
- Ke D: 8 + 2 = 10. Jarak D menjadi 10.
- Ke E: 8 + 1 = 9. Karena 9 < 10 (jarak E sebelumnya), jarak E diperbarui menjadi 9.
- Pilih E (9): (Dalam contoh ini E tidak punya tetangga yang belum dikunjungi yang relevan atau perhitungannya tidak membaik).
- Pilih D (10): D sudah final.
Jalur terpendek dari A ke D adalah A → B → C → D dengan total bobot 10.
Kompleksitas dan Kegunaan
Kompleksitas Waktu
Kompleksitas waktu algoritme Dijkstra sangat bergantung pada struktur data yang digunakan untuk mengimplementasikan antrian prioritas:
- Jika menggunakan Array/List Biasa: O(V²), di mana V adalah jumlah node (vertices).
- Jika menggunakan Binary Heap (Antrian Prioritas): O((V + E) log V), di mana E adalah jumlah tepi (edges). Ini adalah implementasi yang paling umum dan efisien untuk graf jarang (sparse graphs).
Aplikasi Nyata
Algoritme Dijkstra memiliki banyak aplikasi praktis:
- Sistem Navigasi GPS: Mencari rute tercepat antara dua lokasi di peta jalan.
- Jaringan Komputer: Protokol perutean seperti OSPF (Open Shortest Path First) menggunakan prinsip Dijkstra untuk menentukan jalur data tercepat.
- Perencanaan Rute Logistik: Mengoptimalkan pengiriman barang.
Meskipun sangat kuat untuk graf dengan bobot non-negatif, penting untuk selalu mengingat batasan ini saat memilih algoritme pencarian jalur terpendek.