En Kısa Yol (Ağırlıklı)

Nasıl düşünülür

Kenarların ağırlığı olduğunda BFS (hop sayan) en kısa yolu vermez, iki hopluk ucuz kenar yolu, tek hopluk pahalı kenarı geçebilir. Dijkstra iş atıdır: dist[] dizisi ve mesafeye göre min-öncelik kuyruğu tut. En yakın ziyaret edilmemiş düğümü pop et, kenarlarını gevşet (eğer dist[u] + w < dist[v] ise dist[v]’i güncelle ve push). Her düğüm ilk pop edildiğinde kesinleşir, tekrar ziyaret gerekmez.

Kısıt: Dijkstra negatif olmayan ağırlık gerektirir. Negatif kenar, “kesinleşmiş” bir düğümün mesafesini pop sonrası düşürebilir ve greedy değişmezi bozar. Negatif kenarlar için (veya negatif döngü tespiti için) Bellman-Ford: her kenarı V-1 kez gevşet; V’inci geçiş hâlâ gevşetirse negatif döngü vardır.

Şablon şekilleri

Şekil	Temel hamle	Örnek
Dijkstra	Mesafeye min-heap; pop’ta gevşet	LC 743, LC 1976
Dijkstra + durum	Durum = (düğüm, ek boyut); bileşik mesafeli heap	LC 787 (k-durak), LC 2045
Cevapta ikili arama + BFS	Eşikte fizibilite kontrolü	LC 1631
Bellman-Ford	Tüm kenarları V-1 kez gevşet	(negatif kenar olduğunda)

Karmaşıklık temeli

İkili heap’li Dijkstra: O((V + E) log V) zaman, O(V) alan. Bellman-Ford: O(VE) zaman, O(V) alan. Yoğun graf için heapsiz O(V²) Dijkstra daha basit ve rekabetçi olabilir.

Şablondan probleme

1. Ağırlıkların negatif olmadığını doğrula; değilse Bellman-Ford’a geç.
2. (komşu, ağırlık) çiftlerinden komşuluk listesi kur.
3. dist[source] = 0, (0, source) push; diğerleri Infinity.
4. Min’i pop et; stale ise atla (mesafe uyumsuz); komşuları gevşet.
5. Döngü sonunda dist[dest] cevaptır, hâlâ Infinity ise -1 (ulaşılamaz).
6. Problem kısıt ekliyorsa (k-durak, indirim), algoritmayı değil durumu genişlet.

/**
 * Shortest path template: Dijkstra from a source over an adjacency list.
 *
 * NOTE: This uses `pq.sort + shift` as a toy priority queue for readability.
 * In interviews / production, use a binary heap (O((V+E) log V)); this version
 * is O(V² log V) due to the per-step sort. Algorithm and logic are identical.
 */

export function dijkstra(
  n: number, edges: [number, number, number][], source: number,
): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, w] of edges) {
    adj[a]!.push([b, w]);
    adj[b]!.push([a, w]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  dist[source] = 0;

  const pq: [number, number][] = [[0, source]];
  while (pq.length) {
    // Toy PQ: sort + shift. Replace with a binary heap for O((V+E) log V).
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (dist[u]! + w < dist[v]!) {
        dist[v] = dist[u]! + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  return dist;
}

/**
 * Shortest path template: Dijkstra from a source over an adjacency list.
 *
 * NOTE: This uses `pq.sort + shift` as a toy priority queue for readability.
 * In interviews / production, use a binary heap (O((V+E) log V)); this version
 * is O(V² log V) due to the per-step sort. Algorithm and logic are identical.
 */

export function dijkstra(
  n: number, edges: [number, number, number][], source: number,
): number[] {
  const adj: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, w] of edges) {
    adj[a]!.push([b, w]);
    adj[b]!.push([a, w]);
  }
  const dist = new Array<number>(n).fill(Infinity);
  dist[source] = 0;

  const pq: [number, number][] = [[0, source]];
  while (pq.length) {
    // Toy PQ: sort + shift. Replace with a binary heap for O((V+E) log V).
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (dist[u]! + w < dist[v]!) {
        dist[v] = dist[u]! + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  return dist;
}