Algoritma Dijkstra mencari jarak terpendek dari satu node ke semua node lain di graph berbobot. Graph-nya kota (node) yang disambung jalan (edge), dan bobot adalah angka di tiap jalan, misalnya panjangnya dalam km. BFS cuma menghitung jumlah jalan; Dijkstra menjumlahkan panjangnya, mirip aplikasi peta yang mencari rute terpendek dari rumahmu. Syaratnya satu: gak boleh ada bobot negatif.
🧪 Tebakan cepat: dari A ke B ada jalan langsung 4 km. Ada juga jalan memutar: A ke C 2 km, lalu C ke B 1 km. Mana yang lebih pendek? Tebak dulu, jawabannya ada di bagian "Ambil yang terdekat, lalu cek jalannya".
Ambil yang terdekat, lalu cek jalannya
Ada lima kota, A sampai E, dengan jalan dua arah: A-B 4 km, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, dan D-E 2. Dijkstra mencatat dist, jarak terpendek sejauh ini dari A, lalu mengulang dua langkah:
- Ambil kota yang belum selesai dengan
distterkecil. Jaraknya sekarang final. - Cek tiap jalan dari kota itu. Kalau lewat sini lebih pendek dari jarak yang tercatat (atau belum ada catatan), ganti. Langkah ini disebut relaksasi.
| Langkah | Ambil (final) | Yang berubah | dist sesudahnya |
|---|---|---|---|
| 1 | A (0) | B: 0 + 4 = 4, C: 0 + 2 = 2 | A 0, B 4, C 2 |
| 2 | C (2) | B: 2 + 1 = 3, lebih pendek dari 4. D: 2 + 8 = 10. E: 2 + 10 = 12 | B 3, D 10, E 12 |
| 3 | B (3) | D: 3 + 5 = 8, lebih pendek dari 10 | D 8 |
| 4 | D (8) | E: 8 + 2 = 10, lebih pendek dari 12 | E 10 |
| 5 | E (10) | (gak ada) | selesai |
Jarak B turun dari 4 jadi 3: jalan memutar lewat C lebih pendek. Itu jawaban tebakannya.
const graph = {
A: [["B", 4], ["C", 2]],
B: [["A", 4], ["C", 1], ["D", 5]],
C: [["A", 2], ["B", 1], ["D", 8], ["E", 10]],
D: [["B", 5], ["C", 8], ["E", 2]],
E: [["C", 10], ["D", 2]],
};
function dijkstra(graph, start) {
const dist = {};
dist[start] = 0;
const done = new Set();
while (true) {
let u = null; // kota belum selesai dengan jarak terkecil
for (const node in dist) {
if (!done.has(node) && (u === null || dist[node] < dist[u])) u = node;
}
if (u === null) break; // semua kota yang terjangkau sudah selesai
done.add(u); // jarak u sekarang final
for (const [v, w] of graph[u]) {
const newDist = dist[u] + w;
if (dist[v] === undefined || newDist < dist[v]) dist[v] = newDist; // relaksasi
}
}
return dist;
}
console.log(dijkstra(graph, "A")); // { A: 0, B: 3, C: 2, D: 8, E: 10 }
graph[u]berisi pasangan[tetangga, bobot].for (const [v, w] of graph[u])membongkar tiap pasangan:vkota tetangga,wpanjang jalannya. Jalan satu arah cukup dicatat di daftar kota asalnya.distmulai cuma berisistart, jaraknya 0. Kota lain baru masuk begitu ada jalan yang mencapainya, jadi kota yang gak bisa dicapai gak pernah ada di hasil.doneadalahSetberisi kota yang jaraknya sudah final.for (const node in dist)menyisir kuncidistuntuk mencari jarak terkecil yang belum selesai.- Relaksasi: kota yang belum punya jarak langsung diisi, yang sudah punya cuma diganti kalau
newDistlebih kecil. while (true)berhenti lewatbreakbegitu gak ada lagi kota yang belum selesai.
Kenapa bobot negatif dilarang
Dijkstra berjanji: kota yang diambil, yang jaraknya terkecil di antara yang belum selesai, sudah final. Janji itu benar karena jalan lain ke kota itu pasti lewat kota yang jaraknya lebih besar, dan menambah bobot yang gak negatif cuma bikin makin panjang. Kalau ada bobot negatif, jalan memutar bisa jadi lebih pendek belakangan, padahal kotanya sudah dianggap final, jadi hasilnya bisa salah. Untuk graph dengan bobot negatif, pakai algoritma Bellman-Ford.
Kecepatan dan pilihan lain
Kode di atas menyisir semua kota tiap kali mencari yang terdekat. Untuk V kota itu sekitar V × V langkah, O(V²): kota dua kali lipat, kerjanya kira-kira empat kali lipat. Cukup untuk graph kecil. Untuk graph besar, kota terdekat diambil dari min-heap (priority queue), struktur data yang memberi isi terkecil dengan cepat: O((V + E) log V), dengan E jumlah jalan. log V itu kecil, untuk 1.000 kota sekitar 10.
Pilih algoritmanya dari bobotnya: semua jalan dihitung sama, pakai BFS. Bobot beda-beda dan gak ada yang negatif, pakai Dijkstra. Ada bobot negatif, pakai Bellman-Ford.
⚠️ Jebakan yang sering ketemu
- Menganggap jarak pertama sudah final. B pertama kali dapat 4, lalu turun jadi 3. Jarak baru final saat kotanya diambil sebagai yang terkecil.
- Memakai BFS di graph berbobot. BFS memilih jalan paling sedikit: A-B-D, 2 jalan, 9 km. Dijkstra memilih yang paling pendek: A-C-B-D, 3 jalan, 8 km.
- Mengisi semua kota dengan
Infinitydi awal. Cara ini (yang dipakai Lab) juga menghitung jarak dengan benar, tapi kota yang gak terjangkau ikut muncul di hasil sebagaiInfinity. Kalau kota itu harus gak ada di hasil, masukkan kota kedisthanya saat ada jalan yang mencapainya.
TL;DR: Dijkstra mencari jarak terpendek dari satu kota ke semua kota lain di graph berbobot tanpa bobot negatif. Ulangi: ambil kota belum selesai dengan dist terkecil (jaraknya final), lalu relaksasi tiap jalannya: kalau dist[u] + w lebih kecil dari dist[v] (atau dist[v] belum ada), ganti. Jalan memutar bisa lebih pendek dari jalan langsung. Bobot negatif merusak janji "yang diambil sudah final", jadi pakai Bellman-Ford. Dengan sisir biasa O(V²), dengan min-heap O((V + E) log V).
