Dijkstra's Algorithm mencari jalur terpendek dari satu node (source) ke semua node lain di weighted graph dengan bobot non-negatif.

Kalau BFS menghitung jarak di graph tanpa bobot (setiap edge = 1), Dijkstra menggeneralisasi untuk edge dengan bobot berbeda-beda (misal: jarak km antar kota, latency antar server).

Intuisi

Bayangkan kamu menyala lampu di node start, dan cahaya menyebar dengan kecepatan berbeda tergantung bobot edge. Node yang pertama kali disinari cahaya punya jarak terpendek dari start.

Ide kunci: Selalu proses node dengan jarak tentatif terkecil dulu. Setelah diproses, jaraknya sudah pasti (final).

Algoritma (dengan min-heap / priority queue)

function dijkstra(adj, start) {
  const dist = {};
  for (const node in adj) dist[node] = Infinity;
  dist[start] = 0;

  // Priority queue: [[distance, node], ...]
  // Untuk produksi, pakai min-heap. Di sini: array sederhana.
  const pq = [[0, start]];

  while (pq.length > 0) {
    // Ambil node dengan jarak terkecil
    pq.sort((a, b) => a[0] - b[0]);
    const [d, node] = pq.shift();

    if (d > dist[node]) continue; // outdated entry, skip

    // Relax tetangga
    for (const [neighbor, weight] of adj[node]) {
      const newDist = d + weight;
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }
  return dist;
}

// Graph: A→B(4), A→C(1), C→B(2), C→D(5), B→D(1)
const adj = {
  A: [["B", 4], ["C", 1]],
  B: [["D", 1]],
  C: [["B", 2], ["D", 5]],
  D: [],
};

dijkstra(adj, "A");
// { A: 0, B: 3, C: 1, D: 4 }
// A→C→B = 1+2 = 3 (bukan A→B = 4)
// A→C→B→D = 1+2+1 = 4 (bukan A→C→D = 6 atau A→B→D = 5)

Proses Relaxation

"Relax" edge (u, v, w) artinya:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Kita "merelaksasi" estimasi jarak ke v jika ternyata jalur lewat u lebih pendek.

Trace untuk graph di atas (dari A):

Final: {A:0, B:3, C:1, D:4} ✓

Kenapa Tidak Boleh Ada Edge Negatif?

Dijkstra mengasumsikan: setelah sebuah node dikeluarkan dari queue, jaraknya final. Dengan edge negatif, asumsi ini rusak — bisa saja ada jalur lain dengan edge negatif yang masih bisa memperpendek jaraknya kemudian.

Contoh masalah:

A --1--> B
A --5--> C
B --(-10)--> C

Dijkstra: proses A (d=0), relax → dist[B]=1, dist[C]=5. Proses B (d=1), relax C: 1 + (-10) = -9, update dist[C]=-9. Tapi C sudah pernah di-"finalisasi"? Nope, Dijkstra naif mungkin sudah mengeluarkan C dengan d=5 lebih dulu dalam variasi tertentu, atau pesimistiknya algoritma tidak menjamin kebenaran.

Solusi: pakai Bellman-Ford.

Dijkstra vs Bellman-Ford

Kompleksitas

• Dengan min-heap: O((V + E) log V)
• Tanpa heap (array linear scan): O(V²) — untuk dense graph kadang ini oke
• Fibonacci heap (akademik): O(E + V log V)

Kegunaan Nyata

• Google Maps / GPS: rute tercepat antar lokasi
• Network routing: OSPF protocol di internet
• Game AI: pathfinding di peta (digabung dengan A*)
• Dependency resolution: minimum cost build

A* = Dijkstra + heuristic. A* menambahkan estimasi jarak ke goal untuk mempercepat pencarian di grid/map. Dipakai di game dan robotika.

🎭 Analogi sehari-hari (lampu menyebar): Imajine kamu di kota besar, mau ke 10 lokasi dari rumah. Bayangkan rumah kamu nyalain lampu raksasa, cahayanya menyebar lewat jalan. Jalan tol = lampu cepat sampai (weight kecil). Jalan tikus = lampu lama sampai (weight besar). Lokasi yang pertama disinari = rute terpendek dari rumah. Itulah Dijkstra.

💡 Mengapa harus pakai priority queue? Tanpa PQ, scan semua belum-visit nodes setiap iterasi = O(V²). PQ ambil min instan = O(log V) per ambil. Total O((V+E) log V). Untuk 1jt nodes, beda 1 trilyun vs 20 juta operasi.

⚠️ Jebakan umum:

• Edge negatif = HASIL SALAH. Pakai Bellman-Ford
• Outdated entries di PQ — saat node sudah punya jarak lebih kecil, entry lama tetap di queue. Skip dengan if (d > dist[node]) continue
• Tidak update dist sebelum push ke PQ = duplicate processing tidak terdeteksi
• JS sort PQ tiap iterasi = O(n log n) per ambil = TLE. Pakai min-heap proper

🎯 Dijkstra vs alternatif:

• Unweighted → BFS (lebih simpel, sama O(V+E))
• Positive weights → Dijkstra (default)
• Negative weights → Bellman-Ford (handle, deteksi negative cycle)
• All-pairs → Floyd-Warshall (O(V³))
• Map / grid + heuristic available → A* (Dijkstra + heuristic)

🧪 Tebakan cepat: Google Maps bukan Dijkstra murni. Pakai variant: A* (heuristic euclid distance), graph partitioning (highway hierarchy), dan caching. Untuk skala kota beneran perlu trick massive.

TL;DR: Dijkstra = shortest path positive-weight graph dengan greedy + priority queue. O((V+E) log V). Foundation Google Maps, network routing, game pathfinding. Negative weight? Bellman-Ford.