Algoritma Dijkstra menemukan jalur terpendek dari satu simpul ke simpul lain dalam graf berbobot non-negatif. Untuk menerapkannya, kamu perlu memahami cara kerja, memilih struktur data yang tepat, dan mengimplementasikannya dalam kode. Panduan ini memandu kamu melalui langkah-langkah tersebut.
Apa Itu Algoritma Dijkstra?
Dijkstra adalah algoritma pencarian jalur terpendek yang bekerja pada graf dengan bobot sisi non-negatif. Algoritma ini diperkenalkan oleh Edsger W. Dijkstra pada 1956. Tujuannya adalah menemukan rute dengan total bobot terkecil dari simpul sumber ke semua simpul lain atau ke simpul tujuan tertentu.
Algoritma ini banyak dipakai dalam aplikasi navigasi, jaringan komputer, dan sistem rekomendasi. Dengan memahami cara kerjanya, kamu bisa menyelesaikan masalah optimasi yang melibatkan graf.
Konsep Dasar yang Perlu Dipahami
Sebelum menulis kode, pahami beberapa istilah dalam teori graf. Graf terdiri dari simpul (vertex) dan sisi (edge). Setiap sisi memiliki bobot yang merepresentasikan biaya perjalanan, jarak, atau waktu. Algoritma Dijkstra mencari jalur dengan total bobot minimum dari simpul sumber ke simpul tujuan.
Ada dua himpunan simpul yang digunakan: simpul yang sudah dikunjungi (dengan jarak terpendek final) dan simpul yang belum dikunjungi. Algoritma ini secara iteratif memilih simpul dengan jarak terpendek dari himpunan yang belum dikunjungi, lalu memperbarui jarak ke simpul tetangganya.
Langkah-Langkah Menerapkan Algoritma Dijkstra
Berikut adalah langkah-langkah sistematis untuk menerapkan algoritma Dijkstra:
1. Representasi Graf
Pilih struktur data yang sesuai. Graf dapat direpresentasikan dengan matriks ketetanggaan atau daftar ketetanggaan. Untuk graf jarang, daftar ketetanggaan lebih efisien karena hanya menyimpan sisi yang ada.
2. Inisialisasi Jarak
Buat array atau kamus untuk menyimpan jarak terpendek dari sumber ke setiap simpul. Inisialisasi jarak sumber ke 0 dan simpul lainnya ke tak hingga. Simpan juga simpul sebelumnya untuk merekonstruksi jalur.
3. Pilih Simpul dengan Jarak Terkecil
Gunakan priority queue (heap) untuk memilih simpul yang belum dikunjungi dengan jarak terkecil. Ini adalah kunci efisiensi algoritma. Dengan heap, kompleksitas waktu menjadi O((V + E) log V).
4. Perbarui Jarak Tetangga
Untuk setiap tetangga dari simpul yang dipilih, hitung jarak baru melalui simpul tersebut. Jika jarak baru lebih kecil dari jarak yang tersimpan, perbarui jarak dan catat simpul sebelumnya.
5. Ulangi Hingga Semua Simpul Dikunjungi
Lanjutkan proses hingga priority queue kosong atau jarak ke simpul tujuan sudah final. Pada akhirnya, array jarak akan berisi jarak terpendek dari sumber ke semua simpul.
Implementasi dalam Python
Berikut adalah contoh implementasi algoritma Dijkstra dalam Python menggunakan daftar ketetanggaan dan heapq:
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
pq = [(0, start)]
previous = {node: None for node in graph}
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current_node
heapq.heappush(pq, (distance, neighbor))
return distances, previous
# Contoh penggunaan
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))
Kode di atas mengembalikan jarak terpendek dari simpul ‘A’ ke semua simpul lain, serta simpul sebelumnya untuk setiap simpul. Kamu bisa merekonstruksi jalur dengan menelusuri kembali dari tujuan ke sumber.
Tips dan Kesalahan Umum
Beberapa hal yang perlu diperhatikan saat menerapkan algoritma Dijkstra:
- Pastikan semua bobot sisi non-negatif. Jika ada bobot negatif, gunakan algoritma Bellman-Ford.
- Gunakan priority queue untuk efisiensi, bukan pencarian linear.
- Perhatikan representasi graf: daftar ketetanggaan lebih baik untuk graf jarang.
- Untuk merekonstruksi jalur, simpan simpul sebelumnya setiap kali jarak diperbarui.
Jika kamu ingin memperdalam pemahaman tentang efisiensi algoritma, baca Big O Notation: Cara Mengukur Efisiensi Algoritma. Untuk latihan soal harian, kunjungi Cara Melatih Logika Algoritma dengan Latihan Soal Harian.
Dalam pengembangan aplikasi nyata, pemahaman algoritma Dijkstra sering dikombinasikan dengan riset pengguna untuk desain antarmuka, seperti yang dijelaskan dalam artikel Membandingkan Tiga Metode Riset Pengguna untuk Desain Antarmuka. Selain itu, jika kamu bekerja dengan antarmuka web, teknik animasi sederhana dapat meningkatkan pengalaman pengguna; lihat Tips jQuery untuk Pemula: Pola Animasi Sederhana agar Halaman Tidak.
Ringkasan
Menerapkan algoritma Dijkstra memerlukan pemahaman tentang graf, inisialisasi jarak, penggunaan priority queue, dan pembaruan jarak tetangga. Dengan mengikuti langkah-langkah di atas dan berlatih dengan contoh kode, kamu akan mampu mengimplementasikan algoritma ini untuk berbagai masalah pencarian jalur terpendek.
Pertanyaan yang Sering Diajukan
Apakah algoritma Dijkstra bisa digunakan untuk graf dengan bobot negatif?
Tidak, algoritma Dijkstra mengasumsikan semua bobot sisi non-negatif. Untuk graf dengan bobot negatif, gunakan algoritma Bellman-Ford.
Bagaimana cara merekonstruksi jalur terpendek setelah menjalankan Dijkstra?
Simpan simpul sebelumnya (previous node) setiap kali jarak diperbarui. Setelah algoritma selesai, telusuri kembali dari simpul tujuan ke simpul sumber menggunakan array previous.
Apa kompleksitas waktu algoritma Dijkstra?
Dengan implementasi priority queue (heap), kompleksitas waktunya adalah O((V + E) log V), di mana V adalah jumlah simpul dan E adalah jumlah sisi.