Shortest path (jalur terpendek) adalah rute paling murah dari satu node ke node lain di sebuah graph. Di graph berbobot, tiap edge punya angka (bobot), misalnya jarak dalam kilometer atau menit perjalanan, dan panjang sebuah jalur adalah jumlah bobot edge-nya. Mirip aplikasi peta yang memilih rute tercepat dari sekian banyak jalan.
🧪 Tebakan cepat: dari A ke B ada jalan langsung berbobot 4, dan ada jalan memutar: A ke C (2), lalu C ke B (1). Mana yang lebih pendek? Tebak dulu, jawabannya ada di bagian "Dijkstra: lanjut dari node termurah".
Dijkstra: lanjut dari node termurah
Algoritma Dijkstra mencari jarak terpendek dari satu node awal ke semua node lain. Caranya:
- Jarak node awal 0, node lain ∞ (Infinity, artinya belum ada jalur yang ketemu).
- Ambil node yang belum final dengan jarak terkecil. Jaraknya sekarang final.
- Cek tiap edge yang keluar dari node itu. Kalau jarak node + bobot lebih kecil dari jarak tetangga yang tercatat, ganti. Langkah ini disebut relaksasi.
- Ulangi sampai gak ada node yang tersisa.
Ini jalannya di graph milik Lab, mulai dari A:
| Ambil | Edge yang dicek | Jarak A, B, C, D, E sesudahnya |
|---|---|---|
| A (0) | A ke B: 0 + 4, A ke C: 0 + 2 | 0, 4, 2, ∞, ∞ |
| C (2) | C ke B: 2 + 1 = 3, lebih kecil dari 4. C ke E: 2 + 5 | 0, 3, 2, ∞, 7 |
| B (3) | B ke D: 3 + 3 | 0, 3, 2, 6, 7 |
| D (6) | D ke E: 6 + 1 = 7, gak lebih kecil dari 7 | 0, 3, 2, 6, 7 |
| E (7) | gak ada edge keluar | selesai |
Jarak B turun dari 4 ke 3: jalan memutar lewat C lebih pendek. Itu jawaban tebakan tadi.
const graph = {
A: { B: 4, C: 2 },
B: { D: 3 },
C: { B: 1, E: 5 },
D: { E: 1 },
E: {},
};
function dijkstra(graph, start) {
const dist = {};
for (const node in graph) dist[node] = Infinity;
dist[start] = 0;
const done = new Set();
while (true) {
// ambil node termurah yang belum final
let node = null;
for (const n in dist) {
if (!done.has(n) && dist[n] < Infinity && (node === null || dist[n] < dist[node])) {
node = n;
}
}
if (node === null) break;
done.add(node);
// relaksasi: cek tiap tetangga
for (const [next, w] of Object.entries(graph[node])) {
if (dist[node] + w < dist[next]) {
dist[next] = dist[node] + w;
}
}
}
return dist;
}
console.log(dijkstra(graph, "A")); // { A: 0, B: 3, C: 2, D: 6, E: 7 }
A: { B: 4, C: 2 }artinya dari A ada edge ke B (bobot 4) dan ke C (bobot 2). Edge-nya satu arah.distmenyimpan jarak terbaik sejauh ini, dandoneadalah Set berisi node yang jaraknya sudah final.- Loop pertama di dalam
whilemencari node termurah yang belum final. Kalau gak ada lagi,break. Object.entries(graph[node])memberi pasangan[tetangga, bobot]. Kalaudist[node] + wlebih kecil, jarak tetangga diganti.
Bobot negatif bikin Dijkstra salah
Dijkstra menganggap node yang sudah final gak mungkin jadi lebih murah lagi. Itu benar selama semua bobot 0 atau lebih. Dengan bobot negatif, jalur yang lebih panjang bisa jadi lebih murah belakangan, padahal node-nya keburu final dan node sesudahnya gak dicek ulang. Contoh: A ke B 2, A ke C 5, C ke B -4, B ke D 1. Dijkstra menjawab D = 3, padahal A, C, B, D totalnya 2. Kalau ada bobot negatif, pakai algoritma lain, misalnya Bellman-Ford.
Graph tanpa bobot: cukup BFS
Kalau edge-nya gak punya bobot, tiap edge dihitung 1 langkah, jadi jalur terpendek adalah jalur dengan edge paling sedikit. BFS (breadth-first search) memakai antrean dan mengunjungi node lapis demi lapis: semua yang 1 langkah dulu, lalu 2 langkah, dan seterusnya. Jadi saat sebuah node pertama kali ketemu, jaraknya pasti yang terpendek.
| Ambil dari antrean | Tetangga baru dan jaraknya | Antrean sesudahnya |
|---|---|---|
| A | B = 1, C = 1 | B, C |
| B | D = 2 | C, D |
| C | (D sudah punya jarak) | D |
| D | gak ada | kosong, selesai |
const peta = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "D"],
D: ["B", "C"],
};
function jarakBFS(graph, start) {
const jarak = {};
jarak[start] = 0;
const antrean = [start];
while (antrean.length > 0) {
const node = antrean.shift();
for (const tetangga of graph[node]) {
if (jarak[tetangga] === undefined) {
jarak[tetangga] = jarak[node] + 1;
antrean.push(tetangga);
}
}
}
return jarak;
}
console.log(jarakBFS(peta, "A")); // { A: 0, B: 1, C: 1, D: 2 }
Tetangga yang sudah punya jarak dilewati, jadi tiap node masuk antrean sekali. Kalau yang dicari jarak ke satu tujuan saja: tujuan sama dengan start berarti 0, begitu tujuan dapat jarak langsung return jaraknya, dan kalau antrean habis tanpa ketemu tujuan, return -1 sebagai tanda gak ada jalur.
⚠️ Jebakan yang sering ketemu
- Menandai node terlambat. Beri jarak waktu tetangga masuk antrean, bukan waktu diambil. Kalau terlambat, node yang sama bisa masuk antrean berkali-kali.
- Lupa node yang gak terjangkau. Di Dijkstra jaraknya tetap
Infinity, di BFS tujuannya gak pernah dapat jarak. Cek dulu sebelum memakai angkanya. - Dijkstra untuk graph tanpa bobot. Hasilnya benar, tapi BFS lebih sederhana dan lebih cepat.
💡 Seberapa cepat? Versi di atas mengecek semua node tiap mencari yang termurah, jadi untuk V node kira-kira V × V langkah, O(V²): node-nya dua kali lipat, waktunya kira-kira empat kali lipat. Dengan heap (antrean prioritas) Dijkstra jadi O((V + E) log V), E = jumlah edge. BFS cukup O(V + E): tiap node dan edge disentuh sekali.
TL;DR: Dijkstra mencari jarak terpendek di graph berbobot: mulai dari 0 dan ∞, ambil node termurah yang belum final, lalu perbarui jarak tetangganya (relaksasi) sampai semua final. Dijkstra butuh bobot yang gak negatif; untuk bobot negatif pakai Bellman-Ford. Di graph tanpa bobot, BFS dengan antrean sudah memberi jumlah edge paling sedikit: start ke dirinya sendiri 0, tujuan yang gak terjangkau -1.
