Shortest Path mencari jalur terpendek antar node di weighted graph. Algoritma paling terkenal: Dijkstra.

Dijkstra's Algorithm:

1. Set jarak semua node = ∞, kecuali start = 0
2. Ambil node dengan jarak terkecil yang belum dikunjungi
3. Update jarak tetangganya jika ditemukan jalur lebih pendek
4. Ulangi sampai semua node dikunjungi

Kompleksitas: O((V + E) log V) dengan priority queue

function dijkstra(graph, start) {
  const distances = new Map();
  const previous = new Map();
  const visited = new Set();

  // Inisialisasi
  for (const vertex of graph.adjacencyList.keys()) {
    distances.set(vertex, Infinity);
  }
  distances.set(start, 0);

  while (visited.size < graph.adjacencyList.size) {
    // Ambil node belum dikunjungi dengan jarak terkecil
    let current = null;
    let minDist = Infinity;
    for (const [v, d] of distances) {
      if (!visited.has(v) && d < minDist) {
        current = v;
        minDist = d;
      }
    }
    if (!current) break;

    visited.add(current);

    // Update tetangga
    for (const { node, weight } of graph.adjacencyList.get(current)) {
      const newDist = distances.get(current) + weight;
      if (newDist < distances.get(node)) {
        distances.set(node, newDist);
        previous.set(node, current);
      }
    }
  }

  return { distances, previous };
}

Kegunaan nyata:

• Google Maps — rute tercepat
• Network routing — jalur data tercepat
• Game pathfinding — NPC mencari jalan
• Social network — degree of separation

🎭 Analogi sehari-hari: Kamu dapet undangan kondangan di kota lain. Lihat peta, ada banyak rute (jalan tol, jalan biasa, jalan tikus). Setiap jalan punya estimasi waktu (weight). Dijkstra = cara sistematis cari rute tercepat: cek opsi terdekat dulu, update kalau ketemu jalan pintas, jangan balik ke jalan yang sudah dilewati.

💡 Kenapa Dijkstra tidak bisa untuk negative weight? Algoritma asumsi: setelah node di-visit, jaraknya pasti final. Tapi kalau ada edge negative, jalur lebih jauh lewat negative bisa beneran lebih pendek total. Dijkstra gak ngecek lagi → salah. Pakai Bellman-Ford atau SPFA untuk negative weight.

⚠️ Jebakan umum:

• Tanpa priority queue = O(V²). Pakai min-heap → O((V+E) log V)
• Negative weight = HASIL SALAH. Cek dulu, atau pakai Bellman-Ford
• Disconnected graph = node tidak terjangkau tetap Infinity, perlu handle
• Graph dengan banyak edge = adjacency matrix lebih cocok kadang

🎯 Pilih algoritma shortest path:

• Unweighted graph → BFS (O(V+E))
• Positive weights → Dijkstra (O((V+E) log V))
• Negative weights → Bellman-Ford (O(VE))
• All-pairs shortest path → Floyd-Warshall (O(V³))
• A (heuristic available)* → A search* (Dijkstra + heuristic)

🧪 Tebakan cepat: Google Maps pakai Dijkstra murni? Hampir tidak. Pakai variant + heuristic (A*), partitioning, dan caching. Untuk skala kota beneran, optimization heavy.

TL;DR: Dijkstra = shortest path positive-weight graph dengan greedy + priority queue. Foundation banyak sistem navigasi. Untuk negative weight, pakai Bellman-Ford.