Bölüm 4.2: En Kısa Yol Algoritmaları

4.2.1En kısa yol problemi

Çizge gezinme algoritmaları bir düğümden hangi düğümlere ulaşılabildiğini söyler. Gerçek uygulamalarda çoğu zaman bu yetmez: ulaşmanın en ucuz yolu da istenir. Kenarlara uzunluk, süre ya da maliyet gibi sayılar eklendiğinde soru “ulaşılır mı?” olmaktan çıkar, “en az kaça ulaşılır?” olur. Bu kesim problemi tanımlar, türlerini ayırır ve bütün algoritmaların üzerine kurulduğu ortak işlemi, gevşetmeyi anlatır.

4.2.1.1Yol ağı bir çizgedir

Bir şehrin yol haritası doğal bir çizgedir. Kavşaklar düğüm (vertex), kavşakları bağlayan yollar kenar (edge) olur. Her yolun bir uzunluğu ya da geçiş süresi vardır; bu sayıya kenarın ağırlığı (weight) denir. Kenarlarına ağırlık yazılmış çizgeye ağırlıklı çizge (weighted graph) adı verilir. Tek yönlü sokaklar varsa kenarların yönü de önemlidir; bu durumda çizge yönlüdür.

Çizgede bir yol, art arda gelen kenarlarla birbirine bağlanan düğümler dizisidir. Yolun uzunluğu, üzerindeki kenar ağırlıklarının toplamıdır. Bu tanımda kenar sayısı değil, ağırlıkların toplamı önemlidir. İki kenarlı bir yol, beş kenarlı bir yoldan daha uzun olabilir.

Şekil 4.2.1 küçük bir yol ağını gösterir. Ev'den Okul'a giden birkaç yol vardır. Ev–1–2–4–Okul yolu dört kenarlıdır ve uzunluğu 4 + 2 + 3 + 3 = 12'dir. Ev–1–4–Okul yolu yalnız üç kenarlıdır, ama 1–4 kenarı 6 birim tuttuğu için uzunluğu 4 + 6 + 3 = 13 olur. Ev–3–4–Okul yolu da üç kenarlıdır ve o da 13 eder. En kısa yol, en az kenarlı yol değil, dört kenarlı Ev–1–2–4–Okul yoludur: δ(Ev, Okul) = 12.

Örnek, problemin özünü gösterir. Ağırlıksız bir çizgede en kısa yol en az kenarlı yoldur ve genişlik öncelikli arama bunu doğrudan bulur. Ağırlıklı bir çizgede ise kenar saymak yetmez; ağırlıkların toplamı karşılaştırılmalıdır. Bu yüzden ağırlıklı çizgeler için ayrı algoritmalara gerek vardır.

En kısa yol problemi gündelik teknolojinin pek çok yerinde karşımıza çıkar. Navigasyon uygulamaları yol ağında en kısa ya da en hızlı güzergâhı hesaplar. İnternet yönlendiricileri paketleri hangi komşuya ileteceklerine en kısa yol hesabıyla karar verir. OSPF (Open Shortest Path First) protokolü Dijkstra algoritmasını, RIP (Routing Information Protocol) protokolü ise Bellman-Ford'un dağıtık bir biçimini kullanır. Oyunlarda karakterlerin engellerin çevresinden dolaşması A* aramasıyla yapılır. Lojistikte araçların dağıtım rotaları da en kısa yol hesaplarına dayanır.

4.2.1.2Problem türleri

“En kısa yolu bul” isteği üç farklı biçimde gelebilir. Hangi biçimin istendiği, kullanılacak algoritmayı da belirler.

• Tek kaynaklı en kısa yollar (single-source shortest paths): bir s kaynağından çizgedeki bütün düğümlere uzaklıklar istenir. Sonuç, her düğüm için bir sayı içeren bir dizidir. Dijkstra, Bellman-Ford ve ağırlıksız çizgede genişlik öncelikli arama bu problemi çözer.
• Tüm çiftler en kısa yolları (all-pairs shortest paths): her (u, v) düğüm çifti için uzaklık istenir. Sonuç n × n boyutlu bir matristir. Floyd-Warshall algoritması bu problem için tasarlanmıştır.
• Tek çift (single-pair): yalnız bir s başlangıcından bir t hedefine en kısa yol istenir. Tek kaynaklı bir algoritma bu işi de görür, ama gereğinden fazla düğüm açar. A* araması hedefi bildiği için aramayı ona doğru yöneltir.

Problem türlerinin yanında çizgenin özellikleri de seçimi etkiler. En önemli özellik, negatif ağırlıklı kenar olup olmadığıdır. Ağırlıklar maliyet olarak düşünülünce negatif değer garip görünebilir. Oysa kazanç ya da geri ödeme taşıyan kenarlarda negatif ağırlık doğaldır: bir ulaşım ağında indirim sağlayan aktarma, bir finans çizgesinde kâr getiren işlem böyle kenarlardır. Tablo 4.2.1 bölümdeki algoritmaları ne buldukları ve kısıtlarıyla birlikte listeler.

4.2.1.3Temel işlem: gevşetme

Bu bölümdeki algoritmaların hepsi aynı fikirle çalışır. Her düğüm için o ana kadar bulunmuş en iyi yolun uzunluğu bir tahmin olarak tutulur. Algoritma ilerledikçe daha kısa yollar bulunur ve tahminler küçülür. Sonunda her tahmin gerçek uzaklığa eşit olur. Her düğüm için iki bilgi saklanır:

• d[v]: kaynaktan v'ye şimdiye kadar bulunan en kısa yolun uzunluğu. Başta kaynakta 0, diğer bütün düğümlerde ∞'dur. ∞ “henüz yol bulunmadı” demektir.
• π[v]: bu yolda v'den hemen önce gelen düğüm. Bu düğüme önceki (predecessor) düğüm denir. Başta tanımsızdır ve “/” ya da “–” ile gösterilir.

Tahminleri küçülten tek işlem gevşetmedir. Bir (u, v) kenarı gevşetilirken şu soru sorulur: kaynaktan u'ya bilinen yolu alıp sonuna (u, v) kenarını eklersek, v için bildiğimizden daha kısa bir yol çıkar mı? Çıkarsa v'nin tahmini ve önceki düğümü güncellenir.

RELAX(u, v, w):
  eğer d[u] + w(u, v) < d[v]:
    d[v] = d[u] + w(u, v)
    π[v] = u

Sözde kod tanımın kendisidir. İkinci satır, u üzerinden gelen yolun daha kısa olup olmadığını sorar. Kısaysa üçüncü satır yeni uzunluğu yazar, dördüncü satır da yolun artık u'dan geldiğini kaydeder. İşlem bir karşılaştırma ve en çok iki atamadan oluşur; süresi O(1)'dir.

Gevşetmenin iki önemli özelliği vardır. Birincisi, d[v] yalnız azalabilir; hiçbir gevşetme bir tahmini büyütmez. İkincisi, d[v] hiçbir zaman gerçek uzaklık δ(s, v)'nin altına inmez. Bunun nedeni basittir: d[v]'ye yazılan her değer, kaynaktan v'ye gerçekten var olan bir yolun uzunluğudur. Hiçbir yol en kısa yoldan kısa olamayacağına göre tahmin de uzaklığın altına düşemez. Tahmin yukarıdan aşağı doğru iner ve doğru değere ulaşınca orada durur.

Algoritmalar arasındaki fark gevşetmede değil, kenarların hangi sırayla ve kaç kez gevşetildiğindedir. Dijkstra her kenarı bir kez, akıllıca seçilmiş bir sırada gevşetir. Bellman-Ford bütün kenarları sıra gözetmeden tekrar tekrar gevşetir. Floyd-Warshall aynı işlemi düğüm çiftleri üzerinde, ara düğüm ekleyerek yapar. A* ise Dijkstra'nın sırasını hedefe olan tahminle değiştirir.

4.2.1.4En kısa yolların özellikleri

Algoritmaların neden doğru çalıştığını anlamak için en kısa yolların dört özelliğini bilmek gerekir. Bu özellikler hem algoritmaların tasarımında hem de doğruluk kanıtlarında kullanılır.

Optimal alt yapı. En kısa yolun her parçası da en kısa yoldur. s ⇝ u ⇝ v yolu s'den v'ye en kısa yolsa, bu yolun s ⇝ u parçası da s'den u'ya en kısa yoldur. Kanıt kısa bir çelişkiyle yapılır. s'den u'ya daha kısa bir yol olsaydı, eski parça çıkarılıp yerine bu yol konabilirdi. O zaman v'ye de daha kısa bir yol elde edilirdi; bu, yolun en kısa olmasıyla çelişir. Optimal alt yapı (optimal substructure), dinamik programlamanın ve açgözlü algoritmaların ortak dayanağıdır. Bellman-Ford ve Floyd-Warshall bu özelliği dinamik programlamayla, Dijkstra açgözlü seçimle kullanır.

Üçgen eşitsizliği. Her (u, v) kenarı için δ(s, v) ≤ δ(s, u) + w(u, v) sağlanır. Eşitsizliğin sağ tarafı, u'ya en kısa yoldan gidip (u, v) kenarını kullanan belirli bir yolun uzunluğudur. En kısa yol bu yoldan uzun olamaz. Gevşetme bu eşitsizliğin tahminler üzerinde bozulduğu kenarları bulup düzeltir: d[v] > d[u] + w(u, v) olan her kenar bir düzeltme fırsatıdır.

Negatif döngü. Toplam ağırlığı negatif olan bir döngüye negatif döngü (negative cycle) denir. Kaynaktan böyle bir döngüye ulaşılabiliyorsa, döngüde her tur atıldığında yol biraz daha kısalır. Yol istenildiği kadar kısaltılabildiği için en kısa yol tanımsız kalır; uzaklık −∞ olarak yazılır. Bu durum yalnız döngüdeki düğümleri değil, döngüden geçerek ulaşılan bütün düğümleri etkiler.

Basit yol. Negatif döngü yoksa en kısa yol bir döngü içermez. Pozitif ağırlıklı bir döngüyü yoldan çıkarmak yolu kısaltır, sıfır ağırlıklı bir döngüyü çıkarmak ise uzunluğu değiştirmez. Her iki durumda da döngüsüz bir en kısa yol vardır. Döngü içermeyen yol her düğümden en çok bir kez geçer. V düğümlü bir çizgede böyle bir yol en çok V düğüm, dolayısıyla en çok V − 1 kenar içerir. Bellman-Ford'un V − 1 tur dönmesinin nedeni budur.

En kısa yol ağacı, bütün en kısa yolları tek bir yapıda toplar. Her düğüm yalnız kendi önceki düğümünü sakladığı için yolların hepsi V boyutlu tek bir π dizisine sığar. Bir yolu okumak için hedeften başlanır ve π işaretçileri kaynağa varana kadar izlenir. Bu yolla elde edilen düğümler ters sıradadır; yolu kaynaktan hedefe yazmak için sıra çevrilir.

4.2.2Dijkstra algoritması

Dijkstra algoritması tek kaynaklı en kısa yol probleminin en çok kullanılan çözümüdür. Edsger W. Dijkstra algoritmayı 1956'da geliştirdi ve 1959'da üç sayfalık kısa bir makalede yayımladı. Algoritma, kaynaktan diğer bütün düğümlere en kısa yolları bulur. Tek bir koşulu vardır: kenar ağırlıklarının hiçbiri negatif olmamalıdır. Bu koşul sağlandığında hızlıdır ve büyük yol ağlarında bile pratikte kullanılabilir.

4.2.2.1Açgözlü seçim ve su dalgası

Algoritmanın fikrini bir benzetme iyi anlatır. Durgun bir göle taş atıldığında dalga her yöne aynı hızla yayılır. Dalga önce taşa en yakın noktaya, sonra bir sonraki en yakın noktaya ulaşır. Kenarları su kanalları, ağırlıkları kanal uzunlukları gibi düşünelim. Kaynaktan çıkan dalga düğümlere tam olarak uzaklık sırasıyla varır. Bir düğüme ilk ulaşan dalga, oraya en kısa yoldan gelmiştir; daha sonra gelen hiçbir dalga daha erken varamaz.

Dijkstra algoritması bu dalganın hareketini adım adım taklit eder. Düğümler iki gruba ayrılır. Uzaklığı kesinleşmiş düğümler S kümesindedir; dalga onlara çoktan ulaşmıştır. Diğer düğümlerin yalnız bir tahmini vardır. Her adımda, kesinleşmemiş düğümler arasından tahmini en küçük olan seçilir ve kesinleştirilir. Sonra bu düğümden çıkan kenarlar gevşetilir; böylece komşuların tahminleri güncellenir.

Her adımda “şu an en iyi görünen” seçeneği alan ve bu kararı bir daha değiştirmeyen algoritmalara açgözlü algoritma (greedy algorithm) denir. Dijkstra açgözlüdür: seçilen düğümün uzaklığını kesin kabul eder ve ona bir daha dokunmaz. Açgözlü kararlar çoğu problemde yanlış sonuç verir. Dijkstra'da ise doğrudur, çünkü ağırlıklar negatif değildir. Bu koşulun neden yeterli olduğu ve bozulunca ne olduğu kesimin sonunda gösterilir.

4.2.2.2Algoritmanın adımları

Algoritma beş adımda özetlenir:

1. İlklendirme. Kaynağın uzaklığı 0, diğer bütün düğümlerin uzaklığı ∞ yapılır. Önceki düğümler tanımsızdır ve kesinleşmiş düğüm kümesi boştur: d[s] = 0, d[v] = ∞, π[v] = tanımsız, S = ∅.
2. Seçim. Kesinleşmemiş düğümler arasından d değeri en küçük olan u seçilir ve S'ye eklenir. Seçim bir dizi taranarak ya da bir öncelikli kuyruk (priority queue) ile yapılır.
3. Aday uzaklıklar. u'nun henüz kesinleşmemiş her komşusu v için aday uzaklık d[u] + w(u, v) hesaplanır.
4. Gevşetme. Aday uzaklık d[v]'den küçükse d[v] ve π[v] güncellenir.
5. Tekrar. Bütün düğümler kesinleşene ya da kalan düğümlerin hepsinin uzaklığı ∞ olana kadar 2.–4. adımlar tekrarlanır. Kaynaktan ulaşılamayan düğümlerin uzaklığı ∞ olarak kalır.

Her düğüm bir kez seçilir ve seçildiği anda çıkan kenarları bir kez gevşetilir. Yönlü bir çizgede her kenar toplamda bir kez, yönsüz bir çizgede iki uçtan birer kez ele alınır. Algoritmanın bütün işi bu seçimler ve gevşetmelerden oluşur.

4.2.2.3Örnek 1: yönsüz çizge

İlk örnek altı düğümlü yönsüz bir çizgedir; kaynak 1 numaralı düğümdür. Kenarlar ve ağırlıkları şunlardır: 1–2 (7), 1–3 (9), 1–6 (14), 2–3 (10), 2–4 (15), 3–4 (11), 3–6 (2), 4–5 (6), 5–6 (9). Şekil 4.2.4 çizgenin başlangıç ve bitiş durumlarını yan yana gösterir.

Algoritma altı tur döner; her turda bir düğüm kesinleşir. Tablo 4.2.2 her turdan sonraki uzaklık tahminlerini verir. Kalın değerler o turda değişen tahminlerdir.

Turların ayrıntısı şöyledir. Birinci turda yalnız kaynağın uzaklığı sonludur; 1 seçilir. 1'in üç komşusu vardır ve hepsinin tahmini ∞'dur. Kenar ağırlıkları doğrudan yeni tahminler olur: d[2] = 7, d[3] = 9, d[6] = 14. Üçünün de önceki düğümü 1'dir.

İkinci turda kesinleşmemiş düğümlerin en küçük tahmini 7'dir; 2 seçilir. 1 zaten kesinleştiği için atlanır. 2–3 kenarı 7 + 10 = 17 önerir; bu 9'dan büyük olduğu için 3'ün tahmini değişmez. 2–4 kenarı 7 + 15 = 22 önerir ve 4'e ilk kez bir yol bulunur: d[4] = 22, π[4] = 2.

Üçüncü turda 3 seçilir (d = 9). Bu tur örneğin en öğretici adımıdır. 3–4 kenarı 9 + 11 = 20 önerir ve bu, bir önceki turda bulunan 22'den küçüktür. Böylece 4'ün tahmini 20'ye iner ve önceki düğümü 2'den 3'e geçer. 3–6 kenarı da 9 + 2 = 11 önerir ve 6'nın 14 olan tahminini düşürür. 1'den 6'ya doğrudan kenar 14 tutar; 3 üzerinden dolaşmak 11 tutar. Doğrudan kenar her zaman en kısa yol değildir.

Dördüncü turda en küçük tahmin 11'dir; 6 seçilir. 6–5 kenarı 5'e ilk yolu verir: 11 + 9 = 20. Beşinci turda 4 ve 5'in tahminleri eşittir (20). Eşitlikte küçük numaralı düğüm seçilmiştir; 4 kesinleşir. 4–5 kenarı 20 + 6 = 26 önerir, 20'yi geçemez. Son turda 5 seçilir ve kesinleşmemiş komşusu kalmadığı için algoritma biter.

Sonuçta uzaklıklar 2: 7, 3: 9, 6: 11, 4: 20, 5: 20'dir. Önceki dizisi π[2] = 1, π[3] = 1, π[4] = 3, π[5] = 6, π[6] = 3'tür. Bu beş kenar en kısa yol ağacını oluşturur. Örneğin 5'e en kısa yol, işaretçiler geriye izlenerek bulunur: 5 ← 6 ← 3 ← 1. Yol 1 → 3 → 6 → 5, uzunluğu 9 + 2 + 9 = 20'dir. Düğümlerin kesinleşme sırası 1, 2, 3, 6, 4, 5'tir; bu sıra uzaklıkların küçükten büyüğe sırasıyla aynıdır.

4.2.2.4Örnek 2: yönlü çizge, Q ve S kümeleri

İkinci örnek beş düğümlü yönlü bir çizgedir ve kaynak 5'tir. Kenarlar: 5 → 2 (4), 5 → 4 (2), 4 → 2 (1), 4 → 3 (1), 3 → 4 (2), 2 → 1 (3), 1 → 3 (6), 1 → 4 (3). Yönlü çizgede kenar yalnız ok yönünde kullanılır. Örneğin 2 → 1 kenarı 2'den 1'e gitmeye izin verir, tersine izin vermez. Aynı çizge Bellman-Ford ve Floyd-Warshall örneklerinde de kullanılacak; böylece üç algoritmanın sonuçları karşılaştırılabilir.

Bu kez algoritmanın durumu iki kümeyle izlenir. Q, henüz kesinleşmemiş düğümlerin öncelikli kuyruğudur ve düğümleri d değerine göre sıralı tutar. S ise kesinleşmiş düğümlerin listesidir. Her adımda Q'nun başındaki düğüm alınır, S'ye eklenir ve kenarları gevşetilir.

İkinci adım dikkat ister. 4 kesinleşince 4 → 2 kenarı 2 + 1 = 3 önerir. 2'nin tahmini birinci adımda doğrudan kenarla 4 olmuştu; şimdi 3'e iner. Kaynaktan 2'ye doğrudan kenar 4 tutar, 4 üzerinden dolaşmak ise 3 tutar. Üçüncü adımda 2 ile 3'ün tahminleri eşittir (3); küçük numaralı 2 önce alınır. Dördüncü ve beşinci adımlarda yeni gevşetme olmaz, çünkü kenarların ucundaki düğümler zaten kesinleşmiştir.

Son durumda uzaklıklar ve önceki düğümler şöyledir:

Yeşil kenarlar iki yol verir: 5 → 4 → 2 → 1 (uzunluk 2 + 1 + 3 = 6) ve 5 → 4 → 3 (uzunluk 2 + 1 = 3). 5 → 2 kenarı en kısa yol ağacına girmez; çünkü 2'ye 4 üzerinden daha kısa bir yol vardır.

4.2.2.5Sözde kod ve tembel silme

Algoritmanın öncelikli kuyruklu sözde kodu aşağıdadır. Kuyrukta (düğüm, uzaklık) çiftleri tutulur; çıkar() işlemi uzaklığı en küçük çifti döndürür.

DIJKSTRA(G, kaynak):
  mesafeler = [ ]; ziyaretEdildi = [ ]
  öncelikKuyruğu = { }
  her bir v için V içinde:
    mesafeler[v] = sonsuz
    ziyaretEdildi[v] = 0
  mesafeler[kaynak] = 0
  öncelikKuyruğu.ekle(kaynak, 0)
  döngü öncelikKuyruğu boş değil iken:
    u = öncelikKuyruğu.çıkar()   // en küçük mesafe
    eğer ziyaretEdildi[u] == 0:
      ziyaretEdildi[u] = 1
      her bir (u, v) için G[u] içinde:
        eğer mesafeler[u] + ağırlık(u, v) < mesafeler[v]:
          mesafeler[v] = mesafeler[u] + ağırlık(u, v)
          öncelikKuyruğu.ekle(v, mesafeler[v])
  döndür mesafeler

İlk altı satır dizileri hazırlar: her düğümün uzaklığı sonsuz, ziyaret bilgisi 0 olur. Kaynağın uzaklığı 0 yapılır ve kaynak kuyruğa eklenir. Ana döngü kuyruk boşalana kadar döner. Her turda en küçük uzaklıklı kayıt çıkarılır. Düğüm daha önce işlenmemişse işaretlenir ve komşuları gevşetilir. Bir komşunun uzaklığı küçülürse komşu, yeni uzaklığıyla kuyruğa eklenir.

Kodda bir ayrıntı göze çarpar: bir düğümün uzaklığı küçüldüğünde kuyruktaki eski kaydı silinmez, yeni bir kayıt eklenir. Böylece aynı düğüm kuyrukta birden çok kez bulunabilir. Eski kayıt daha büyük bir uzaklık taşıdığı için kuyruktan daha geç çıkar. Çıktığında düğüm zaten işaretlenmiştir ve ziyaretEdildi denetimi onu atlar. Bu yönteme tembel silme (lazy deletion) denir.

Tembel silmenin nedeni, Java'nın PriorityQueue sınıfında bir öğenin önceliğini azaltan bir işlemin bulunmamasıdır. Kuyruktan rastgele bir öğeyi silmek de doğrusal zaman alır. Yeni kayıt eklemek ise O(log n) sürer. Bedeli, kuyruğun biraz büyümesidir: her gevşetme bir kayıt ekleyebildiği için kuyrukta en çok E kayıt birikir. Yolu da bulmak isteniyorsa gevşetme sırasında önceki[v] = u ataması eklenir.

4.2.2.6Java kodu ve izleme

Sözde kodun Java karşılığı aşağıdadır. Çizge komsu adlı bir komşuluk listesinde tutulur: komsu.get(u), u'dan çıkan kenarların listesidir. Her Kenar nesnesinin hedef ve agirlik alanları vardır. Düğümler 1'den V'ye kadar numaralıdır; bu yüzden diziler V + 1 boyutludur ve 0 indisi kullanılmaz. SONSUZ, Integer.MAX_VALUE değerini taşıyan bir sabittir.

void dijkstra(int kaynak) {
  int[] uzaklik = new int[V + 1];
  int[] onceki = new int[V + 1];
  boolean[] ziyaret = new boolean[V + 1];
  Arrays.fill(uzaklik, SONSUZ);
  uzaklik[kaynak] = 0;
  PriorityQueue<int[]> kuyruk =
    new PriorityQueue<>((a, b) -> a[1] - b[1]);
  kuyruk.add(new int[] { kaynak, 0 });
  while (!kuyruk.isEmpty()) {
    int u = kuyruk.poll()[0];
    if (ziyaret[u]) continue; // eski kayıt
    ziyaret[u] = true;
    for (Kenar k : komsu.get(u)) {
      int v = k.hedef, w = k.agirlik;
      if (!ziyaret[v]
          && uzaklik[u] + w < uzaklik[v]) {
        uzaklik[v] = uzaklik[u] + w;
        onceki[v] = u;
        kuyruk.add(new int[] { v, uzaklik[v] });
      }
    }
  }
}

Kod satır satır şöyle okunur:

• Satır 2–6: uzaklik, onceki ve ziyaret dizileri oluşturulur. uzaklik sonsuzla doldurulur, kaynağınki 0 yapılır. boolean dizisi Java'da kendiliğinden false ile başlar.
• Satır 7–9: Kuyruk int[] çiftleri tutar: a[0] düğüm, a[1] o anki uzaklıktır. Karşılaştırıcı (a, b) -> a[1] - b[1] çiftleri uzaklığa göre sıralar; böylece poll() en küçük uzaklıklı çifti verir. Başta kuyrukta yalnız {kaynak, 0} vardır.
• Satır 11–13: En küçük çift çıkarılır ve düğümü u'ya alınır. Düğüm daha önce işlenmişse bu eski bir kayıttır ve continue ile atlanır. İşlenmemişse işaretlenir; bu an düğümün kesinleştiği andır.
• Satır 14–21: u'dan çıkan her kenar için komşu v ve ağırlık w alınır. Komşu kesinleşmemişse ve u üzerinden gelen yol daha kısaysa gevşetme yapılır: uzaklık ve önceki güncellenir, yeni çift kuyruğa eklenir.

Karşılaştırıcıdaki çıkarma işlemi bir taşma tuzağı taşır. Uzaklıklardan biri SONSUZ olsaydı a[1] - b[1] taşabilir ve yanlış işaret verebilirdi. Bu kodda kuyruğa yalnız sonlu uzaklıklar eklendiği için sorun çıkmaz. Daha güvenli bir yazım Integer.compare(a[1], b[1]) ya da Comparator.comparingInt(a -> a[1]) olurdu.

Kod, Örnek 2'deki çizgede dijkstra(5) ile çalıştırıldığında kuyruk Tablo 4.2.5'teki gibi değişir. Kuyruk sütunu, her işlemden sonra kuyruktaki kayıtları küçükten büyüğe sırayla gösterir.

İzlemede tembel silme açıkça görülür. 2 numaralı düğüm kuyruğa iki kez girmiştir: önce (2, 4) olarak, sonra daha kısa yol bulununca (2, 3) olarak. Yeni kayıt önce çıkar ve 2'yi kesinleştirir. Eski (2, 4) kaydı beşinci poll() çağrısında çıkar; ziyaret[2] zaten true olduğu için atlanır. Toplam altı poll() çağrısı yapılır: beş düğüm için birer tane ve bir eski kayıt için bir tane. Döngü bittiğinde uzaklik = [6, 3, 3, 2, 0] ve onceki = [2, 4, 4, 5, –] olur (indis 1–5); bu, el ile bulunan sonuçla aynıdır.

4.2.2.7Yolu geri kurmak

Dijkstra uzaklıkları ve önceki dizisini birlikte üretir. Uzaklık dizisi “ne kadar?” sorusunu, önceki dizisi “hangi yoldan?” sorusunu cevaplar. Örnek 2'nin sonucu π = [2, 4, 4, 5, /] idi. Hedef 1 için işaretçiler geriye izlenir: π[1] = 2, π[2] = 4, π[4] = 5. 5 kaynaktır, izleme burada durur. Toplanan düğümler 1, 2, 4, 5 sırasındadır, yani hedeften kaynağa doğrudur. Sıra çevrilince yol 5 → 4 → 2 → 1 olur ve uzunluğu 2 + 1 + 3 = 6 = d[1]'dir.

Sırayı çevirmenin doğal yolu bir yığın (stack) kullanmaktır. Yığın son giren ilk çıkar (LIFO) ilkesiyle çalışır. Hedeften kaynağa doğru itilen düğümler kaynaktan hedefe doğru çekilir.

void yolYaz(int[] onceki, int kaynak, int hedef) {
  Deque<Integer> yigin = new ArrayDeque<>();
  for (int v = hedef; v != kaynak; v = onceki[v])
    yigin.push(v);         // hedeften geriye
  yigin.push(kaynak);
  while (!yigin.isEmpty())
    System.out.print(yigin.pop() + " ");
}

İkinci satır boş bir yığın oluşturur; Java'da ArrayDeque sınıfı yığın olarak kullanılır. for döngüsü v = hedef ile başlar. v kaynağa eşit olmadıkça v'yi yığına iter ve bir önceki düğüme geçer. Döngü kaynağı itmez; çünkü v kaynağa eşit olduğunda koşul yanlış olur. Beşinci satır kaynağı ayrıca iter. Son iki satır yığını boşaltarak düğümleri yazdırır. Tablo 4.2.6 yolYaz(onceki, 5, 1) çağrısının izlemesidir.

Yöntemin maliyeti yolun kenar sayısıyla orantılıdır. Yol en çok V − 1 kenarlı olduğu için süre ve yığının kapladığı yer O(V)'dir. Önceki dizisinin kendisi de O(V) yer tutar. Bütün en kısa yolların tek bir dizide saklanabilmesi, optimal alt yapının pratik bir sonucudur: her yol, kendinden bir önceki düğümün yolunun bir kenar uzatılmış hâlidir.

4.2.2.8Karmaşıklık

Dijkstra'nın maliyeti iki işlemden gelir: en küçük uzaklıklı düğümü seçmek ve kenarları gevşetmek. Seçim V kez, gevşetme en çok E kez yapılır. Toplam süre, bu iki işlemin hangi veri yapısıyla yapıldığına bağlıdır.

• Dizi. Uzaklıklar sırasız bir dizide tutulur. En küçüğü bulmak bütün diziyi taramak demektir: her seçim O(V), V seçim O(V²) tutar. Gevşetme diziye tek bir yazmadır, O(1). Toplam O(V² + E) = O(V²)'dir, çünkü basit bir çizgede E < V²'dir.
• İkili heap. Öncelikli kuyruk ikili heap ile kurulur. En küçüğü çıkarmak ve yeni kayıt eklemek O(log V) sürer. V çıkarma ve en çok E ekleme yapılır: toplam O((V + E) log V). Tembel silmede kuyrukta E kayıt bulunabilir; log E ≤ log V² = 2 log V olduğundan sınır değişmez.
• Fibonacci heap. Bu yapıda en küçüğü çıkarmak amortize O(log V), önceliği azaltmak amortize O(1) sürer. Toplam O(E + V log V)'dir. Kuramsal olarak en iyi sınırdır, ama yapının sabitleri büyük olduğu için pratikte ikili heap çoğu zaman daha hızlıdır.

Hangi yapının daha iyi olduğu çizgenin yoğunluğuna bağlıdır. Yoğun bir çizgede kenar sayısı V² mertebesindedir. Heap sürümü bu durumda O(V² log V) tutar ve dizi sürümünden yavaştır. Seyrek bir çizgede ise kenar sayısı V mertebesindedir ve heap sürümü açıkça kazanır. Yol ağları seyrektir: bir kavşaktan çoğu zaman üç dört yol çıkar.

Bellek tarafında uzaklik, onceki ve ziyaret dizileri O(V) yer tutar. Tembel silmeli kuyrukta en çok E kayıt birikebilir. Toplam ek bellek O(V + E)'dir. Önceliği azaltma işlemi olan bir kuyrukta her düğüm bir kez bulunur ve kuyruk O(V) yer tutar.

4.2.2.9Doğruluk ve negatif kenar sorunu

Dijkstra bir düğümü seçtiği anda onun uzaklığını kesin kabul eder. Bu kararın neden doğru olduğu aşağıdaki teoremle gösterilir.

Kanıtın kilit adımı δ(s, y) ≤ δ(s, u) eşitsizliğidir. Yol y'den u'ya devam ederken uzunluğu azalmaz, çünkü eklenen her kenar negatif değildir. Kısacası, S'nin dışından geçen her yol en az d[u] uzunluğundadır; yol ancak uzayabilir. Negatif bir kenar bu varsayımı bozar. Sonradan işlenen bir düğüm, negatif bir kenarla kesinleşmiş bir düğüme daha kısa bir yol açabilir. Dijkstra kesinleşmiş düğümlere dönmediği için bu yolu hiç görmez.

Akla gelen bir çözüm, bütün ağırlıklara aynı sabiti ekleyerek negatif kenarları ortadan kaldırmaktır. Bu çözüm işe yaramaz. Sabit her kenara eklendiği için çok kenarlı yollar daha fazla ceza alır. Örnekte bütün ağırlıklara 2 eklenirse A → B yolu 4, A → C → B yolu 5 + 0 = 5 olur. Artık doğrudan kenar daha kısa görünür ve en kısa yol değişmiş olur. Sabit ekleme, kenar sayısı sabit olan yapılarda sıralamayı korur: örneğin her kapsayan ağaçta V − 1 kenar bulunur. En kısa yollarda ise kenar sayısı yoldan yola değişir. Negatif kenar varsa doğru araç Bellman-Ford algoritmasıdır.

4.2.3Bellman-Ford algoritması

Dijkstra hızlıdır, ama negatif kenara dayanamaz. Bellman-Ford algoritması bu eksiği kapatır. Algoritma tek kaynaklı en kısa yolları bulur, negatif ağırlıklı kenarlarla doğru çalışır ve kaynaktan ulaşılabilen negatif döngüleri tespit eder. Bunun bedeli hızdır: Bellman-Ford O(V · E) zaman alır ve Dijkstra'dan belirgin biçimde yavaştır.

Algoritma adını Richard Bellman (1958) ve Lester Ford Jr.'dan (1956) alır. Edward F. Moore da 1959'da aynı yöntemi bağımsız olarak yayımlamıştır; bu yüzden bazı kaynaklarda Bellman-Ford-Moore algoritması diye geçer.

4.2.3.1Fikir ve adımlar

Bellman-Ford hiçbir düğümü kesinleştirmez ve düğüm seçmez. Bunun yerine bütün kenarları sırayla gevşetir ve bu taramayı V − 1 kez tekrarlar. Bir taramaya tur denir. Her turda bir kenarın gevşemesi, bir düğümün tahminini düşürür. Bu düşüş, o düğümden çıkan kenarların sonraki gevşetmelerinde komşulara da yansır. İyileşme böylece yol boyunca ilerler.

Bu yaklaşım açgözlü değildir; bir dinamik programlamadır (dynamic programming). i. tur, en çok i kenarlı en kısa yolları, bir önceki turun bulduğu en çok i − 1 kenarlı yollardan kurar. Algoritmanın dört adımı şunlardır:

1. İlklendirme. Kaynağa uzaklık 0, diğer düğümlere ∞ atanır; önceki düğümler tanımsızdır.
2. Turlar. Kenarlar tek tek incelenir ve her biri gevşetilir; bu tur V − 1 kez tekrarlanır. Bir turdaki kenar sırası bütün turlarda aynıdır. Sıra sonucu değiştirmez, yalnız sonuca kaç turda ulaşılacağını etkiler.
3. Yayılma. Bir düğümün uzaklığı güncellenirse, sonraki incelemelerde onun komşularının uzaklıkları da güncellenebilir. İyileşme, yol boyunca her turda en az bir kenar ilerler.
4. Denetim. Negatif döngü kontrolü için bütün kenarlar bir kez daha incelenir. Hâlâ gevşeyen bir kenar varsa kaynaktan ulaşılabilen bir negatif döngü vardır. Döngü yoksa V − 1 turdan sonra hiçbir kenar gevşemez.

Bellman-Ford düğüm seçmediği için komşuluk listesine de gerek duymaz. Çizgeyi bir kenar listesi olarak tutmak yeter: her kayıt bir (u, v, w) üçlüsüdür. Algoritma bu listeyi baştan sona okur ve her üçlüyü gevşetir.

4.2.3.2Neden V − 1 tur? Karmaşıklık

Tur sayısının nereden geldiği, en kısa yolların bir özelliğine dayanır. Negatif döngü yoksa her düğüme döngüsüz bir en kısa yol vardır ve bu yol en çok V − 1 kenarlıdır. Algoritmanın her turu bu yolları bir kenar daha uzatır.

Kanıtın ana fikri şudur: j. turda yolun j. kenarı mutlaka gevşetilir. Kenarların hangi sırada incelendiği önemli değildir; sıra ancak işin daha erken bitmesini sağlayabilir. Uygun bir sırada, bir tur içinde birkaç kenar art arda iyileşebilir ve yol tek turda tamamlanabilir. En kötü sırada ise her tur yalnız bir kenar ilerler ve V − 1 turun hepsi gerekir.

Süre kolayca hesaplanır. Her tur E kenarı inceler ve her inceleme O(1) sürer. V − 1 tur ve bir denetim turu, toplam V · E inceleme eder: O(V · E). Ek bellek yalnız uzaklık ve önceki dizileridir: O(V).

Tablonun son satırı basit bir iyileştirmeden gelir. Bir turda hiçbir d değeri değişmezse sonraki turlar da hiçbir şeyi değiştiremez. Çünkü bir tur, yalnız bir önceki turda değişen tahminler sayesinde yeni bir gevşetme bulabilir. Değişiklik olmayan bir turdan sonra döngüden çıkılabilir. Kenarlar uygun sıradaysa ilk tur her şeyi bulur, ikinci tur bunu doğrular: süre O(E)'ye iner.

int[] bellmanFordErken(int V, List<Kenar> kenarlar, int kaynak) {
  int[] uzaklik = new int[V];
  Arrays.fill(uzaklik, SONSUZ);
  uzaklik[kaynak] = 0;
  for (int i = 1; i < V; i++) {
    boolean degisti = false;
    for (Kenar k : kenarlar) {
      int u = k.bas, v = k.son, w = k.agirlik;
      if (uzaklik[u] != SONSUZ && uzaklik[u] + w < uzaklik[v]) {
        uzaklik[v] = uzaklik[u] + w;
        degisti = true;
      }
    }
    if (!degisti) break;   // bu tur hiçbir şeyi değiştirmedi
  }
  return uzaklik;
}

Kodda her turun başında degisti bayrağı false yapılır. Turdaki herhangi bir gevşetme bayrağı true yapar. Tur bittiğinde bayrak hâlâ false ise break döngüyü sonlandırır. Erken durma sonucu değiştirmez; yalnız gereksiz turları atlar. En kötü durum yine O(V · E)'dir, çünkü her turda bir şey değişebilir.

4.2.3.3Örnek 1: kenar kenar gevşetme

İlk örnek beş düğümlü yönlü bir çizgedir. Kaynak s'dir ve kenarlar her turda şu sırayla incelenir: (s, v₁) 9, (s, v₂) 3, (v₁, v₂) 6, (v₁, v₄) 2, (v₂, v₁) 2, (v₂, v₃) 1, (v₃, v₂) 2, (v₃, v₄) 2.

Birinci turda sekiz kenardan altısı gevşer. Bazı tahminler aynı tur içinde iki kez değişir. v₁ önce doğrudan kenarla 9 olur, sonra v₂ üzerinden 5'e iner. v₄ önce 11 olur, sonra v₃ üzerinden 6'ya iner. Bu, kenar sırasının işe yaradığı bir durumdur. v₂'nin değeri, ondan çıkan kenarlar incelenmeden önce bulunmuştur; bu yüzden iyileşme aynı tur içinde yola yayılır.

İkinci turda sekiz kenarın hiçbiri gevşemez. Erken durmalı sürüm burada durur. Sonuç d[v₁] = 5, d[v₂] = 3, d[v₃] = 4, d[v₄] = 6'dır. Erken durma olmasaydı üç tur ve bir denetim turu daha boşa dönerdi. Bu sırada bütün iş tek turda bitmiştir.

4.2.3.4Örnek 2: negatif kenarlar ve en kötü sıra

İkinci örnekte altı düğüm ve dört negatif kenar vardır. Kaynak S'dir. Kenarlar her turda şu sırayla incelenir: (E, D) −4, (E, A) 4, (C, D) −2, (C, E) 1, (B, C) −2, (A, B) −1, (S, A) 3. Bu sıra bilerek seçilmiştir: en kısa yolun kenarlarını sondan başa doğru dizer. Bu, Bellman-Ford için en kötü sıradır.

Birinci turda yalnız (S, A) kenarı işe yarar. Listedeki diğer kenarların başlangıç düğümleri incelendikleri anda hâlâ ∞'dur. Örneğin (A, B) kenarı listede (S, A)'dan önce gelir. İncelendiğinde A'nın tahmini henüz ∞'dur ve kenar boşa geçer. Her tur yolu tam bir kenar uzatır: A, B, C sırayla bulunur. Dördüncü turda C'den çıkan iki kenar birden gevşer. Beşinci turda D, E üzerinden daha kısa bir yol bulur: 1 + (−4) = −3 < −2. Doğrudan C → D kenarı −2 verirken C → E → D yolu 1 − 4 = −3 verir.

V − 1 = 5 turun hepsi kullanılmıştır. Denetim turunda hiçbir kenar gevşemez; demek ki negatif döngü yoktur. Gerçekten de çizgedeki tek döngü A → B → C → E → A'dır ve ağırlığı −1 − 2 + 1 + 4 = +2'dir. Negatif kenarlar olduğu hâlde döngü pozitiftir.

4.2.3.5Örnek 3: Dijkstra'nın çizgesi

Üçüncü örnek, Dijkstra Örnek 2'deki yönlü çizgedir; kaynak yine 5'tir. Negatif kenar yoktur, bu yüzden iki algoritmanın aynı sonucu vermesi gerekir. Kenarlar her turda şu sırayla incelenir: (1, 3), (1, 4), (2, 1), (3, 4), (4, 2), (4, 3), (5, 2), (5, 4).

Birinci turda kaynaktan çıkan iki kenar listenin sonundadır; yalnız onlar gevşer. İkinci turda üç gevşetme olur. (2, 1) kenarı 1'e ilk yolu verir: 4 + 3 = 7. Hemen sonra (4, 2) kenarı 2'nin tahminini 3'e düşürür. Ama (2, 1) listede (4, 2)'den önce geldiği için bu iyileşme 1'e ancak üçüncü turda yansır: 3 + 3 = 6. Dördüncü turda hiçbir şey değişmez.

Sonuç d = [6, 3, 3, 2, 0] ve π = [2, 4, 4, 5, /]'dir. Dijkstra'nın bulduğu sonuçla tıpatıp aynıdır. Fark yapılan iştedir. Dijkstra her kenara bir kez bakmıştı; Bellman-Ford dört turda 32 kenar incelemesi yapar ve denetim turuyla bu sayı 40'a çıkar.

Denetim turu, her kenar için bir kez daha d[v] > d[u] + w(u, v) sorusunu sorar. Tablo 4.2.12 Örnek 3'ün sonucunda bu sorunun sekiz kenar için de “hayır” cevabını verdiğini gösterir.

Eşitlik sağlanan kenarlar dikkat çekicidir: (2, 1), (4, 2), (4, 3) ve (5, 4). Bunlar tam olarak en kısa yol ağacının kenarlarıdır. Ağaçtaki her kenar için d[v] = d[u] + w(u, v) olur, çünkü v'nin değeri bu kenardan gelmiştir. Ağaç dışındaki kenarlarda ise eşitsizlik kesindir.

4.2.3.6Negatif döngü tespiti

Denetim turunun gücü negatif döngülü bir çizgede ortaya çıkar. Şekil 4.2.11 dört düğümlü bir örnektir. Kaynak S'den A'ya 2 ağırlıklı bir kenar vardır. A → B → C → A döngüsünün ağırlığı ise 1 + (−3) + 1 = −1'dir. Kenar sırası (S, A), (A, B), (B, C), (C, A)'dır.

Birinci turda A önce S → A kenarıyla 2 olur. Tur bitmeden döngü dolaşılır: B = 3, C = 0 bulunur ve C → A kenarı A'yı 1'e indirir. Sonraki her turda döngüdeki üç değer birer azalır. Bu düşüş hiç durmaz, çünkü döngüde her tur atıldığında yol 1 kısalır. Normal bir çizgede değerler en geç V − 1 turda sabitlenir; burada sabitlenmezler.

V − 1 = 3 turdan sonra d = [0, −1, 1, −2]'dir. Denetim turu (S, A) ile başlar: 0 + 2 = 2, A'nın −1 olan değerinden küçük değildir. Sonra (A, B) gelir: −1 + 1 = 0 < 1. Kenar hâlâ gevşiyor; demek ki negatif döngü vardır. Döngüdeki ve döngüden ulaşılan bütün düğümlerin en kısa yolu tanımsızdır (−∞). Bulunan d değerleri bu düğümler için anlamsızdır; yalnız algoritmanın kaçıncı turda durdurulduğunu yansıtır.

4.2.3.7Sözde kod, Java kodu ve izleme

Bellman-Ford'un sözde kodu iki bölümden oluşur: V − 1 turluk dış döngü ve ardından gelen tek bir denetim turu.

BELLMAN_FORD(G, kaynak):
  mesafeler = [ ]
  her bir v için V içinde:
    mesafeler[v] = sonsuz
  mesafeler[kaynak] = 0
  döngü i = 1 den |V| - 1:
    her bir (u, v, ağırlık) için E içinde:
      eğer mesafeler[u] + ağırlık < mesafeler[v]:
        mesafeler[v] = mesafeler[u] + ağırlık
  her bir (u, v, ağırlık) için E içinde:
    eğer mesafeler[u] + ağırlık < mesafeler[v]:
      hata "Negatif ağırlıklı döngü var"
  döndür mesafeler

Dış döngü |V| − 1 kez döner; iç döngü her turda kenar listesinin tamamını gezer. Son dört satır denetim turudur. Denetim, gevşetmenin koşulunu sorar ama atama yapmaz; koşul doğruysa hata bildirir. Java karşılığında kenarlar kenarlar adlı bir listede tutulur. Her Kenar nesnesinin bas, son ve agirlik alanları vardır. Düğümler 0'dan V − 1'e kadar numaralıdır.

void bellmanFord(int kaynak) {
  int[] uzaklik = new int[V];
  int[] onceki = new int[V];
  Arrays.fill(uzaklik, SONSUZ);
  uzaklik[kaynak] = 0;
  for (int i = 1; i < V; i++) {
    for (Kenar k : kenarlar) {
      int u = k.bas, v = k.son, w = k.agirlik;
      if (uzaklik[u] != SONSUZ
          && uzaklik[u] + w < uzaklik[v]) {
        uzaklik[v] = uzaklik[u] + w;
        onceki[v] = u;
      }
    }
  }
  for (Kenar k : kenarlar) { // denetim
    int u = k.bas, v = k.son, w = k.agirlik;
    if (uzaklik[u] != SONSUZ
        && uzaklik[u] + w < uzaklik[v])
      throw new IllegalStateException(
          "Negatif döngü");
  }
}

• Satır 2–5: Diziler oluşturulur, uzaklıklar sonsuzla doldurulur ve kaynağınki 0 yapılır.
• Satır 6: i 1'den V − 1'e kadar döner; toplam V − 1 tur.
• Satır 7–13: Her kenar için u, v ve w alınır ve gevşetme yapılır. Koşulun ilk parçası uzaklik[u] != SONSUZ'dur. uzaklik[u] sonsuzsa toplama hiç yapılmaz.
• Satır 16–21: Denetim turu aynı koşulu sorar. Koşul doğruysa IllegalStateException fırlatılır.

Koşuldaki uzaklik[u] != SONSUZ denetimi süs değildir. SONSUZ burada Integer.MAX_VALUE, yani 2 147 483 647'dir. Java'da bu sayıya pozitif bir şey eklenince sonuç taşar ve negatif bir sayıya döner: Integer.MAX_VALUE + 3 işlemi −2 147 483 646 verir. Denetim olmasaydı ulaşılmamış bir düğümden çıkan kenar, bu negatif sayı yüzünden “daha kısa” görünürdü. Dijkstra'nın kodunda bu denetim gerekmiyordu, çünkü kuyruktan yalnız sonlu uzaklıklı düğümler çıkar. Bellman-Ford ise henüz ulaşılmamış düğümlerin kenarlarını da gevşetmeye çalışır.

Tablo 4.2.14 kodun dört düğümlü bir çizgedeki izlemesidir. Kaynak 0, kenar listesi (2, 1, −2), (0, 1, 4), (0, 2, 5), (1, 3, 3) sırasındadır.

Birinci turda (2, 1) kenarı boşa geçer, çünkü listenin başındadır ve incelendiğinde 2'nin değeri hâlâ ∞'dur. İkinci turda bu kenar işe yarar: negatif ağırlık 1'in değerini 4'ten 3'e indirir. Aynı turun sonunda (1, 3) kenarı bu iyileşmeyi 3'e taşır: 7'den 6'ya. Üçüncü tur hiçbir şeyi değiştirmez ve denetim turu istisna fırlatmaz. Sonuç [0, 3, 5, 6]'dır.

Aynı kod negatif döngülü çizgede çalıştırıldığında farklı biter. S, A, B, C düğümleri 0, 1, 2, 3 numarasını alsın. Kenarlar (0, 1, 2), (1, 2, 1), (2, 3, −3), (3, 1, 1) sırasındadır. Birinci turda dört kenarın dördü de gevşer: A = 2, B = 3, C = 0, sonra A = 1. İkinci ve üçüncü turlarda üçer kenar gevşer; döngüdeki değerler her turda bir azalır. Üç tur sonunda uzaklik = [0, −1, 1, −2]'dir. Denetimde ilk kenar (0, 1) için 0 + 2 = 2, −1'den küçük değildir. İkinci kenar (1, 2) için −1 + 1 = 0 < 1'dir; koşul doğrudur ve IllegalStateException("Negatif döngü") fırlatılır.

4.2.4Floyd-Warshall algoritması

Dijkstra ve Bellman-Ford tek bir kaynaktan çalışır. Bazı uygulamalar ise bütün düğüm çiftleri arasındaki uzaklıkları ister: bir haritadaki bütün şehirler arasındaki mesafe tablosu ya da bir ağdaki bütün yönlendiricilerin birbirine uzaklığı gibi. Floyd-Warshall algoritması bu tüm çiftler problemini tek seferde çözer. Kodu yalnız üç iç içe döngüden oluşur. Negatif kenarlarla çalışır ve negatif döngüyü de tespit eder.

4.2.4.1Tüm çiftler problemi

Algoritmanın tarihi ilginçtir. Bernard Roy 1959'da, Stephen Warshall 1962'de ve Robert Floyd yine 1962'de aynı fikri birbirinden bağımsız olarak yayımladı. Warshall'ın makalesi bir ilişkinin geçişli kapanışını, yani hangi düğümün hangisine ulaşabildiğini hesaplıyordu. Floyd aynı yapıyı en kısa yollara uyguladı. Algoritma bugün ikisinin adıyla anılır.

Floyd-Warshall bir dinamik programlama algoritmasıdır. Sonuçlar V × V boyutlu bir D matrisinde tutulur; D[i][j], i'den j'ye o ana kadar bulunan en kısa uzaklıktır. Yolları geri kurmak için ikinci bir Π matrisi de tutulur. Tek kaynaklı algoritmalardaki π dizisinin her kaynak için ayrı bir satır alan hâlidir.

Algoritma dört adımda çalışır:

1. İlklendirme. D kenar ağırlıklarıyla doldurulur: köşegen D[i][i] = 0, doğrudan kenar yoksa ∞.
2. Ara düğüm. k = 1, 2, …, n sırayla ele alınır. Her k için bütün (i, j) çiftleri gezilir.
3. Karşılaştırma. k üzerinden geçen yolun uzunluğu D[i][k] + D[k][j] hesaplanır ve mevcut D[i][j] ile karşılaştırılır.
4. Güncelleme. Yeni yol daha kısaysa değer matrise yazılır ve Π matrisi de güncellenir.

Üçüncü adımdaki karşılaştırma, gevşetmenin düğüm çiftleri üzerindeki biçimidir. i ⇝ k ve k ⇝ j yolları birleştirilir; ortaya çıkan yol bilinen i ⇝ j yolundan kısaysa onun yerini alır.

4.2.4.2Alt problem ve özyineleme bağıntısı

Dinamik programlamanın ilk işi alt problemi tanımlamaktır. Floyd-Warshall'da alt problem, bir yolun hangi ara düğümleri kullanabileceğini sınırlar. Bir yolun ara düğümleri, başlangıç ve bitiş dışındaki düğümleridir.

D^(k−1) bilindiğinde D^(k) nasıl bulunur? i'den j'ye, ara düğümleri {1, …, k}'dan gelen bir en kısa yol p düşünelim. İki durum vardır.

• k, p üzerinde değildir. O zaman p'nin bütün ara düğümleri {1, …, k − 1}'dendir ve uzunluğu D^(k−1)[i][j]'dir.
• k, p üzerindedir. Negatif döngü yoksa p basit bir yoldur ve k'den yalnız bir kez geçer. p, i ⇝ k ve k ⇝ j parçalarına ayrılır. İki parçanın ara düğümleri de {1, …, k − 1}'dendir. Optimal alt yapı gereği her parça kendi başına en kısadır. Uzunluk D^(k−1)[i][k] + D^(k−1)[k][j]'dir.

En kısa yol bu iki seçenekten küçük olanıdır:

D^(k)[i][j] = min( D^(k−1)[i][j], D^(k−1)[i][k] + D^(k−1)[k][j] )

Bağıntı, k'nin ya yolda olmadığını ya da yolun k'den tam bir kez geçtiğini söyler. Ara düğüm kümesi her adımda bir düğüm büyür: önce yalnız 1 kullanılabilir, sonra 1 ve 2, en sonunda bütün düğümler. n adımın sonunda her çift için bütün olası yollar hesaba katılmış olur.

4.2.4.3Karmaşıklık ve döngü sırası

Algoritmanın süresi kod yapısından okunur. Üç iç içe for döngüsü vardır ve her biri V kez döner. En dış döngü ara düğümleri (k), ikinci döngü kaynak düğümleri (i), en iç döngü hedef düğümleri (j) gezer. En içteki karşılaştırma O(1) sürer ve V³ kez yapılır. Süre çizgenin kenar sayısından bağımsızdır: Θ(V³). Bu, en iyi ve en kötü durumun aynı olduğu, sıkı bir sınırdır.

Bellek Θ(V²)'dir. Bağıntıya bakınca her k için yeni bir matris gerekiyormuş gibi görünür. Gerekmez: D yerinde güncellenebilir. k. turda k. satır ve k. sütun değişmez. Örneğin D[i][k] için aday D[i][k] + D[k][k] = D[i][k] + 0'dır ve mevcut değeri geçemez. Bu turda okunan bütün D[i][k] ve D[k][j] değerleri bu yüzden D^(k−1)'deki değerleriyle aynıdır.

Tablo, Floyd-Warshall'ın her zaman en hızlı seçenek olmadığını gösterir. Seyrek ve negatif kenarsız bir çizgede her düğümden bir kez heap'li Dijkstra çalıştırmak daha hızlıdır. Örneğin V = 200 ve E = 800 için V³ = 8 · 10⁶ iken V(V + E) log₂ V ≈ 1,5 · 10⁶'dır. Floyd-Warshall'ın üstünlüğü başka yerdedir. Negatif kenarlarla çalışır, kodu çok kısadır ve sabit çarpanı küçüktür. Yoğun çizgelerde ve birkaç yüz düğüme kadar olan problemlerde pratik bir seçimdir. Negatif kenarlı bir çizgede V kez Bellman-Ford çalıştırmak ise O(V² E) tutar; yoğun çizgede bu O(V⁴)'tür.

Döngülerin sırası keyfî değildir: k en dışta olmalıdır. Bağıntı D^(k)'yı D^(k−1)'den kurar. k. tur başladığında bütün çiftler {1, …, k − 1} ara düğümleriyle hesaplanmış olmalıdır. Döngüler i, j, k sırasına getirilirse her (i, j) hücresi bir kez, diğer hücreler hazır olmadan hesaplanır.

4.2.4.4Örnek: D ve Π matrisleri

Örnek çizge, Dijkstra Örnek 2 ve Bellman-Ford Örnek 3'te kullanılan beş düğümlü yönlü çizgedir. Bu kez bir kaynak seçilmez; bütün çiftler hesaplanır. Π matrisinde Π[i][j], i'den j'ye en kısa yolda j'den önceki düğümdür. Başlangıçta doğrudan kenar varsa Π[i][j] = i, yoksa “/” yazılır.

Ara düğümler sırayla eklendikçe matris değişir. Her turda değişen hücreler aşağıda listelenmiştir.

• k = 1. 1'e gelen tek kenar 2 → 1'dir; bu yüzden yalnız 2. satır değişebilir. 2 ⇝ 3: D[2][1] + D[1][3] = 3 + 6 = 9. 2 ⇝ 4: 3 + 3 = 6. İki hücrenin Π değeri Π[1][j] = 1 olur.
• k = 2. 2'ye gelen kenarlar 4'ten ve 5'ten gelir. 4 ⇝ 1: 1 + 3 = 4. 5 ⇝ 1: 4 + 3 = 7. 5 ⇝ 3: 4 + 9 = 13. Son hücre, bir önceki turda bulunan 2 ⇝ 3 yolunu kullanır; bu yol zaten 1 üzerinden geçer. Böylece 5 ⇝ 3 yolu iki ara düğüm kullanır: 5 → 2 → 1 → 3.
• k = 3. 3'ten çıkan tek kenar 3 → 4'tür ve 3 üzerinden hiçbir yol kısalmaz.
• k = 4. 4 çizgenin merkezidir; sekiz hücre kısalır: 1 ⇝ 2 (4), 1 ⇝ 3 (6 → 4), 2 ⇝ 3 (9 → 7), 3 ⇝ 1 (6), 3 ⇝ 2 (3), 5 ⇝ 1 (7 → 6), 5 ⇝ 2 (4 → 3), 5 ⇝ 3 (13 → 3). Örneğin 5 ⇝ 3 için D[5][4] + D[4][3] = 2 + 1 = 3 < 13'tür.
• k = 5. 5'e hiçbir kenar gelmez; bütün i ≠ 5 için D[i][5] = ∞'dur. 5 üzerinden hiçbir yol kısalmaz.

Son matristen birkaç sonuç okunur. 5. sütun 5'in kendisi dışında baştan sona ∞'dur: 5'e hiçbir düğümden ulaşılamaz. 5. satır [6, 3, 3, 2, 0]'dır. Bu, Dijkstra'nın ve Bellman-Ford'un kaynak 5 için bulduğu uzaklık dizisinin tıpatıp aynısıdır. Floyd-Warshall bir kaynak seçmeden çalıştığı hâlde, matrisin her satırı o satırdaki düğümün tek kaynaklı sonucunu verir. Köşegenin hepsi 0'dır; negatif döngü yoktur.

4.2.4.5Yolun okunması

Π[i][j], i ⇝ j en kısa yolunda j'den önceki düğümdür. Yol, tek kaynaklı durumdaki gibi hedeften geriye okunur. Fark, bütün okumanın i. satırda yapılmasıdır: j'den önceki düğüm Π[i][j], ondan önceki Π[i][Π[i][j]], ve böyle sürer.

Π güncellemesinin kuralı da buradan anlaşılır. k üzerinden daha kısa bir yol bulunduğunda Π[i][j] ← Π[k][j] yapılır. Yeni yolun son parçası k ⇝ j yoludur. Bu yüzden j'den önceki düğüm, k ⇝ j yolunda j'den önceki düğümle aynıdır. Π[i][j] ← k yazmak yanlış olurdu; k, j'ye doğrudan bağlı olmayabilir.

4.2.4.6Sözde kod, Java kodu ve izleme

Sözde kod iki bölümdür. Birinci bölüm matrisi ilklendirir.

FLOYD_WARSHALL(G):
  mesafeler = [ ][ ]
  her bir u için V içinde:
    her bir v için V içinde:
      eğer u == v:
        mesafeler[u][v] = 0
      yoksa eğer (u, v) E içinde:
        mesafeler[u][v] = ağırlık(u, v)
      yoksa:
        mesafeler[u][v] = sonsuz

İkinci bölüm üç iç içe döngüdür; ardından köşegen denetlenir.

  her bir k için V içinde:
    her bir i için V içinde:
      her bir j için V içinde:
        eğer m[i][k] + m[k][j] < m[i][j]:
          m[i][j] = m[i][k] + m[k][j]
  her bir i için V içinde:
    eğer mesafeler[i][i] < 0:
      hata "Negatif ağırlıklı döngü var"
  döndür mesafeler

Negatif döngü denetimi Bellman-Ford'unkinden daha basittir. Negatif bir döngü üzerindeki bir i düğümü, döngüyü dolaşarak kendine negatif uzunlukta bir yol bulur. Algoritma bu yolu da hesaplar ve D[i][i] 0'ın altına iner. Bu yüzden köşegende negatif bir değer görülmesi negatif döngünün işaretidir.

Java kodunda matris yerinde güncellenir; ayrı bir D^(k) kopyası tutulmaz. onceki matrisi sınıfın bir alanıdır ve başlangıçta onceki[i][j] = i değerlerini taşır.

void floydWarshall(int[][] d) {  // V x V
  for (int k = 0; k < V; k++)       // ara
    for (int i = 0; i < V; i++)     // kaynak
      for (int j = 0; j < V; j++)   // hedef
        if (d[i][k] != SONSUZ
            && d[k][j] != SONSUZ
            && d[i][k] + d[k][j] < d[i][j]) {
          d[i][j] = d[i][k] + d[k][j];
          onceki[i][j] = onceki[k][j];
        }
  for (int i = 0; i < V; i++)
    if (d[i][i] < 0)
      throw new IllegalStateException(
          "Negatif döngü");
}

• Satır 2–4: Üç döngü; açıklamalar her döngünün rolünü yazar: ara, kaynak, hedef.
• Satır 5–7: Önce iki parçanın da sonlu olduğu denetlenir. SONSUZ Integer.MAX_VALUE olduğu için iki sonsuzun ya da sonsuzla bir sayının toplamı taşar ve negatif bir sayıya dönebilir. Denetim bu taşmayı önler.
• Satır 8–9: Yeni uzunluk yazılır. onceki[i][j] = onceki[k][j]: yeni yolda j'den önceki düğüm, k ⇝ j yolundakiyle aynıdır.
• Satır 11–14: Köşegende negatif değer varsa istisna fırlatılır.

Kod dört düğümlü bir çizgede izlenir. Düğümler 0–3 numaralıdır. Kenarlar 0 → 1 (3), 0 → 3 (7), 1 → 0 (8), 1 → 2 (2), 2 → 0 (5), 2 → 3 (1), 3 → 0 (2)'dir.

On bir hücre değişir. Bazı hücreler birden çok kez kısalır: d[1][0] önce 8'dir, k = 2'de 7'ye, k = 3'te 5'e iner. Son yol 1 → 2 → 3 → 0 yoludur ve 2 + 1 + 2 = 5 tutar. d[1][3] ise önce 15 olur, sonra 3'e düşer. 0 üzerinden bulunan uzun yol, 2 eklenince yerini çok daha kısa bir yola bırakır.

Dört tur bittiğinde köşegende negatif değer yoktur ve istisna fırlatılmaz. Yolu okumak için yine onceki kullanılır. 1 ⇝ 3: onceki[1][3] = 2, onceki[1][2] = 1. Yol 1 → 2 → 3, uzunluğu d[1][3] = 3'tür. Sonuç matrisi d = [[0, 3, 5, 6], [5, 0, 2, 3], [3, 6, 0, 1], [2, 5, 7, 0]]'dir.

Floyd-Warshall'ın yapısı en kısa yol dışında da kullanılır. Ağırlıklar yerine yalnız “kenar var mı?” bilgisi tutulursa, toplama yerine “ve”, en küçük yerine “veya” yazılır. Ortaya çıkan algoritma, Warshall'ın asıl problemi olan geçişli kapanışı (transitive closure) hesaplar: t[i][j], i'den j'ye bir yol olup olmadığını söyler.

boolean[][] kapanis(boolean[][] t) {
  int V = t.length;
  for (int k = 0; k < V; k++)
    for (int i = 0; i < V; i++)
      for (int j = 0; j < V; j++)
        t[i][j] = t[i][j] || (t[i][k] && t[k][j]);
  return t;
}

Kod yine Θ(V³) sürer ve k yine en dışta durur. Kenarları 0 → 1, 1 → 2, 2 → 0 ve 3 → 2 olan dört düğümlü bir çizgede bütün satırlar 1110 çıkar. 0, 1 ve 2 aynı döngüdedir ve birbirine ulaşır. 3 de 2 üzerinden bu döngüye girer. 3'e ise hiçbir düğümden ulaşılamaz; bu yüzden son sütun baştan sona 0'dır.

4.2.5A* arama

Dijkstra kaynaktan her yöne eşit hızla yayılır. Yalnız tek bir hedefe gidilecekse bu yayılmanın büyük kısmı boşa gider. İstanbul'dan Ankara'ya yol arayan bir Dijkstra, Edirne'ye ve Bursa'ya giden yolları da Ankara'yı bulana kadar inceler. A* (A yıldız) araması bu israfı azaltır. Her düğüm için hedefe ne kadar kaldığını tahmin eder ve aramayı hedefe doğru yöneltir.

Peter Hart, Nils Nilsson ve Bertram Raphael A*'ı 1968'de Stanford Araştırma Enstitüsü'nde geliştirdi. Amaçları, gezgin bir robotun yolunu planlamaktı. Bugün oyunlarda karakterlerin yol bulmasında, harita uygulamalarında ve robotikte en çok kullanılan arama yöntemlerinden biridir.

4.2.5.1f = g + h

A*, iki aramanın güçlü yanlarını birleştirir. Dijkstra (yapay zekâ kitaplarında düzgün maliyetli arama diye de geçer) yalnız kaynaktan gelinen gerçek maliyete bakar. Bu yüzden doğrudur, ama hedefin nerede olduğunu bilmez. Açgözlü en iyi ilk arama (greedy best-first search) ise yalnız hedefe kalan tahmini maliyete bakar. Hedefe hızla koşar, ama gelinen yolun pahalı olup olmadığını önemsemez. A* her düğüm için üç değer kullanır:

• g(n), gerçek maliyet: başlangıç düğümünden n'ye kadar bulunan yolun maliyetidir. Dijkstra'daki d[n] ile aynıdır.
• h(n), sezgisel tahmin: n'den hedefe kalan maliyetin tahminidir. Haritada kuş uçuşu uzaklık, ızgarada Manhattan uzaklığı böyle tahminlerdir.
• f(n) = g(n) + h(n): n üzerinden geçen bir çözümün tahmini toplam maliyetidir. A* her adımda f değeri en küçük olan düğümü genişletir.

Toplamın işe yarama nedeni şudur. Hedefe yakın görünen düğümlerin h değeri küçüktür ve bunlar öne geçer. Ama pahalı bir yoldan gelinmişse g büyüktür ve düğüm geri planda kalır. İki terim birbirini dengeler: biri “hedefe ne kadar kaldı?”, öteki “buraya kaça geldik?” sorusunu cevaplar.

4.2.5.2Algoritmanın adımları

A* iki liste kullanır. Açık liste (open list), keşfedilmiş ama henüz genişletilmemiş düğümleri tutan bir öncelikli kuyruktur. Kapalı liste (closed list), genişletilmiş düğümleri tutar. Bir düğümü genişletmek, onu açık listeden çıkarıp komşularını incelemek demektir.

1. Başlangıç düğümünün g değeri 0 yapılır ve düğüm açık listeye eklenir. Diğer düğümlerin g değeri ∞'dur.
2. Açık listeden f = g + h değeri en küçük düğüm çıkarılır ve kapalı listeye konur. Seçim ölçütü g ya da h tek başına değil, toplamlarıdır.
3. Çıkarılan düğüm hedefse çözüm bulunmuştur; yol önceki işaretçileriyle geri kurulur. Hedef açık listeye eklendiği anda değil, oradan çıkarıldığı anda kesinleşir.
4. Değilse her komşu v için g' = g(u) + w(u, v) hesaplanır. g' daha küçükse g, f ve önceki değerleri güncellenir ve komşu açık listeye eklenir. Bu, Dijkstra'daki gevşetmenin aynısıdır.
5. İkinci adıma dönülür. Açık liste boşalırsa hedefe yol yoktur.

İkinci adımda seçim, açık listenin tamamından yapılır; yalnız son genişletilen düğümün komşularından yapılmaz. A* bu sayede bir kolda ilerlerken o kol pahalılaşırsa başka bir kola geçebilir. Çizge örneğinde tam olarak bu olur.

4.2.5.3Sezgisel fonksiyonun özellikleri

A*'ın en kısa yolu bulup bulmayacağı sezgisele bağlıdır. İki özellik önemlidir.

Tutarlılık daha güçlü bir özelliktir. Tutarlı bir sezgisel her zaman kabul edilebilirdir. Tutarlı h ile bir düğüm kapalı listeye girdiğinde g değeri kesinleşir ve düğüm bir daha açılmaz. Bu, Dijkstra'daki kesinleşmenin tam karşılığıdır. Gerçekten de tutarlı bir h ile A*, kenar ağırlıkları w(u, v) − h(u) + h(v) ≥ 0 olan bir çizgede çalışan Dijkstra'dır. Kabul edilebilir ama tutarsız bir sezgiselde ise bir düğüm sonradan daha ucuz bir yolla yeniden açılabilir.

Izgara üzerindeki aramalarda yaygın sezgiseller hareket kuralına göre seçilir:

• 4 yönlü hareket (yukarı, aşağı, sağ, sol; her adım 1): Manhattan uzaklığı |Δx| + |Δy|. Her adım bu toplamı en çok 1 azaltır; bu yüzden h ≤ h*'dır.
• 8 yönlü hareket (düz adım 10, çapraz adım 14): oktil uzaklık (octile distance) 14 · min(|Δx|, |Δy|) + 10 · (max − min). Önce mümkün olduğu kadar çapraz, sonra düz gidilir. 14, 10 · √2 ≈ 14,14 değerinin tam sayıya yuvarlanmış hâlidir.
• Serbest düzlem: Öklid uzaklığı √(Δx² + Δy²), yani kuş uçuşu.

Manhattan uzaklığı 8 yönlü harekette kabul edilebilir değildir. Çapraz bir adım |Δx| + |Δy| toplamını 2 azaltır, ama maliyeti yalnız 1'dir (ya da 1,4'tür). Örneğin Δx = Δy = 3 olan bir hedef için Manhattan uzaklığı 6'dır. Her adımı 1 olan 8 yönlü ızgarada gerçek kalan maliyet ise üç çapraz adımla yalnız 3'tür. Sezgisel gerçek değeri iki katına çıkarır.

Sezgiselin kalitesi iki uç durumla anlaşılır. h = 0 alınırsa f = g olur ve A* tam olarak Dijkstra'ya dönüşür. Bu sezgisel kabul edilebilirdir, ama aramayı hiç yönlendirmez. h = h* (mükemmel tahmin) alınırsa en kısa yol üzerindeki her düğümün f değeri h*(s)'ye eşit olur. Yol dışındaki düğümlerin f'si ise daha büyüktür. Eşitlikler uygun biçimde bozulursa yalnız yol üzerindeki düğümler açılır. h > h* olan, yani fazla tahmin eden bir sezgisel aramayı hızlandırabilir, ama en kısa yol garantisini kaldırır.

4.2.5.4Karmaşıklık

A*'ın maliyeti arama ağacı üzerinden anlatılır. b dallanma faktörü, yani bir düğümün ortalama komşu sayısı olsun. d ise hedefin derinliği, yani çözümdeki adım sayısı olsun. En kötü durumda arama, derinliği d'ye kadar olan bütün düğümleri açar. Zaman ve bellek bu yüzden O(b^d)'dir. Bu sınır işe yaramayan bir sezgiselin, örneğin h = 0'ın sınırıdır. Mükemmel bir tahminde arama yol uzunluğuyla doğrusaldır: yalnız yol üzerindeki d düğüm genişletilir.

Sonlu bir çizgede tutarlı bir h ile A*, Dijkstra'dan fazla iş yapmaz. Her düğüm en çok bir kez genişletilir ve toplam süre ikili heap ile O((V + E) log V)'dir. Pratikte iyi bir sezgisel bu sınırın çok altında kalır, çünkü hedefin ters yönündeki düğümler hiç açılmaz.

A*'ın asıl zayıf noktası bellektir. Açık ve kapalı listeler aramayla birlikte büyür ve büyük haritalarda belleği doldurabilir. Bu sorunu çözmek için bellek sınırlı türevler geliştirilmiştir. IDA* (iterative deepening A*), derinlik öncelikli aramayı artan bir f sınırıyla tekrarlar ve yalnız o anki yolu bellekte tutar. SMA* (simplified memory-bounded A*) ise bellek dolunca en kötü görünen düğümleri listeden atar.

4.2.5.5Örnek: çizgede A*

Örnek yönsüz bir çizgedir; başlangıç s, hedef t'dir. Kenarlar: s–a 1,5; s–d 2; a–b 2; b–c 3; c–t 4; d–e 3; e–t 2. Sezgisel değerler: h(s) = 5, h(a) = 4, h(b) = 2, h(c) = 4, h(d) = 4,5, h(e) = 2, h(t) = 0.

Arama önce üst kola yönelir. a'nın f değeri 5,5 ile en küçüktür, ardından b de 5,5 ile öne çıkar. b genişletilince c açılır, ama c'nin g değeri 6,5'e çıkmıştır ve f(c) = 10,5 olur. Bu kol pahalılaşmıştır. Açık listede en küçük f artık d'nindir (6,5) ve arama alt kola geçer. Bu geçiş, seçimin açık listenin tamamından yapılmasının sonucudur. d'den e açılır (f = 7), e'den t açılır (g = 7, f = 7).

t açık listeden çıkarıldığında arama durur. En kısa yol s → d → e → t, maliyeti 2 + 3 + 2 = 7'dir. Üst kol s → a → b → c → t ise 1,5 + 2 + 3 + 4 = 10,5 tutar. c açılmış ama hiç genişletilmemiştir. Yedi düğümden altısı genişletilmiştir. Dijkstra aynı çizgede uzaklık sırasıyla s, a, d, b, e, c, t düğümlerini genişletirdi; c'nin uzaklığı (6,5) t'ninkinden (7) küçük olduğu için c'yi de açardı.

4.2.5.6Java kodu ve izleme

A*'ın Java kodu Dijkstra'nınkine çok benzer. Farklar iki yerdedir: kuyruk g + h'ye göre sıralanır ve hedef çıkarıldığında arama durur. g, h ve ata sınıf alanlarıdır; g ve h double dizileridir. komsu[u], u'nun kenar listesidir ve her kenarın v (komşu) ile w (ağırlık) alanları vardır.

double aYildiz(int s, int t) {
  Arrays.fill(g, SONSUZ); g[s] = 0;
  Queue<Integer> acik = new PriorityQueue<>(
    Comparator.comparingDouble(v -> g[v] + h[v]));
  acik.add(s);
  while (!acik.isEmpty()) {
    int u = acik.poll();      // en küçük f
    if (u == t) return g[t];  // hedef
    for (Kenar k : komsu[u])
      if (g[u] + k.w < g[k.v]) {
        g[k.v] = g[u] + k.w; ata[k.v] = u;
        acik.remove(k.v); acik.add(k.v);
      }
  }
  return SONSUZ;
}

• Satır 2: Bütün g değerleri sonsuz, başlangıcınki 0 yapılır.
• Satır 3–5: Açık liste bir öncelikli kuyruktur. Karşılaştırıcı her v düğümünü g[v] + h[v] değerine göre sıralar. Başta yalnız s vardır.
• Satır 7–8: En küçük f'li düğüm çıkarılır. Hedefse g[t] döndürülür. Durma koşulu çıkarma anındadır.
• Satır 9–13: Her kenar gevşetilir. g küçülürse önceki düğüm ata'ya yazılır. Düğüm önce kuyruktan silinir, sonra yeniden eklenir.
• Satır 15: Kuyruk boşalırsa hedefe yol yoktur.

On ikinci satırdaki remove ve add çifti önemlidir. Karşılaştırıcı g[v] dizisini okur. Bir düğüm kuyruktayken g[v] değişirse heap'in sıralama düzeni bozulur, çünkü heap düğümün yerini eski değere göre belirlemiştir. Düğümü çıkarıp yeniden eklemek, onu yeni değerine göre doğru yere koyar. PriorityQueue.remove(Object) doğrusal zaman alır; büyük çizgelerde Dijkstra'daki gibi tembel silme tercih edilir.

Kod, A* örneğindeki çizgede çalıştırıldığında poll() sırası s (f = 5), a (5,5), b (5,5), d (6,5), e (7), t (7) olur. Her adımdaki g güncellemeleri Tablo 4.2.20'deki değerlerle aynıdır. Altıncı çağrıda hedef çıkar ve return g[t] 7 döndürür. ata dizisi geriye okunursa t ← e ← d ← s, yani s → d → e → t elde edilir. c açık listede f = 10,5 ile kalır ve hiç çıkarılmaz.

4.2.5.7Örnek: ızgarada duvarın çevresinden

A*'ın en tanıdık kullanımı ızgara haritalardır. Örnekte 8 sütun ve 7 satırdan oluşan bir ızgara vardır. Başlangıç A, hedef B'dir. Aralarında ters L biçiminde bir duvar durur. Hareket 8 yönlüdür: düz adım 10, çapraz adım 14 maliyetlidir. Sezgisel oktil uzaklıktır ve duvarları yok sayar. A'dan B'ye 3 sütun ve 3 satır fark vardır; h(A) = 3 · 14 = 42'dir.

Şekillerde her hücrede üç sayı yazılıdır: sol üstte g, sağ üstte h, ortada f.

Arama önce duvarın hemen altına, B'nin doğrultusuna yönelir. Sezgisel duvarı görmediği için bu hücreler en umut verici görünür. Genişletilen hücrelerin f değerleri sırasıyla şöyledir:

42, 42, 48, 48, 48, 54, 54, 60, 62, 62, 62, 62, 68, 68, 68, 68, 68, 68

Değerler hiç azalmaz. Bu, tutarlı bir sezgiselin bir özelliğidir: genişletilen düğümlerin f değerleri azalmayan bir dizi oluşturur. Duvarın altındaki yol tıkalıdır; duvarın üstüne çıkmak için ya sağdan ya soldan dolaşmak gerekir. Dolaşma maliyeti tahminde yoktur ve f adım adım yükselir. On üçüncü genişletmede f = 68'e ulaşılır ve arama duvarın iki yanına yayılır. On yedinci genişletmede duvarın sağından dolaşan yol B'ye ulaşır; B açık listeye f = 68 ile girer.

B on sekizinci genişletmede çıkarılır ve arama durur. Bulunan yolun maliyeti 68'dir: iki çapraz adım (28) ve dört düz adım (40). On sekiz genişletmenin on biri kapalı (pembe) hücrelerdir, yedisi yol üzerindeki hücrelerdir. Duvarın solundan dolaşan en ucuz yol 96 tutar. A* bu yöndeki en soldaki sütunun hücrelerini açmış, ama hiçbirini genişletmemiştir. Izgaranın köşelerindeki birkaç hücre ise hiç açılmamıştır.

Örnekte çapraz adımlar duvarın köşesini sıyırabilir. Yolun iki çapraz adımı da bir duvar hücresinin köşesinden geçer. Birçok oyunda bu “köşe kesme” yasaktır: çapraz adım ancak iki yandaki düz komşu da boşsa yapılabilir. Böyle bir kural aramanın sonucunu değiştirebilir, ama A*'ın işleyişini değiştirmez.

4.2.6Ağırlıksız çizgede en kısa yol: BFS

Bütün kenarların ağırlığı eşitse, örneğin hepsi 1 ise, bir yolun uzunluğu kenar sayısına eşittir. En kısa yol en az kenarlı yol olur. Bu özel durumda ağır algoritmalara gerek yoktur. Genişlik öncelikli arama (breadth-first search, BFS) problemi doğrusal zamanda çözer.

BFS düğümleri kaynağa uzaklık sırasıyla, katman katman ziyaret eder. Önce kaynağın komşuları (uzaklık 1), sonra onların ziyaret edilmemiş komşuları (uzaklık 2) gelir ve böyle sürer. Bir v düğümü ilk kez u'dan bulunduğunda d[v] = d[u] + 1 ve π[v] = u yazılır. Düğüm ilk bulunduğu anda en kısa uzaklığına ulaşmıştır; sonra bulunan yollar daha uzun olamaz.

BFS'nin Dijkstra'yla ilişkisi açıktır. Dijkstra öncelikli kuyrukla en küçük uzaklıklı düğümü seçer. Ağırlıklar eşitken düğümler kuyruğa uzaklık sırasıyla girer. İlk giren ilk çıkar (FIFO) ilkesiyle çalışan sıradan bir kuyruk bu sırayı zaten korur ve öncelikli kuyruğa gerek kalmaz. Kuyruk işlemleri O(1) olduğu için toplam süre O(V + E)'dir; heap'in log V çarpanı ortadan kalkar.

Şekildeki çizgede kenarlar 0–1, 0–2, 0–7, 1–2, 2–3, 2–4, 3–5, 4–6 ve 5–6'dır. 0'ın komşuları 1, 2 ve 7 birinci seviyededir. 2'nin komşuları 3 ve 4 ikinci seviyededir. 3'ün komşusu 5 ve 4'ün komşusu 6 üçüncü seviyededir. 6'ya giden bir başka yol 0 → 2 → 3 → 5 → 6'dır, ama dört kenarlıdır. BFS 6'yı ilk kez 4'ten bulur ve π[6] = 4 yazar; 5'ten gelen yol daha sonra görülür ve bir şey değiştirmez.

Bütün kenarların ağırlığı aynı sabit c ise de BFS yeterlidir. Uzaklıklar seviyelerin c katıdır. Örneğin bütün kenarları 5 olan aynı çizgede 6'nın uzaklığı 3 · 5 = 15'tir. Ağırlıklar farklıysa BFS yanılır; en az kenarlı yol en kısa yol olmayabilir.

Tek bir hedef varsa BFS'nin bir türevi daha hızlıdır. İki yönlü arama (bidirectional search), BFS'yi aynı anda hem kaynaktan hem hedeften başlatır. İki dalga ortada buluştuğunda arama durur. Dallanma faktörü b ve hedef derinliği d olan bir aramada tek yönlü BFS yaklaşık b^d düğüm açar. İki yönlü arama ise yaklaşık 2 · b^d/2 düğüm açar. b = 10 ve d = 6 için bu, bir milyon düğüm yerine iki bin düğüm demektir.

4.2.7Karşılaştırma ve algoritma seçimi

Bölümdeki beş algoritma aynı temel işlemi, gevşetmeyi kullanır. Farkları, hangi problemi çözdüklerinde, hangi kısıtları kabul ettiklerinde ve ne kadar sürdüklerindedir. Tablo 4.2.21 bu farkları tek tabloda toplar.

Seçim birkaç soruyla yapılır:

1. Çizge ağırlıksız mı? BFS yeterlidir.
2. Ağırlıkların hepsi sıfır ya da pozitif mi? Dijkstra kullanılır. Hedef tek ve iyi bir sezgisel varsa A* daha az düğüm açar.
3. Negatif kenar var mı? Bellman-Ford kullanılır; negatif döngü de böylece denetlenir.
4. Tüm çiftler mi isteniyor ve V küçük mü? Floyd-Warshall kullanılır.

4.2.8Sık yapılan hatalar

Bölüm boyunca kutularda verilen hataların en önemlileri burada bir arada toplanmıştır.

• Negatif kenarda Dijkstra. Kesinleşmiş bir düğüme sonradan daha kısa yol açılabilir; sonuç hiçbir uyarı olmadan yanlış çıkar. Negatif kenarda Bellman-Ford gerekir. Ağırlıklara sabit eklemek de çözüm değildir; çok kenarlı yollar daha fazla ceza alır.
• ∞ + w taşması. Integer.MAX_VALUE + w negatif bir sayıya döner ve “daha kısa” görünür. Bu yüzden toplamadan önce d[u] != SONSUZ denetlenir. Floyd-Warshall'da iki parçanın ikisi de denetlenmelidir.
• Floyd-Warshall döngü sırası. k ara düğüm döngüsü en dışta olmalıdır. i, j, k sırası bazı hücreleri ∞ ya da gereğinden büyük bırakır.
• Tur sayısı. Bellman-Ford'da V − 1 turun hepsi gerekebilir; iş tek turda bitmeyebilir. Denetim turu bu turlardan ayrıdır.
• A*'da hedefte durmak. Hedef açık listeye eklendiğinde değil, listeden çıkarıldığında durulur. Fazla tahmin eden bir h en kısa yolu kaçırabilir.
• Yönsüz kenarda negatif ağırlık. Yönsüz bir negatif kenar, u → v → u yoluyla kendi başına negatif bir döngüdür. Yönsüz çizgede negatif ağırlık varsa en kısa yol tanımsızdır.
• Ulaşılamayan hedefte yol yazdırmak. Önceki dizisi kaynağa hiç ulaşmaz. Önce uzaklığın sonlu olduğu denetlenmelidir.

4.2.9Özet

• Ağırlıklı bir çizgede yolun uzunluğu kenar ağırlıklarının toplamıdır. En kısa yol, en az kenarlı yol olmak zorunda değildir. δ(s, v), s'den v'ye en kısa yolun uzunluğudur.
• Üç problem türü vardır: tek kaynaklı (Dijkstra, Bellman-Ford, BFS), tüm çiftler (Floyd-Warshall) ve tek çift (A*).
• Bütün algoritmaların ortak işlemi gevşetmedir: d[u] + w(u, v) < d[v] ise d[v] ve π[v] güncellenir. Tahmin yalnız azalır ve gerçek uzaklığın altına inmez.
• En kısa yolların her parçası da en kısadır (optimal alt yapı). Negatif döngü yoksa en kısa yol en çok V − 1 kenarlıdır. Ulaşılabilir bir negatif döngü varsa en kısa yol tanımsızdır.
• Dijkstra en küçük tahminli düğümü kesinleştirir ve komşularını gevşetir. Ağırlıklar negatif olmamalıdır. Dizi ile O(V²), ikili heap ile O((V + E) log V) sürer. Tembel silmeli kuyruk eski kayıtları ziyaret denetimiyle atlar.
• Bellman-Ford bütün kenarları V − 1 tur gevşetir. Negatif kenarla çalışır; V. turda hâlâ gevşeyen kenar negatif döngüyü gösterir. Süre O(V · E)'dir; erken durmayla en iyi durum O(E)'dir.
• Floyd-Warshall D[i][j] = min(D[i][j], D[i][k] + D[k][j]) bağıntısını k en dışta olacak biçimde uygular. Süre Θ(V³), bellek Θ(V²)'dir. D[i][i] < 0 negatif döngüyü gösterir.
• A* f = g + h değeri en küçük düğümü genişletir. Kabul edilebilir h ile en kısa yolu bulur; tutarlı h ile her düğüm bir kez genişletilir. h = 0 alınırsa A* Dijkstra'ya dönüşür.
• Ağırlıksız çizgede BFS en az kenarlı yolu O(V + E) sürede bulur.
• Yollar π (ya da Π) işaretçileriyle hedeften geriye okunur; işaretçiler birlikte en kısa yol ağacını oluşturur.

4.2.10Kavram listesi

• en kısa yol shortest path
• uzaklık distance
• ağırlıklı çizge weighted graph
• tek kaynaklı en kısa yollar single-source shortest paths
• tüm çiftler en kısa yolları all-pairs shortest paths
• gevşetme relaxation
• optimal alt yapı optimal substructure
• negatif döngü negative cycle
• Dijkstra algoritması Dijkstra's algorithm
• öncelikli kuyruk priority queue
• açgözlü algoritma greedy algorithm
• Bellman-Ford algoritması Bellman-Ford algorithm
• dinamik programlama dynamic programming
• Floyd-Warshall algoritması Floyd-Warshall algorithm
• A* algoritması A* search
• sezgisel heuristic
• kabul edilebilir sezgisel admissible heuristic
• genişlik öncelikli arama breadth-first search (BFS)

4.2.11Kendini Dene

1. Yönlü çizge: s → a 2, s → b 6, a → b 3, a → c 7, b → c 1, c → t 2, b → t 8. Kaynak s. Dijkstra düğümleri hangi sırayla kesinleştirir? Son uzaklıklar ve s'den t'ye yol nedir?

   Cevap

   Sıra s, a, b, c, t. a = 2; b önce 6 olur, a üzerinden 2 + 3 = 5'e iner; c = 5 + 1 = 6 (a üzerinden 9 olurdu); t = 6 + 2 = 8 (b'den doğrudan 13 olurdu). Yol s → a → b → c → t, uzunluk 8.

2. Dizi ile seçim yapan Dijkstra ve ikili heap'li Dijkstra, V = 10⁵ ve E = 4 · 10⁵ olan bir çizgede yaklaşık kaç işlem yapar? Bellman-Ford kaç gevşetme denemesi yapar?

   Cevap

   Dizi: V² = 10¹⁰. Heap: (V + E) log₂ V ≈ 5 · 10⁵ · 16,6 ≈ 8,3 · 10⁶. Bellman-Ford: V · E = 4 · 10¹⁰. Çizge seyrek olduğu için heap'li Dijkstra açık ara en hızlısıdır.

3. Zincir çizge s → a → b → c, bütün ağırlıklar 1. Erken durmalı Bellman-Ford kenarları (a) (b, c), (a, b), (s, a) sırasıyla, (b) (s, a), (a, b), (b, c) sırasıyla incelerse kaç tur döner?

   Cevap

   (a) Her tur yalnız bir kenar ilerler: 1. turda a, 2. turda b, 3. turda c bulunur. V − 1 = 3 turun hepsi kullanılır. (b) 1. turda üçü birden bulunur; 2. turda hiçbir şey değişmez ve algoritma durur: 2 tur. Sonuç ikisinde de [0, 1, 2, 3]'tür.

4. Floyd-Warshall, kenarları 0 → 1 (4), 1 → 2 (2), 2 → 0 (1) olan çizgede çalıştırılıyor. k = 0 turundan sonra hangi hücre değişir? Son D matrisi nedir?

   Cevap

   k = 0: 0'a gelen kenar yalnız 2 → 0'dır; D[2][1] = 1 + 4 = 5. k = 1: D[0][2] = 4 + 2 = 6. k = 2: D[1][0] = 2 + 1 = 3. Son matris [[0, 4, 6], [3, 0, 2], [1, 5, 0]]. Köşegen 0, döngünün ağırlığı 7'dir.

5. Floyd-Warshall, kenarları 0 → 1 (1), 1 → 2 (−2), 2 → 0 (−1), 0 → 2 (4) olan çizgede çalıştırılıyor. Köşegende ne görülür? Kod ne yapar?

   Cevap

   0 → 1 → 2 → 0 döngüsünün ağırlığı 1 − 2 − 1 = −2'dir. Algoritmanın sonunda köşegende negatif değerler çıkar (yerinde güncellemeyle −2, −2 ve −4). d[i][i] < 0 denetimi ilk satırda doğru olur ve IllegalStateException("Negatif döngü") fırlatılır. Matrisin diğer değerleri anlamsızdır.

6. Floyd-Warshall örneğinin son Π matrisinden 3 ⇝ 1 yolu hangisidir? Yolun uzunluğu D[3][1] ile uyuşur mu?

   Cevap

   3. satırda: Π[3][1] = 2, Π[3][2] = 4, Π[3][4] = 3. Yol 3 → 4 → 2 → 1, uzunluk 2 + 1 + 3 = 6 = D[3][1].

7. Zincir s → a → t, w(s, a) = 2, w(a, t) = 5. h(s) = 6, h(a) = 5, h(t) = 0 sezgiseli kabul edilebilir mi, tutarlı mı?

   Cevap

   Gerçek kalanlar h*(s) = 7, h*(a) = 5, h*(t) = 0. 6 ≤ 7, 5 ≤ 5: kabul edilebilir. Tutarlılık: h(s) = 6 ≤ 2 + 5 = 7 ve h(a) = 5 ≤ 5 + 0; ikisi de sağlanır, sezgisel tutarlıdır.

8. Bütün kenar ağırlıkları 5 olan bir çizgede BFS kullanılabilir mi? BFS örneğindeki çizgede 6'nın uzaklığı ne olur?

   Cevap

   Kullanılabilir. Bütün ağırlıklar eşitken en kısa yol yine en az kenarlı yoldur; uzaklık, BFS seviyesinin 5 katıdır. 6 üçüncü seviyededir: 3 · 5 = 15.

9. Dijkstra'nın Java kodunda karşılaştırıcı (a, b) -> a[1] - b[1] biçimindedir. Kuyruğa uzaklığı Integer.MAX_VALUE olan bir kayıt eklenseydi ne olabilirdi?

   Cevap

   Çıkarma taşabilirdi. Örneğin Integer.MAX_VALUE - (-1) negatif bir sayıya döner ve karşılaştırıcı yanlış sırayı bildirir. Sunumdaki kodda kuyruğa yalnız sonlu uzaklıklar eklendiği için sorun çıkmaz. Güvenli yazım Integer.compare(a[1], b[1])'dir.

10. Dijkstra, her düğüme giden en kısa yolların sayısını da tutacak biçimde değiştiriliyor. Kenarları s → a 1, s → b 1, a → c 1, b → c 1, c → t 1, s → t 3, a → t 2 olan çizgede sayi[t] kaçtır?

    Cevap

    d[t] = 3'tür ve dört yol bu uzunluktadır: s → t, s → a → t, s → a → c → t, s → b → c → t. Algoritma sayi[c] = 2 bulur; t'ye s'den 1, a'dan 1, c'den 2 yol gelir: sayi[t] = 4. Kural: daha kısa yol bulununca sayı yeniden başlar (sayi[v] = sayi[u]), eşit uzunlukta yol bulununca eklenir (sayi[v] += sayi[u]).

Son sorudaki kural aşağıdaki kodla uygulanır. Kod seçimi dizi taramasıyla yapar ve Java ile denenmiştir.

long[] yolSayisi(int V, List<List<int[]>> komsu, int kaynak, int[] uzaklik) {
  long[] sayi = new long[V];
  boolean[] kesin = new boolean[V];
  Arrays.fill(uzaklik, SONSUZ);
  uzaklik[kaynak] = 0; sayi[kaynak] = 1;
  for (int tur = 0; tur < V; tur++) {
    int u = -1;
    for (int x = 0; x < V; x++)
      if (!kesin[x] && uzaklik[x] != SONSUZ && (u == -1 || uzaklik[x] < uzaklik[u])) u = x;
    if (u == -1) break;
    kesin[u] = true;
    for (int[] k : komsu.get(u)) {
      int v = k[0], w = k[1];
      if (uzaklik[u] + w < uzaklik[v]) {        // daha kısa yol: sayım yeniden başlar
        uzaklik[v] = uzaklik[u] + w;
        sayi[v] = sayi[u];
      } else if (uzaklik[u] + w == uzaklik[v]) { // eşit uzunlukta yeni yollar
        sayi[v] += sayi[u];
      }
    }
  }
  return sayi;
}

Kural, ağırlıkların pozitif olmasına dayanır. Bir düğüm kesinleştiğinde ona gelen bütün en kısa yollar daha küçük uzaklıklı, yani daha önce kesinleşmiş düğümlerden gelmiştir. Bu yüzden sayi[u], u kesinleştiği anda tamdır ve komşulara doğru değer aktarılır.

4.2.12İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 22 ve 23: gevşetmenin özelliklerini, Dijkstra ve Bellman-Ford'un doğruluk kanıtlarını, Floyd-Warshall'ı ve seyrek çizgeler için Johnson algoritmasını ayrıntılı verir.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 4.4: en kısa yol algoritmalarının Java kodlarını, indeksli öncelikli kuyrukla Dijkstra'yı ve kuyruk tabanlı Bellman-Ford'u anlatır.
• S. Russell ve P. Norvig, Artificial Intelligence: A Modern Approach (4. baskı, 2020), Bölüm 3: A*, kabul edilebilir ve tutarlı sezgiseller, IDA* ve bellek sınırlı arama türevlerini yapay zekâ açısından ele alır.
• E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs” (1959): algoritmanın üç sayfalık özgün makalesidir; aynı makale minimum kapsayan ağaç problemini de çözer.

4.2.13Kaynaklar

1. R. Bellman, “On a Routing Problem”, Quarterly of Applied Mathematics 16, 1958.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 22–23).
3. E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik 1, 1959.
4. R. W. Floyd, “Algorithm 97: Shortest Path”, Communications of the ACM 5(6), 1962.
5. P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics 4(2), 1968.
6. S. Russell, P. Norvig, Artificial Intelligence: A Modern Approach, 4. baskı, Pearson, 2020.
7. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011 (Kesim 4.4: Shortest Paths).
8. S. Warshall, “A Theorem on Boolean Matrices”, Journal of the ACM 9(1), 1962.

İlgili sayfalar: Bölüm 4.2 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.