Shortest Path: Dijkstra, PriorityQueue ve A*'a Kısa Bakış

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore kargo ağı: şehirler arası hatlar ve her hattın bir kargo maliyeti var (birim maliyet, örnek değerler). İstanbul'daki depodan Antalya'daki müşteriye en ucuz rota hangisi?

WeightedGraph g = new();
g.AddEdge("Istanbul", "Bursa", 4);
g.AddEdge("Istanbul", "Eskisehir", 9);
g.AddEdge("Bursa", "Eskisehir", 4);
g.AddEdge("Bursa", "Izmir", 8);
g.AddEdge("Eskisehir", "Ankara", 6);
g.AddEdge("Eskisehir", "Izmir", 11);
g.AddEdge("Ankara", "Konya", 7);
g.AddEdge("Konya", "Antalya", 8);
g.AddEdge("Izmir", "Antalya", 12);

Rotaları kabaca iki gruba ayırabiliriz: kuzeyden Ankara ve Konya üzerinden, ya da batıdan İzmir üzerinden. Hangisi daha ucuz, ve fark kaç birim? Kafadan topla ve tahminini aklında tut. Bir de şunu düşün: serinin 15. yazısındaki BFS (Breadth-First Search) bu soruya doğru cevap verebilir mi?

BFS Neden Yetmiyor

BFS bütün edge'lerin eşit olduğunu varsayar: bir adım bir adımdır. Bu ağda üç hatlı iki rota var: İstanbul, Bursa, İzmir, Antalya (4 + 8 + 12 = 24) ve İstanbul, Eskişehir, İzmir, Antalya (9 + 11 + 12 = 32). BFS için ikisi aynı uzunlukta; hangisini döndüreceği yalnız edge'lerin graph'a eklenme sırasına bağlı. Bu ekleme sırasında şanslıyız; İstanbul'un hatlarını ters sırayla eklersen BFS 32'lik rotayı "en kısa" diye verir. Ayrıca ağırlıklı graph'ta dört ucuz hat üç pahalı hattan daha az tutabilir. "En az adım" yerine "en düşük toplam maliyet" sırasıyla ilerleyen bir algoritma gerekiyor.

Ağırlıklar hepsi eşitse (ya da hepsi 1 ise) BFS hâlâ doğru ve en hızlı seçenek. Ağırlıklar yalnız 0 ve 1 ise deque kullanan 0-1 BFS yeterli. Genel negatif olmayan ağırlıklar için standart cevap Dijkstra.

Dijkstra'yı PriorityQueue ile Yazmak

Edsger Dijkstra'nın 1959'da yayımladığı algoritma BFS'in queue'sunu bir priority queue ile değiştirir: her zaman, şimdiye kadar bilinen en ucuz mesafeye sahip şehri işler. Negatif ağırlık yoksa, priority queue'dan çıkan bir şehrin mesafesi kesinleşmiştir; daha sonra bulunacak her yol, zaten daha pahalı bir noktadan geçeceği için onu ucuzlatamaz.

public sealed record PathResult(int Cost, IReadOnlyList<string> Path);

// PriorityQueue ve lazy deletion ile Dijkstra. O((V + E) log V); ağırlıklar >= 0 olmalı.
public static PathResult? Dijkstra(WeightedGraph graph, string source, string target, Action<string, int>? onSettled = null)
{
    Dictionary<string, int> dist = new() { [source] = 0 };
    Dictionary<string, string> previous = [];
    PriorityQueue<string, int> queue = new();
    queue.Enqueue(source, 0);

    while (queue.TryDequeue(out string? city, out int d))
    {
        if (d > dist[city])
        {
            continue; // eski kayıt: kuyruğa girdikten sonra daha kısa bir yol bulundu
        }

        onSettled?.Invoke(city, d);
        if (city == target)
        {
            return new PathResult(d, BuildPath(previous, target));
        }

        foreach ((string next, int cost) in graph.Edges(city))
        {
            int candidate = d + cost;
            if (candidate < dist.GetValueOrDefault(next, int.MaxValue))
            {
                dist[next] = candidate;
                previous[next] = city;
                queue.Enqueue(next, candidate); // decrease-key yok: yeni bir kayıt ekle
            }
        }
    }

    return null;
}

Döngünün iki satırı bu yazının asıl konusu. Serinin 13. yazısında gördük: .NET'in PriorityQueue'sunda decrease-key yok. Bir şehre daha ucuz bir yol bulduğumuzda kuyruktaki eski kaydın önceliğini düşüremiyoruz. Bunun yerine şehri yeni maliyetle bir kez daha ekliyoruz. Eski kayıt kuyrukta kalıyor ve bir gün çıkıyor; çıktığında d > dist[city] kontrolü onun eski olduğunu anlayıp atlıyor. Buna lazy deletion denir. Bedeli, kuyruğun en fazla E kayda kadar büyüyebilmesi; ama log E ile log V arasında yalnız sabit bir çarpan fark var (E en fazla V² olduğundan log E ≤ 2 log V), bu yüzden maliyet O((V + E) log V) olarak kalıyor.

Adım Adım: Kuyrukta Ne Oluyor

Aynı algoritmanın her kuyruk olayını yazdıran bir kopyasıyla İstanbul'dan Antalya'ya giderken olanlar:

  pop Istanbul 0: Bursa=4, Eskisehir=9
  pop Bursa 4: Eskisehir=8, Izmir=12
  pop Eskisehir 8: Ankara=14
  pop Eskisehir 9: stale, skip
  pop Izmir 12: Antalya=24
  pop Ankara 14: Konya=21
  pop Konya 21:
  pop Antalya 24: 

Açılıştaki sorunun cevabı: en ucuz rota batıdan, İzmir üzerinden 24 birim; kuzey rotası (Bursa, Eskişehir, Ankara, Konya) 4 + 4 + 6 + 7 + 8 = 29. Path reconstruction için her şehre hangi şehirden geldiğimizi previous'ta tutuyoruz ve hedeften geriye yürüyoruz:

private static List<string> BuildPath(Dictionary<string, string> previous, string target)
{
    List<string> path = [target];
    while (previous.TryGetValue(path[^1], out string? p)) path.Add(p);
    path.Reverse();
    return path;
}

settled Istanbul     0
settled Bursa        4
settled Eskisehir    8
settled Izmir       12
settled Ankara      14
settled Konya       21
settled Antalya     24
cost=24 path=Istanbul -> Bursa -> Izmir -> Antalya

İki ayrıntı. Hedef kuyruktan çıktığı an duruyoruz; Antalya için 24 bulduğumuz anda (adım 5) değil, çünkü o an daha ucuz bir yol hâlâ mümkün olabilirdi. Ve previous, eski kayıtlar atlandığı için her zaman en son ve en iyi güncellemeyi gösteriyor; Eskişehir'in parent'ı İstanbul değil, Bursa.

Negatif Ağırlık: Dijkstra'nın Bozulduğu Yer

Dijkstra'nın "kuyruktan çıkan kesinleşmiştir" varsayımı negatif bir edge ile çöker. Kargo ağına bir kampanya ekleyelim: İzmir'den Bursa'ya giden boş dönüş araçları için taşıyıcı 4 birim iade ediyor:

WeightedGraph refund = new();
refund.AddEdge("Depot", "Bursa", 2, bidirectional: false);
refund.AddEdge("Depot", "Izmir", 5, bidirectional: false);
refund.AddEdge("Izmir", "Bursa", -4, bidirectional: false);
Console.WriteLine($"Dijkstra Depot->Bursa: {ShortestPath.Dijkstra(refund, "Depot", "Bursa")!.Cost}");
Console.WriteLine($"Bellman-Ford Depot->Bursa: {ShortestPath.BellmanFord(refund, "Depot")!["Bursa"]}");

Dijkstra Depot->Bursa: 2
Bellman-Ford Depot->Bursa: 1

Dijkstra Bursa'yı 2 maliyetle kuyruktan çıkarıyor ve kesinleşmiş sayıp duruyor; oysa Depot, İzmir, Bursa rotası 5 - 4 = 1. Negatif ağırlık varsa Bellman-Ford gerekir: bütün edge'leri V - 1 tur boyunca gevşetir (relax) ve bir V'inci turda hâlâ iyileşme varsa negatif bir cycle olduğunu söyler:

// Bellman-Ford: O(V * E), negatif ağırlığı kaldırır, negatif cycle'ı tespit eder
public static Dictionary<string, int>? BellmanFord(WeightedGraph graph, string source)
{
    List<string> vertices = [.. graph.Vertices];
    Dictionary<string, int> dist = vertices.ToDictionary(v => v, _ => int.MaxValue);
    dist[source] = 0;
    for (int round = 0; round < vertices.Count - 1; round++)
    {
        bool changed = false;
        foreach (string u in vertices)
        {
            if (dist[u] == int.MaxValue) continue;
            foreach ((string v, int cost) in graph.Edges(u))
            {
                if (dist[u] + cost < dist[v])
                {
                    dist[v] = dist[u] + cost;
                    changed = true;
                }
            }
        }

        if (!changed) break;
    }

    foreach (string u in vertices)
    {
        if (dist[u] == int.MaxValue) continue;
        foreach ((string v, int cost) in graph.Edges(u))
        {
            if (dist[u] + cost < dist[v]) return null; // negatif cycle
        }
    }

    return dist;
}

Negatif cycle'da "en kısa yol" tanımsızdır: cycle'da döndükçe maliyet sonsuza kadar düşer. Gerçek hayatta bu genellikle veri hatasıdır (iki hattın iadesi birbirini besliyor) ya da kur farkı arbitrajı gibi bilinçli olarak aranan bir durumdur. O(V·E) maliyeti Dijkstra'dan çok daha yüksek; bu yüzden ağırlıkların negatif olmadığını biliyorsan Dijkstra, emin değilsen önce veriyi doğrula.

A*: Hedefe Doğru Bakmak

Dijkstra hedefin nerede olduğunu bilmez; başlangıçtan her yöne eşit hızla yayılır. Depo içinde bir robotun rafların arasından sol üst köşeden sağ alt köşeye gittiğini düşün: Dijkstra, robotun arkasında kalan koridorları da hedefe yakın olanlarla aynı öncelikle gezer. A* (Hart, Nilsson ve Raphael, 1968) kuyruktaki önceliği g + h yapar: g şimdiye kadarki gerçek maliyet, h hedefe kalan maliyetin bir tahmini (heuristic):

// useHeuristic = false, A*'ı aynı grid üzerinde düz Dijkstra'ya çevirir
public static (int Steps, int Expanded) Search(string[] grid, (int R, int C) start, (int R, int C) goal, bool useHeuristic)
{
    int rows = grid.Length, cols = grid[0].Length;
    int[,] g = new int[rows, cols];
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            g[r, c] = int.MaxValue;

    // 4 yönlü, maliyeti 1 olan hareketlerde Manhattan mesafesi hiçbir zaman fazla tahmin etmez: admissible
    int H((int R, int C) p) => useHeuristic ? Math.Abs(p.R - goal.R) + Math.Abs(p.C - goal.C) : 0;

    PriorityQueue<(int R, int C), int> open = new();
    g[start.R, start.C] = 0;
    open.Enqueue(start, H(start));
    int expanded = 0;
    while (open.TryDequeue(out (int R, int C) cell, out int f))
    {
        if (f - H(cell) > g[cell.R, cell.C]) continue;
        expanded++;
        if (cell == goal) return (g[cell.R, cell.C], expanded);

        foreach ((int dr, int dc) in Directions)
        {
            int nr = cell.R + dr, nc = cell.C + dc;
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] == '#') continue;
            int candidate = g[cell.R, cell.C] + 1;
            if (candidate < g[nr, nc])
            {
                g[nr, nc] = candidate;
                open.Enqueue((nr, nc), candidate + H((nr, nc)));
            }
        }
    }

    return (-1, expanded);
}

Heuristic'in tek şartı admissible olması: gerçek kalan maliyeti hiçbir zaman fazla tahmin etmemeli. Dört yönlü ve her adımı 1 olan bir grid'de Manhattan mesafesi (satır farkı + sütun farkı) duvarları yok sayar, yani gerçek yoldan hiçbir zaman uzun olamaz. Admissible bir heuristic ile A* en kısa yolu garanti eder; fazla tahmin eden bir heuristic daha hızlı olabilir ama yanlış yol bulabilir. h = 0 seçersek A* düz Dijkstra'ya döner; testte iki durumu aynı grid'de karşılaştırıyoruz.

200 × 200'lük, raf blokları ve koridorlardan oluşan bir depo kat planında:

200x200 warehouse: Dijkstra steps=398 expanded=33,600; A* steps=398 expanded=1,845

İkisi de aynı uzunlukta (398 adım) yolu buluyor; Dijkstra 33.600 hücreyi işlerken A* 1.845 hücreyle yetiniyor.

Ölçüm: Dijkstra ve A*

[Benchmark(Baseline = true)]
public int Dijkstra() => GridAStar.Search(_floor, (0, 0), (199, 199), useHeuristic: false).Steps;

[Benchmark]
public int AStar() => GridAStar.Search(_floor, (0, 0), (199, 199), useHeuristic: true).Steps;

Ölçümler Apple M5 (10 çekirdek), macOS 27.0.1, .NET 10.0.13, BenchmarkDotNet 0.15.8 ile alındı. Benchmark'ları tek tek çalıştırdım ama makinede paralel işler vardı; mutlak sayılara değil oranlara bak.

| Method   | Mean      | Ratio | Allocated |
|--------- |----------:|------:|----------:|
| Dijkstra | 835.66 us |  1.00 | 164.47 KB |
| AStar    |  59.51 us |  0.07 | 188.52 KB |

A* 14 kat hızlı. Allocation'ın çoğu iki yöntemde de aynı: 200 × 200'lük int[,] mesafe tablosu (160 KB). A* biraz daha fazla ayırıyor, çünkü kuyruğu farklı bir sırayla doldurup büyütüyor. Kazanç tamamen heuristic'in kalitesine bağlı: kat planı hedefle aynı yönde açık koridorlar sunduğu için Manhattan mesafesi iyi bir tahmin. Hedefin çıkmaz bir duvarın arkasında olduğu bir labirentte A* da Dijkstra kadar çok hücre gezebilir.

Üretimde Dikkat

Gerçek yol ağlarında Dijkstra'yı her istekte sıfırdan çalıştırmak pahalıdır. Harita servisleri contraction hierarchies gibi ön işleme teknikleri kullanır: graph bir kez işlenir, sonra her sorgu milisaniyenin altında cevaplanır. Bookstore ölçeğinde (onlarca depo, yüzlerce hat) düz Dijkstra fazlasıyla yeterli; en sık sorulan rotaları cache'lemek ve hat maliyetleri değişince cache'i temizlemek pratik bir adım.

Ağırlıkların birimi ve taşması. Maliyetleri int tutuyorsak int.MaxValue'yu "sonsuz" olarak kullanırken dist[u] + cost taşabilir. Bizim kodda Bellman-Ford bu yüzden dist[u] == int.MaxValue olanları atlıyor; Dijkstra'da sadece kuyruktan çıkan, yani gerçek mesafesi olan şehirlerden ekleme yapıyoruz. Para birimiyle çalışıyorsan decimal ya da kuruş cinsinden long kullan.

Çok kriterli rotalar. "En ucuz" ile "en hızlı" çoğu zaman farklıdır. Tek bir ağırlık tanımla (maliyet + zaman × bir katsayı) ya da kısıtlı bir arama yap (en geç 48 saatte teslim olan en ucuz rota); ikincisi düz Dijkstra'nın kapsamını aşar ve state'e kalan süreyi eklemeyi gerektirir.

Ölç, sonra optimize et. Yüzlerce şehirlik bir graph için Dictionary<string, int> yerine int id'li array'ler kullanmak gerçek bir hızlanma sağlar (serinin 15. yazısındaki id mapping), ama okunabilirlikten ödün verir. Profil göstermeden yapma.

Sık Düşülen Tuzaklar

Lazy deletion kontrolünü unutmak. if (d > dist[city]) continue; satırı olmadan algoritma yine doğru sonucu bulur, ama eski kayıtlar da işlenir ve her biri komşularını yeniden gevşetir. Yoğun graph'larda iş katlanır ve onSettled gibi callback'ler aynı şehir için birden çok kez çağrılır; şehri "teslimat planına ekle" gibi bir yan etki varsa bu doğrudan hata olur.

Hedef eklendiğinde durmak. Hedefin mesafesini ilk güncellediğin anda durursan (adım 5'teki 24'te durmak gibi), daha ucuz bir rota kuyrukta beklerken yanlış cevap verirsin. Dur ancak hedef kuyruktan çıktığında.

Negatif ağırlıkla Dijkstra. İade, indirim ya da "kazanç" kenarları graph'a girdiğinde Dijkstra sessizce yanlış sonuç verir; exception yok, uyarı yok. Graph'ı kurarken negatif ağırlığı reddeden bir guard ekle.

Admissible olmayan heuristic. Grid'de çapraz hareket de varsa Manhattan mesafesi gerçek mesafeyi fazla tahmin edebilir ve A* en kısa olmayan bir yol döndürür. Hareket modeline uygun heuristic seç (çapraz hareket için Chebyshev ya da octile mesafesi).

Küçük Bir Deneme

★☆☆ Dijkstra'yı hedef vermeden bütün şehirlere mesafe döndürecek şekilde değiştir (Dictionary<string, int>) ve sonucu testte Bellman-Ford ile karşılaştır.

★★☆ Lazy deletion satırını kaldırıp 10.000 vertex'lik, vertex başına 20 edge'li rastgele bir graph'ta onSettled'ın kaç kez çağrıldığını say. Satırla ve satırsız sürelerini BenchmarkDotNet ile ölç.

★★★ Depo grid'ine çapraz hareketi ekle (maliyet √2 yerine 14/10 oranıyla tamsayı: düz 10, çapraz 14). Manhattan, Chebyshev ve octile heuristic'lerini dene; hangisinin yanlış (daha uzun) yol bulduğunu bir testle göster.

Dijkstra iki nokta arasındaki en ucuz yolu buldu. Bir sonraki yazıda soru değişiyor: bütün ofisleri birbirine bağlayan en ucuz fiber ağı hangisi? Cevap bir yol değil bir tree; onu kurmak için önce "bu iki nokta zaten bağlı mı?" sorusunu neredeyse sabit sürede cevaplayan Union-Find'ı yazacağız.