Bölüm 6: En Kısa Yol Algoritmaları
Giriş
Öğrenme Çıktıları
Tek kaynaklı, tüm çiftler ve tek çift en kısa yol problemlerini ayırt etmek; gevşetme (relaxation) işlemini ve önceki (π) dizisini açıklamak.
İki algoritmayı bir örnek çizge üzerinde adım adım çalıştırmak, uzaklık ve π tablolarını doldurmak, Java kodunu izlemek.
Dijkstra'nın negatif kenarda neden yanıldığını göstermek; Bellman-Ford ve Floyd-Warshall ile negatif döngüyü tespit etmek.
Tüm çiftler için D ve Π matrislerini k = 1…n güncellemek; A*'ın f = g + h ile hedefe yönelen aramasını uygulamak ve algoritmaları karşılaştırmak.
Giriş
Yol Ağı Bir Çizgedir
- Kavşaklar düğüm (vertex), yollar kenar (edge), yol uzunlukları ya da süreleri ağırlık (weight) olur.
- Bir yolun uzunluğu = üzerindeki kenar ağırlıklarının toplamı.
- En kısa yol (shortest path): iki düğüm arasındaki toplam ağırlığı en küçük yol; uzunluğu δ(s, v) ile gösterilir.
- Örnek: Ev → Okul için Ev–1–2–4–Okul = 4 + 2 + 3 + 3 = 12; daha az kenarlı Ev–1–4–Okul ise 13 eder.
Giriş
En Kısa Yol Problem Türleri
| Algoritma | Ne bulur? | Kısıt / not |
|---|---|---|
| Dijkstra | kaynaktan tüm düğümlere | kenar ağırlıkları negatif olmamalı |
| Bellman-Ford | kaynaktan tüm düğümlere | negatif kenarda çalışır, negatif döngüyü bulur; Dijkstra'dan yavaş |
| Floyd-Warshall | tüm çiftler arası | negatif kenarda çalışır; negatif döngüyü köşegenden tespit eder |
| A* | başlangıçtan hedefe | sezgisel (heuristic) tahminle aramayı hızlandırır |
| BFS | kaynaktan tüm düğümlere | yalnızca ağırlıksız (ya da eşit ağırlıklı) çizgeler |
Giriş
Temel İşlem: Gevşetme (Relaxation)
Her düğüm için iki bilgi tutulur:
d[v]: şimdiye kadar bulunan en kısa yol tahmini (başta ∞, kaynakta 0)π[v]: bu yolda v'den önceki düğüm (önceki, predecessor)
RELAX(u, v, w):
eğer d[u] + w(u, v) < d[v]:
d[v] = d[u] + w(u, v)
π[v] = ud[u] + w = 5 + 3 = 8 < 9 → d[v] = 8, π[v] = u
Giriş
En Kısa Yolların Özellikleri
En kısa yolun her alt yolu da en kısa yoldur. s ⇝ u ⇝ v en kısaysa s ⇝ u parçası da en kısadır. Dinamik programlama ve açgözlü yaklaşım buna dayanır.
Her (u, v) kenarı için δ(s, v) ≤ δ(s, u) + w(u, v). Gevşetme bu eşitsizliği bozan kenarları düzeltir.
Toplam ağırlığı negatif olan bir döngü kaynaktan ulaşılabiliyorsa, döngüde dolaştıkça yol kısalır: en kısa yol tanımsızdır (−∞).
Negatif döngü yoksa en kısa yol döngü içermez; en fazla V − 1 kenarlıdır. Bellman-Ford'un V − 1 turu buradan gelir.
Dijkstra
Dijkstra Algoritması
- Kaynak düğümden diğer tüm düğümlere olan en kısa yolları bulur (tek kaynaklı).
- 1956'da Edsger W. Dijkstra tarafından geliştirildi, 1959'da yayımlandı.
- Yalnızca negatif olmayan ağırlıklı kenarlardan oluşan çizgelerde doğru çalışır.
- Açgözlü (greedy): her adımda, henüz kesinleşmemiş düğümler arasından d değeri en küçük olanı seçer ve kesinleştirir.
- Seçilen düğümün komşuları gevşetilir.
Dijkstra
Dijkstra: Algoritma Adımları
Adım 1: Başlangıç düğümü seçilir, uzaklığı 0 atanır; diğer tüm düğümlerin uzaklığı ∞ olur.
İlklendirme: d[s] = 0, d[v] = ∞, π[v] = tanımsız, S = ∅.
Adım 2: Seçilen düğümden başlayarak, henüz işlenmemiş komşulara olan uzaklıklar hesaplanır.
Komşu v için aday uzaklık: d[u] + w(u, v).
Adım 3: Daha kısa bir yol bulunursa komşunun uzaklığı güncellenir (gevşetme).
d[u] + w(u, v) < d[v] ise d[v] ve π[v] değişir.
Adım 4: İşlenen düğüm işaretlenir (S'ye eklenir) ve uzaklığı en küçük işaretsiz düğüm seçilir.
Seçim, dizi ya da öncelikli kuyruk (priority queue) ile yapılır.
Adım 5: Tüm düğümler işlenene kadar Adım 2–4 tekrarlanır.
Ulaşılamayan düğümlerin uzaklığı ∞ olarak kalır.
Dijkstra
Dijkstra Örnek 1: Yönsüz Çizge, Kaynak 1
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | ∞ | – |
| 3 | ∞ | – |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | ∞ | – |
İlklendirme: kaynak 1, d[1] = 0, diğerleri ∞. Hiçbir düğüm kesinleşmedi.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | ∞ | – |
| 3 | ∞ | – |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | ∞ | – |
Kesinleşmemişler içinde en küçük d: 1 (d = 0) seçilir ve kesinleşir.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | ∞ | – |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | ∞ | – |
Kenar (1, 2): d[1] + 7 = 7 < ∞ → d[2] = 7, π[2] = 1.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | ∞ | – |
Kenar (1, 3): d[1] + 9 = 9 < ∞ → d[3] = 9, π[3] = 1.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | 14 | 1 |
Kenar (1, 6): d[1] + 14 = 14 < ∞ → d[6] = 14, π[6] = 1.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | 14 | 1 |
Kesinleşmemişler içinde en küçük d: 2 (d = 7) seçilir ve kesinleşir. Kesinleşmiş komşular (1) atlanır.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | ∞ | – |
| 5 | ∞ | – |
| 6 | 14 | 1 |
Kenar (2, 3): d[2] + 10 = 17 ≥ 9 → değişiklik yok.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 22 | 2 |
| 5 | ∞ | – |
| 6 | 14 | 1 |
Kenar (2, 4): d[2] + 15 = 22 < ∞ → d[4] = 22, π[4] = 2.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 22 | 2 |
| 5 | ∞ | – |
| 6 | 14 | 1 |
Kesinleşmemişler içinde en küçük d: 3 (d = 9) seçilir ve kesinleşir. Kesinleşmiş komşular (1, 2) atlanır.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | ∞ | – |
| 6 | 14 | 1 |
Kenar (3, 4): d[3] + 11 = 20 < 22 → d[4] = 20, π[4] = 3.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | ∞ | – |
| 6 | 11 | 3 |
Kenar (3, 6): d[3] + 2 = 11 < 14 → d[6] = 11, π[6] = 3.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | ∞ | – |
| 6 | 11 | 3 |
Kesinleşmemişler içinde en küçük d: 6 (d = 11) seçilir ve kesinleşir. Kesinleşmiş komşular (1, 3) atlanır.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | 20 | 6 |
| 6 | 11 | 3 |
Kenar (6, 5): d[6] + 9 = 20 < ∞ → d[5] = 20, π[5] = 6.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | 20 | 6 |
| 6 | 11 | 3 |
Kesinleşmemişler içinde en küçük d: 4 (d = 20) seçilir ve kesinleşir. (4 ve 5 eşit: 20; küçük numaralı 4 alındı.) Kesinleşmiş komşular (2, 3) atlanır.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | 20 | 6 |
| 6 | 11 | 3 |
Kenar (4, 5): d[4] + 6 = 26 ≥ 20 → değişiklik yok.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | 20 | 6 |
| 6 | 11 | 3 |
Kesinleşmemişler içinde en küçük d: 5 (d = 20) seçilir ve kesinleşir. Kesinleşmiş komşular (4, 6) atlanır.
| düğüm | d | π |
|---|---|---|
| 1 | 0 | – |
| 2 | 7 | 1 |
| 3 | 9 | 1 |
| 4 | 20 | 3 |
| 5 | 20 | 6 |
| 6 | 11 | 3 |
Bitti: 1'den uzaklıklar 2:7, 3:9, 6:11, 4:20, 5:20. Yeşil kenarlar en kısa yol ağacını oluşturur (ör. 1 → 3 → 6 → 5).
Dijkstra
Dijkstra Örnek 2: Yönlü Çizge, Q ve S Kümeleri
Q
| d | u | π |
|---|---|---|
| 0 | 5 | / |
| ∞ | 1 | / |
| ∞ | 2 | / |
| ∞ | 3 | / |
| ∞ | 4 | / |
S
| u | d | π |
|---|---|---|
İlklendirme: kaynak 5'in uzaklığı 0, diğerleri ∞. Tüm düğümler Q'da, S = ∅.
Q
| d | u | π |
|---|---|---|
| 2 | 4 | 5 |
| 4 | 2 | 5 |
| ∞ | 1 | / |
| ∞ | 3 | / |
S
| u | d | π |
|---|---|---|
| 5 | 0 | / |
Adım 1: Q'dan 5 alınır, d = 0 ile S'ye konur. Gevşetme: (5,2): ∞ → 4; (5,4): ∞ → 2.
Q
| d | u | π |
|---|---|---|
| 3 | 2 | 4 |
| 3 | 3 | 4 |
| ∞ | 1 | / |
S
| u | d | π |
|---|---|---|
| 5 | 0 | / |
| 4 | 2 | 5 |
Adım 2: Q'dan 4 alınır, d = 2 ile S'ye konur. Gevşetme: (4,2): 4 → 3; (4,3): ∞ → 3.
Q
| d | u | π |
|---|---|---|
| 3 | 3 | 4 |
| 6 | 1 | 2 |
S
| u | d | π |
|---|---|---|
| 5 | 0 | / |
| 4 | 2 | 5 |
| 2 | 3 | 4 |
Adım 3: Q'dan 2 alınır, d = 3 ile S'ye konur. Gevşetme: (2,1): ∞ → 6. (2 ve 3 eşit: 3; küçük numaralı 2 alındı.)
Q
| d | u | π |
|---|---|---|
| 6 | 1 | 2 |
S
| u | d | π |
|---|---|---|
| 5 | 0 | / |
| 4 | 2 | 5 |
| 2 | 3 | 4 |
| 3 | 3 | 4 |
Adım 4: Q'dan 3 alınır, d = 3 ile S'ye konur. Gevşetme: (3,4): 4 zaten S'de. Daha kısa yol çıkmaz (gevşetme yok).
Q
| d | u | π |
|---|---|---|
S
| u | d | π |
|---|---|---|
| 5 | 0 | / |
| 4 | 2 | 5 |
| 2 | 3 | 4 |
| 3 | 3 | 4 |
| 1 | 6 | 2 |
Adım 5: Q'dan 1 alınır, d = 6 ile S'ye konur. Gevşetme: (1,3): 3 zaten S'de; (1,4): 4 zaten S'de. Daha kısa yol çıkmaz (gevşetme yok).
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| d | 6 | 3 | 3 | 2 | 0 |
| π | 2 | 4 | 4 | 5 | / |
Son durum: 5'ten en kısa yollar. Yalnızca π kenarları (yeşil) kalır: 5→4→2→1 (6), 5→4→3 (3).
Dijkstra
Dijkstra: Sözde Kod
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 mesafelerziyaretEdildi kontrolü onu atlar. Yol için gevşetmede önceki[v] = u da saklanır.Dijkstra
Dijkstra (Öncelikli Kuyruk): Kodu Adım Adım İzle
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] }); } } } }
Diziler kurulur (düğümler 1..5, indis 0 kullanılmaz); uzaklik[5] = 0 ve (5, 0) kuyruğa eklenir.
Kuyruktan en küçük uzaklıklı kayıt (5, 0) alınır: u = 5.
5 kesinleşir: ziyaret[5] = true.
Kenar 5→2 (w = 4): 0 + 4 < ∞ → koşul doğru.
uzaklik[2] = 4, onceki[2] = 5; (2, 4) kuyruğa eklenir.
Kenar 5→4 (w = 2): 0 + 2 < ∞ → koşul doğru.
uzaklik[4] = 2, onceki[4] = 5; (4, 2) kuyruğa eklenir.
Kuyruktan en küçük uzaklıklı kayıt (4, 2) alınır: u = 4.
4 kesinleşir: ziyaret[4] = true.
Kenar 4→2 (w = 1): 2 + 1 < 4 → koşul doğru.
uzaklik[2] = 3, onceki[2] = 4; (2, 3) kuyruğa eklenir.
Kenar 4→3 (w = 1): 2 + 1 < ∞ → koşul doğru.
uzaklik[3] = 3, onceki[3] = 4; (3, 3) kuyruğa eklenir.
Kuyruktan en küçük uzaklıklı kayıt (2, 3) alınır: u = 2.
2 kesinleşir: ziyaret[2] = true.
Kenar 2→1 (w = 3): 3 + 3 < ∞ → koşul doğru.
uzaklik[1] = 6, onceki[1] = 2; (1, 6) kuyruğa eklenir.
Kuyruktan en küçük uzaklıklı kayıt (3, 3) alınır: u = 3.
3 kesinleşir: ziyaret[3] = true.
Kenar 3→4 (w = 2): ziyaret[4] = true → koşul yanlış.
Kuyruktan en küçük uzaklıklı kayıt (2, 4) alınır: u = 2.
ziyaret[2] zaten true: bu, 2'nin eski (2, 4) kaydı → continue ile atlanır (tembel silme).
Kuyruktan en küçük uzaklıklı kayıt (1, 6) alınır: u = 1.
1 kesinleşir: ziyaret[1] = true.
Kenar 1→3 (w = 6): ziyaret[3] = true → koşul yanlış.
Kenar 1→4 (w = 3): ziyaret[4] = true → koşul yanlış.
Kuyruk boş: döngü biter. uzaklik = [6, 3, 3, 2, 0], onceki = [2, 4, 4, 5, –].
Dijkstra
Yolu Geri Kurma: π (önceki) Dizisi
Örnek 2'nin sonucu: π = [2, 4, 4, 5, /]. Hedef 1 için geriye doğru:
1 ← π[1] = 2 ← π[2] = 4 ← π[4] = 5 (kaynak)
Ters çevrilince yol: 5 → 4 → 2 → 1, uzunluk 2 + 1 + 3 = 6 = d[1].
void yolYaz(int[] onceki, int[] uzaklik, int kaynak, int hedef) { if (uzaklik[hedef] == SONSUZ) { // ulaşılamaz System.out.print("yol yok"); return; } 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() + " "); }
Yığın (stack) geriye doğru toplanan düğümleri doğru sıraya çevirir.
Dijkstra · Kodu adım adım çalıştır
Yolu Geri Kurma: yolYaz(onceki, uzaklik, 5, 1) İzleme
void yolYaz(int[] onceki, int[] uzaklik, int kaynak, int hedef) { if (uzaklik[hedef] == SONSUZ) { // ulaşılamaz System.out.print("yol yok"); return; } 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() + " "); }
Dijkstra Örnek 2'nin sonucu: onceki = [2, 4, 4, 5, /] (kaynak 5, hedef 1). d[1] = 6 ≠ SONSUZ: hedef ulaşılabilir. Boş bir yığın oluşturuldu; yol hedeften geriye doğru toplanacak.
1 ≠ kaynak → yığına itilir. Sonraki adımda v = onceki[1] = 2.
2 ≠ kaynak → yığına itilir. Sonraki adımda v = onceki[2] = 4.
4 ≠ kaynak → yığına itilir. Sonraki adımda v = onceki[4] = 5.
v = 5 = kaynak: döngü koşulu yanlış, döngü biter. Kaynağın kendisi henüz yığında değil.
Kaynak 5 itilir. Yığının tepesinde (şekilde en üstte) kaynak, dibinde hedef var: sıra kendiliğinden düzeldi.
5 çekilip yazılır (LIFO: en son itilen ilk çıkar).
4 çekilip yazılır (LIFO: en son itilen ilk çıkar).
2 çekilip yazılır (LIFO: en son itilen ilk çıkar).
1 çekilip yazılır. Yığın boşaldı: yol 5 → 4 → 2 → 1, uzunluk 2 + 1 + 3 = 6.
Dijkstra
Dijkstra: Algoritma Karmaşıklığı
Maliyet, en küçük uzaklıklı düğümü seçme işleminin nasıl yapıldığına bağlıdır:
| Seçim yapısı | Seçim | Gevşetme | Toplam | Uygun çizge |
|---|---|---|---|---|
| Dizi (doğrusal tarama) | V × O(V) | E × O(1) | O(V²) | yoğun (E ≈ V²) |
| İkili heap (öncelikli kuyruk) | O(log V) | O(log V) | O((V + E) log V) | seyrek (E ≪ V²) |
| Fibonacci heap | O(log V) amortize | O(1) amortize | O(E + V log V) | kuramsal en iyi |
Dijkstra
Dijkstra Neden Negatif Kenarda Yanılır?
- Doğruluk kanıtı şuna dayanır: kesinleşen u için, S dışından geçen her yol en az d[u] uzunluğundadır; çünkü kenarlar negatif değildir ve yol yalnızca uzayabilir.
- Negatif kenar bu varsayımı bozar: sonradan işlenen bir düğüm, kesinleşmiş bir düğüme daha kısa yol açabilir.
- Tüm ağırlıklara sabit eklemek de çözüm değildir: çok kenarlı yollar daha fazla ceza alır, en kısa yol değişir.
- Negatif kenar varsa Bellman-Ford kullanılır.
A kesinleşir; gevşetme ile d[B] = 2, d[C] = 3.
En küçük d: B (2). Dijkstra B'yi kesinleştirir: “B'ye daha kısa yol olamaz” varsayımı.
C işlenir: d[C] + (−2) = 1 < 2, ama B zaten S'de. Sonuç d[B] = 2 yanlış; gerçek δ(A, B) = 1 (A → C → B).
Bellman-Ford
Bellman-Ford Algoritması
- Kaynak düğümden diğer tüm düğümlere olan en kısa yolları bulur (tek kaynaklı).
- Richard Bellman (1958) ve Lester Ford Jr. (1956) adlarını taşır; E. F. Moore da 1959'da aynı yöntemi verdi.
- Negatif ağırlıklı kenarları işleyebilir.
- Kaynaktan ulaşılabilen negatif döngüleri tespit edebilir.
- Dijkstra'dan yavaştır: O(V · E).
Bellman-Ford
Bellman-Ford: Algoritma Adımları
Adım 1: Başlangıç düğümüne uzaklık 0, diğer düğümlere ∞ atanır.
π[v] = tanımsız.
Adım 2: Kenarlar tek tek incelenir, düğümler arası uzaklıklar gevşetme ile güncellenir; bu tur V − 1 kez tekrarlanır.
Bir turda kenar sırası sabittir; sıra sonucu değil, kaç turda yakınsayacağını etkiler.
Adım 3: 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.
Adım 4: Negatif döngü kontrolü için tüm kenarlar bir kez daha incelenir; hâlâ gevşeyen 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
Neden V − 1 Tur? Karmaşıklık
- Negatif döngü yoksa her en kısa yol en fazla V − 1 kenarlıdır.
- Değişmez: i. turun sonunda, en fazla i kenarlı en kısa yolu olan her v için d[v] = δ(s, v).
- Tur i'de yolun i. kenarı mutlaka gevşetilir; V − 1 tur tüm yolları tamamlar.
- Her tur E kenarı inceler: toplam O(V · E) zaman, O(V) ek bellek.
| Çizge | Zaman |
|---|---|
| Seyrek, E ≈ V | O(V²) |
| Yoğun, E ≈ V² | O(V³) |
| En iyi durum (erken durma) | O(E) |
Bellman-Ford
Bellman-Ford Örnek 1: Kenar Kenar Gevşetme
İlklendirme: d[s] = 0, diğerleri ∞. Kenarlar her turda yukarıdaki sırayla incelenir.
Tur 1, kenar (s, v₁): 0 + 9 = 9 < ∞ → d[v₁] = 9.
Tur 1, kenar (s, v₂): 0 + 3 = 3 < ∞ → d[v₂] = 3.
Tur 1, kenar (v₁, v₂): 9 + 6 = 15 ≥ 3 → değişmez.
Tur 1, kenar (v₁, v₄): 9 + 2 = 11 < ∞ → d[v₄] = 11.
Tur 1, kenar (v₂, v₁): 3 + 2 = 5 < 9 → d[v₁] = 5.
Tur 1, kenar (v₂, v₃): 3 + 1 = 4 < ∞ → d[v₃] = 4.
Tur 1, kenar (v₃, v₂): 4 + 2 = 6 ≥ 3 → değişmez.
Tur 1, kenar (v₃, v₄): 4 + 2 = 6 < 11 → d[v₄] = 6.
Tur 2: sekiz kenarın hiçbiri gevşemez → erken durma. Sonuç: v₁ = 5, v₂ = 3, v₃ = 4, v₄ = 6 (bu sırada tek tur yetti).
Bellman-Ford
Bellman-Ford Örnek 2: Negatif Kenarlar
Negatif kenarlı çizge, kaynak S. Kenarlar her turda yukarıdaki sırayla incelenir (sondan başa: en kötü sıra).
Tur 1: yalnızca (S,A): ∞ → 3. Diğer kenarların başı hâlâ ∞.
Tur 2: yalnızca (A,B): ∞ → 2.
Tur 3: yalnızca (B,C): ∞ → 0.
Tur 4: yalnızca (C,D): ∞ → -2; (C,E): ∞ → 1.
Tur 5: yalnızca (E,D): -2 → -3. E üzerinden D'ye daha kısa yol: 1 + (−4) = −3.
Denetim turu: hiçbir kenar gevşemez → negatif döngü yok (A→B→C→E→A = −1 −2 + 1 + 4 = +2). V − 1 = 5 turun hepsi gerekti.
Bellman-Ford
Bellman-Ford Örnek 3: Dijkstra Örnek 2'deki Çizge
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| d | ∞ | ∞ | ∞ | ∞ | 0 |
| π | / | / | / | / | / |
İlklendirme: kaynak 5'in uzaklığı 0, diğerleri ∞. Kenar sırası: (1,3), (1,4), (2,1), (3,4), (4,2), (4,3), (5,2), (5,4).
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| d | ∞ | 4 | ∞ | 2 | 0 |
| π | / | 5 | / | 5 | / |
Tur 1: (5,2): ∞ → 4; (5,4): ∞ → 2.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| d | 7 | 3 | 3 | 2 | 0 |
| π | 2 | 4 | 4 | 5 | / |
Tur 2: (2,1): ∞ → 7; (4,2): 4 → 3; (4,3): ∞ → 3. (4,2) kenarı 2'ye daha kısa yol buldu.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| d | 6 | 3 | 3 | 2 | 0 |
| π | 2 | 4 | 4 | 5 | / |
Tur 3: (2,1): 7 → 6. 2 bir önceki turda iyileştiği için (2,1) yeniden gevşer.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| d | 6 | 3 | 3 | 2 | 0 |
| π | 2 | 4 | 4 | 5 | / |
Tur 4: daha kısa yol bulunamadı (hiçbir kenar gevşemez).
Bellman-Ford
Negatif Döngü Kontrolü (V. Tur)
Her kenar için son bir kez gevşetme denenir: d[v] > d[u] + w(u, v) olan bir kenar kalırsa kaynaktan ulaşılabilen bir negatif döngü vardır. Örnek 3'ün sonucunda:
| kenar | d[v] | d[u] + w(u, v) | sonuç |
|---|---|---|---|
| (1, 3) | d[3] = 3 | d[1] + w = 6 + 6 = 12 | 3 ≯ 12 ✓ |
| (1, 4) | d[4] = 2 | d[1] + w = 6 + 3 = 9 | 2 ≯ 9 ✓ |
| (2, 1) | d[1] = 6 | d[2] + w = 3 + 3 = 6 | 6 ≯ 6 ✓ |
| (3, 4) | d[4] = 2 | d[3] + w = 3 + 2 = 5 | 2 ≯ 5 ✓ |
| (4, 2) | d[2] = 3 | d[4] + w = 2 + 1 = 3 | 3 ≯ 3 ✓ |
| (4, 3) | d[3] = 3 | d[4] + w = 2 + 1 = 3 | 3 ≯ 3 ✓ |
| (5, 2) | d[2] = 3 | d[5] + w = 0 + 4 = 4 | 3 ≯ 4 ✓ |
| (5, 4) | d[4] = 2 | d[5] + w = 0 + 2 = 2 | 2 ≯ 2 ✓ |
Bellman-Ford
Negatif Döngü Tespiti: Örnek
A → B → C → A döngüsü: 1 + (−3) + 1 = −1. Kenar sırası: (S,A), (A,B), (B,C), (C,A).
| tur | S | A | B | C |
|---|---|---|---|---|
| 1 | 0 | 1 | 3 | 0 |
| 2 | 0 | 0 | 2 | -1 |
| 3 | 0 | -1 | 1 | -2 |
- V − 1 = 3 tur sonunda d = [0, −1, 1, −2]; döngüdeki değerler her turda 1 azalıyor.
- Denetim: (A, B) için d[A] + 1 = 0 < d[B] = 1 → negatif döngü var.
- Döngüdeki ve döngüden ulaşılan düğümlerin en kısa yolu −∞'dur (tanımsız).
Bellman-Ford
Bellman-Ford: Sözde Kod
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
Bellman-Ford
Bellman-Ford: Kodu Adım Adım İzle
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ü"); } }
Kaynak 0. uzaklik = [0, ∞, ∞, ∞]. Kenar listesi: (2,1,−2), (0,1,4), (0,2,5), (1,3,3).
Tur 1, kenar (2,1): uzaklik[2] = ∞ → koşul yanlış, atlanır.
Tur 1, kenar (0,1): 0 + (4) = 4 < ∞ → koşul doğru.
uzaklik[1] = 4, onceki[1] = 0.
Tur 1, kenar (0,2): 0 + (5) = 5 < ∞ → koşul doğru.
uzaklik[2] = 5, onceki[2] = 0.
Tur 1, kenar (1,3): 4 + (3) = 7 < ∞ → koşul doğru.
uzaklik[3] = 7, onceki[3] = 1. Tur 1 bitti: (2,1) kenarı 2 henüz ∞ iken incelendiği için boşa geçti.
Tur 2, kenar (2,1): 5 + (-2) = 3 < 4 → koşul doğru.
uzaklik[1] = 3, onceki[1] = 2.
Tur 2, kenar (0,1): 0 + (4) = 4 ≥ 3 → değişiklik yok.
Tur 2, kenar (0,2): 0 + (5) = 5 ≥ 5 → değişiklik yok.
Tur 2, kenar (1,3): 3 + (3) = 6 < 7 → koşul doğru.
uzaklik[3] = 6, onceki[3] = 1. Tur 2 bitti: negatif kenar 1'i 3'e, o da 3'ü 6'ya indirdi.
Tur 3, kenar (2,1): 5 + (-2) = 3 ≥ 3 → değişiklik yok.
Tur 3, kenar (0,1): 0 + (4) = 4 ≥ 3 → değişiklik yok.
Tur 3, kenar (0,2): 0 + (5) = 5 ≥ 5 → değişiklik yok.
Tur 3, kenar (1,3): 3 + (3) = 6 ≥ 6 → değişiklik yok.
Tur 3 hiçbir şeyi değiştirmedi. Denetim turu (satır 16–20): hiçbir kenar gevşemez, istisna fırlatılmaz. Sonuç [0, 3, 5, 6].
Bellman-Ford · Kodu adım adım çalıştır
Bellman-Ford: Negatif Döngü Denetimi İzleme
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ü"); }
S → A (2) ve A → B → C → A döngüsü: 1 + (−3) + 1 = −1. uzaklik = [S, A, B, C] = [0, ∞, ∞, ∞]; kenarlar SA, AB, BC, CA sırasıyla gevşetilecek.
Tur 1, kenar SA: 0 + (2) = 2 daha küçük → uzaklik[A] = 2.
Tur 1, kenar AB: 2 + (1) = 3 daha küçük → uzaklik[B] = 3.
Tur 1, kenar BC: 3 + (-3) = 0 daha küçük → uzaklik[C] = 0.
Tur 1, kenar CA: 0 + (1) = 1 daha küçük → uzaklik[A] = 1. A, döngü üzerinden dolaşınca 2'den 1'e indi.
Tur 2 bitti: dört kenardan üçü yine gevşedi (B = 2, C = -1, A = 0). Döngüdeki değerler her turda 1 azalıyor.
Tur 3 bitti: dört kenardan üçü yine gevşedi (B = 1, C = -2, A = -1). Döngüdeki değerler her turda 1 azalıyor.
V − 1 = 3 tur bitti; denetim turu başlar. Kenar SA: 0 + 2 = 2 < -1 değil, sorun yok.
Denetim, kenar AB: -1 + 1 = 0 < 1 → V − 1 turdan sonra hâlâ gevşiyor: negatif döngü var, istisna fırlatılır.
Floyd-Warshall
Floyd-Warshall Algoritması
- Tüm düğüm çiftleri arasındaki en kısa yolları bulur (all-pairs).
- Bernard Roy (1959), Stephen Warshall (1962, geçişli kapanış) ve Robert Floyd (1962, en kısa yol) tarafından birbirinden bağımsız verilmiştir.
- Negatif ağırlıklı kenarlarla çalışır; negatif döngüyü tespit eder (o durumda en kısa yol tanımsızdır).
- Dinamik programlama kullanır; sonuçları bir V × V matriste (D) tutar.
Floyd-Warshall
Floyd-Warshall: Adımlar ve Yineleme Bağıntısı
- Adım 1: D matrisi kenar ağırlıklarıyla doldurulur: D[i][i] = 0; doğrudan kenar yoksa ∞.
- Adım 2: Ara düğüm k = 1, 2, …, n sırayla ele alınır; her (i, j) çifti için…
- Adım 3: 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.
- Adım 4: Daha kısaysa yeni değer matrise yazılır (Π matrisi de güncellenir).
k ya yolda yoktur ya da yol k'den bir kez geçer. D(n) sonuçtur.
Floyd-Warshall
Floyd-Warshall: Karmaşıklık
- Zaman Θ(V³): 3 iç içe for döngüsü, her biri V kez.
- ilk (en dış) döngü tüm ara düğümleri (k) gezer,
- ikinci döngü tüm kaynak düğümleri (i) gezer,
- son döngü tüm hedef düğümleri (j) gezer.
- Bellek Θ(V²): D yerinde (in-place) güncellenebilir; k. satır ve sütun k turunda değişmez.
| Tüm çiftler için | Zaman |
|---|---|
| Floyd-Warshall | O(V³) |
| V × Dijkstra (dizi) | O(V³) |
| V × Dijkstra (heap) | O(V(V + E) log V) |
| V × Bellman-Ford | O(V² E) |
Floyd-Warshall
Floyd-Warshall Örneği: D ve Π Matrisleri
D(0)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | 6 | 3 | ∞ |
| 2 | 3 | 0 | ∞ | ∞ | ∞ |
| 3 | ∞ | ∞ | 0 | 2 | ∞ |
| 4 | ∞ | 1 | 1 | 0 | ∞ |
| 5 | ∞ | 4 | ∞ | 2 | 0 |
Π(0)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | / | 1 | 1 | / |
| 2 | 2 | / | / | / | / |
| 3 | / | / | / | 3 | / |
| 4 | / | 4 | 4 | / | / |
| 5 | / | 5 | / | 5 | / |
k = 0 (ilklendirme): D kenar ağırlıklarıyla doldurulur, köşegen 0, kenar yoksa ∞. Π[i][j] = i (doğrudan kenar varsa), yoksa /.
D(1)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | 6 | 3 | ∞ |
| 2 | 3 | 0 | 9 | 6 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 | ∞ |
| 4 | ∞ | 1 | 1 | 0 | ∞ |
| 5 | ∞ | 4 | ∞ | 2 | 0 |
Π(1)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | / | 1 | 1 | / |
| 2 | 2 | / | 1 | 1 | / |
| 3 | / | / | / | 3 | / |
| 4 | / | 4 | 4 | / | / |
| 5 | / | 5 | / | 5 | / |
k = 1: düğüm 1 üzerinden 2 ⇝ 3 (3 + 6 = 9) ve 2 ⇝ 4 (3 + 3 = 6) yolları bulundu.
D(2)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | 6 | 3 | ∞ |
| 2 | 3 | 0 | 9 | 6 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 | ∞ |
| 4 | 4 | 1 | 1 | 0 | ∞ |
| 5 | 7 | 4 | 13 | 2 | 0 |
Π(2)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | / | 1 | 1 | / |
| 2 | 2 | / | 1 | 1 | / |
| 3 | / | / | / | 3 | / |
| 4 | 2 | 4 | 4 | / | / |
| 5 | 2 | 5 | 1 | 5 | / |
k = 2: düğüm 2 üzerinden 4 ⇝ 1 (1 + 3 = 4), 5 ⇝ 1 (4 + 3 = 7) ve 5 ⇝ 3 (4 + 9 = 13) bulundu.
D(3)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | ∞ | 6 | 3 | ∞ |
| 2 | 3 | 0 | 9 | 6 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 | ∞ |
| 4 | 4 | 1 | 1 | 0 | ∞ |
| 5 | 7 | 4 | 13 | 2 | 0 |
Π(3)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | / | 1 | 1 | / |
| 2 | 2 | / | 1 | 1 | / |
| 3 | / | / | / | 3 | / |
| 4 | 2 | 4 | 4 | / | / |
| 5 | 2 | 5 | 1 | 5 | / |
k = 3: düğüm 3 üzerinden kısa yol bulunamadı (3'ten yalnızca 4'e kenar var, hiçbir değer iyileşmez).
D(4)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 4 | 3 | ∞ |
| 2 | 3 | 0 | 7 | 6 | ∞ |
| 3 | 6 | 3 | 0 | 2 | ∞ |
| 4 | 4 | 1 | 1 | 0 | ∞ |
| 5 | 6 | 3 | 3 | 2 | 0 |
Π(4)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | 4 | 4 | 1 | / |
| 2 | 2 | / | 4 | 1 | / |
| 3 | 2 | 4 | / | 3 | / |
| 4 | 2 | 4 | 4 | / | / |
| 5 | 2 | 4 | 4 | 5 | / |
k = 4: düğüm 4 üzerinden 1⇝2, 1⇝3, 2⇝3, 3⇝1, 3⇝2, 5⇝1, 5⇝2, 5⇝3 kısaldı (8 hücre). Ör. 5⇝3: 2 + 1 = 3 < 13.
D(5)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 4 | 3 | ∞ |
| 2 | 3 | 0 | 7 | 6 | ∞ |
| 3 | 6 | 3 | 0 | 2 | ∞ |
| 4 | 4 | 1 | 1 | 0 | ∞ |
| 5 | 6 | 3 | 3 | 2 | 0 |
Π(5)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | 4 | 4 | 1 | / |
| 2 | 2 | / | 4 | 1 | / |
| 3 | 2 | 4 | / | 3 | / |
| 4 | 2 | 4 | 4 | / | / |
| 5 | 2 | 4 | 4 | 5 | / |
k = 5: düğüm 5 üzerinden kısa yol yok (5'e gelen kenar olmadığından D[i][5] = ∞). Son matrisler hazır.
Floyd-Warshall
Son Durum ve Yolun Okunması
D (uzaklıklar)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 4 | 4 | 3 | ∞ |
| 2 | 3 | 0 | 7 | 6 | ∞ |
| 3 | 6 | 3 | 0 | 2 | ∞ |
| 4 | 4 | 1 | 1 | 0 | ∞ |
| 5 | 6 | 3 | 3 | 2 | 0 |
Π (önceki)
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | / | 4 | 4 | 1 | / |
| 2 | 2 | / | 4 | 1 | / |
| 3 | 2 | 4 | / | 3 | / |
| 4 | 2 | 4 | 4 | / | / |
| 5 | 2 | 4 | 4 | 5 | / |
- Π[i][j]: i'den j'ye en kısa yolda j'den önceki düğüm.
- 5 ⇝ 1: Π[5][1] = 2, Π[5][2] = 4, Π[5][4] = 5 → 5 → 4 → 2 → 1, D[5][1] = 6.
- 1 ⇝ 2: Π[1][2] = 4, Π[1][4] = 1 → 1 → 4 → 2, D[1][2] = 4.
- 5. sütun ∞: 5'e hiçbir düğümden ulaşılamaz.
- 5. satır, Dijkstra ve Bellman-Ford'un kaynak 5 için bulduğu [6, 3, 3, 2, 0] ile aynıdır.
Floyd-Warshall
Floyd-Warshall: Sözde Kod
1. İlklendirme
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
2. Üç iç içe döngü ve denetim
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 mesafeler[i][k] + mesafeler[k][j] < mesafeler[i][j]: mesafeler[i][j] = mesafeler[i][k] + mesafeler[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
Floyd-Warshall
Floyd-Warshall: Java
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ü"); }
- Matris yerinde güncellenir; ayrı D(k) kopyası gerekmez.
- SONSUZ denetimi,
Integer.MAX_VALUEtoplamının taşmasını (overflow) önler. onceki[i][j] = onceki[k][j]: yeni yolda j'den önceki düğüm, k ⇝ j yolundakiyle aynıdır.- Negatif döngü: bir düğümün kendine uzaklığı negatif çıkarsa (D[i][i] < 0).
Floyd-Warshall · Kodu adım adım çalıştır
Floyd-Warshall: Kodu Adım Adım İzle
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ü"); }
Başlangıç: d kenar ağırlıklarıyla dolu (köşegen 0, kenar yoksa ∞); onceki[i][j] = i. Sağdaki matris d, altındaki onceki.
k = 0 ara düğüm: d[1][0] + d[0][3] = 8 + 7 = 15 < ∞ → d[1][3] = 15, onceki[1][3] = onceki[0][3] = 0.
k = 0 ara düğüm: d[2][0] + d[0][1] = 5 + 3 = 8 < ∞ → d[2][1] = 8, onceki[2][1] = onceki[0][1] = 0.
k = 0 ara düğüm: d[3][0] + d[0][1] = 2 + 3 = 5 < ∞ → d[3][1] = 5, onceki[3][1] = onceki[0][1] = 0.
k = 1 ara düğüm: d[0][1] + d[1][2] = 3 + 2 = 5 < ∞ → d[0][2] = 5, onceki[0][2] = onceki[1][2] = 1.
k = 1 ara düğüm: d[3][1] + d[1][2] = 5 + 2 = 7 < ∞ → d[3][2] = 7, onceki[3][2] = onceki[1][2] = 1.
k = 2 ara düğüm: d[0][2] + d[2][3] = 5 + 1 = 6 < 7 → d[0][3] = 6, onceki[0][3] = onceki[2][3] = 2.
k = 2 ara düğüm: d[1][2] + d[2][0] = 2 + 5 = 7 < 8 → d[1][0] = 7, onceki[1][0] = onceki[2][0] = 2.
k = 2 ara düğüm: d[1][2] + d[2][3] = 2 + 1 = 3 < 15 → d[1][3] = 3, onceki[1][3] = onceki[2][3] = 2.
k = 3 ara düğüm: d[1][3] + d[3][0] = 3 + 2 = 5 < 7 → d[1][0] = 5, onceki[1][0] = onceki[3][0] = 3.
k = 3 ara düğüm: d[2][3] + d[3][0] = 1 + 2 = 3 < 5 → d[2][0] = 3, onceki[2][0] = onceki[3][0] = 3.
k = 3 ara düğüm: d[2][3] + d[3][1] = 1 + 5 = 6 < 8 → d[2][1] = 6, onceki[2][1] = onceki[3][1] = 0.
Dört tur bitti. Köşegende negatif değer yok → negatif döngü yok. Örnek yol: onceki[1][3] = 2, onceki[1][2] = 1 → 1 → 2 → 3, d[1][3] = 3.
A* Arama
A* (A Yıldız) Arama Algoritması
- İki nokta (başlangıç → hedef) arasındaki en kısa yolu bulan bir arama algoritmasıdır.
- 1968'de Peter Hart, Nils Nilsson ve Bertram Raphael tarafından geliştirildi.
- Dijkstra'nın (düzgün maliyetli arama) gerçek maliyetini, açgözlü en iyi ilk arama (Greedy Best-First Search) yaklaşımının hedef tahminiyle birleştirir.
- Düzgün çalışması için iyi bir tahmin fonksiyonu (sezgisel, heuristic) gerekir.
- Düğüm sayısı arttıkça zaman ve bellek maliyeti hızla artar.
A* Arama
A* Nasıl Çalışır? f(n) = g(n) + h(n)
| Seçim ölçütü | Algoritma | Davranış |
|---|---|---|
| yalnızca g(n) | Dijkstra | her yöne eşit yayılır; doğru ama çok düğüm açar |
| yalnızca h(n) | Açgözlü en iyi ilk | hedefe koşar; hızlı ama en kısa yolu garanti etmez |
| g(n) + h(n) | A* | hedefe yönelir; h uygunsa en kısa yolu garanti eder |
A* Arama
A*: Algoritma Adımları
1. Başlangıç düğümünün g değeri 0 yapılır ve düğüm açık listeye (open list, öncelikli kuyruk) eklenir. Diğer düğümlerin g değeri ∞'dur.
Açık liste: keşfedilmiş ama henüz genişletilmemiş düğümler.
2. Açık listeden f = g + h değeri en küçük düğüm çıkarılır ve kapalı listeye (closed list) konur.
Seçim ölçütü g ya da h tek başına değil, toplamları f = g + h'dir.
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, çıkarıldığı anda kesinleşir.
4. Değilse her komşu için g' = g(u) + w(u, v) hesaplanır; g' daha küçükse g, f ve önceki değerleri güncellenir, komşu açık listeye eklenir.
Bu, Dijkstra'daki gevşetmenin aynısıdır. v kapalı listedeyse ve daha iyi g bulunduysa yeniden açılır (tutarlı h'de bu hiç olmaz).
5. 2. adıma dönülür. Açık liste boşalırsa hedefe yol yoktur.
Seçim yalnızca son düğümün komşuları arasından değil, açık listenin tamamından yapılır.
A* Arama
Sezgisel Fonksiyonun Özellikleri
A* Arama
A*: Algoritma Karmaşıklığı
- Arama ağacı açısından en kötü durumda zaman ve bellek O(bd):
- b: dallanma faktörü (bir düğümün ortalama komşu sayısı), d: hedefin derinliği (çözümdeki adım sayısı).
- Sonlu bir çizgede tutarlı h ile A*, Dijkstra gibi en fazla O((V + E) log V) iş yapar.
- Sezgisel ne kadar iyiyse o kadar az düğüm açılır: mükemmel tahminde (h = h*) yalnızca yol üzerindeki d düğüm genişletilir.
- Zayıf nokta bellektir: açık ve kapalı listeler büyür; IDA*, SMA* gibi türevler bellek sınırlıdır.
A* Arama
A* Örnek: s'den t'ye (h değerleri düğüm yanında)
Açık liste
| düğüm | g | h | f |
|---|---|---|---|
| a | 1,5 | 4 | 5,5 |
| d | 2 | 4,5 | 6,5 |
Kapalı: s
s genişletilir: komşular a (g = 1,5) ve d (g = 2) açılır. f(a) = 1,5 + 4 = 5,5, f(d) = 2 + 4,5 = 6,5.
Açık liste
| düğüm | g | h | f |
|---|---|---|---|
| b | 3,5 | 2 | 5,5 |
| d | 2 | 4,5 | 6,5 |
Kapalı: s, a
En küçük f: a (5,5). a genişletilir → b: g = 3,5, f(b) = 3,5 + 2 = 5,5.
Açık liste
| düğüm | g | h | f |
|---|---|---|---|
| d | 2 | 4,5 | 6,5 |
| c | 6,5 | 4 | 10,5 |
Kapalı: s, a, b
b genişletilir (5,5 < 6,5) → c: g = 6,5, f(c) = 6,5 + 4 = 10,5. Bu yol pahalılaşıyor.
Açık liste
| düğüm | g | h | f |
|---|---|---|---|
| e | 5 | 2 | 7 |
| c | 6,5 | 4 | 10,5 |
Kapalı: s, a, b, d
Artık en küçük f: d (6,5). Arama diğer kola geçer → e: g = 5, f(e) = 5 + 2 = 7.
Açık liste
| düğüm | g | h | f |
|---|---|---|---|
| t | 7 | 0 | 7 |
| c | 6,5 | 4 | 10,5 |
Kapalı: s, a, b, d, e
e genişletilir → t: g = 5 + 2 = 7, f(t) = 7 + 0 = 7 < f(c) = 10,5.
Açık liste
| düğüm | g | h | f |
|---|---|---|---|
| c | 6,5 | 4 | 10,5 |
Kapalı: s, a, b, d, e, t
t açık listeden çıkarıldı: hedef. En kısa yol s → d → e → t, maliyet 7. c hiç genişletilmedi.
A* Arama · Kodu adım adım çalıştır
A*: Kodu Adım Adım İzle
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; }
Yönsüz çizge, hedef t. Düğüm yanındaki h değerleri hedefe tahmini uzaklıktır. g(s) = 0; açık listede yalnızca s var (parantezde f = g + h).
Açık listede f'si en küçük olan s çıkarılır (f = 0 + 5 = 5). Hedef değil, komşuları incelenecek.
g(a) = 0 + 1,5 = 1,5, f = 5,5; g(d) = 0 + 2 = 2, f = 6,5.
Açık listede f'si en küçük olan a çıkarılır (f = 1,5 + 4 = 5,5). Hedef değil, komşuları incelenecek.
g(b) = 1,5 + 2 = 3,5, f = 5,5.
Açık listede f'si en küçük olan b çıkarılır (f = 3,5 + 2 = 5,5). Hedef değil, komşuları incelenecek.
g(c) = 3,5 + 3 = 6,5, f = 10,5. c'nin f'si (10,5) büyük; sıradaki seçim f'si 6,5 olan d olacak.
Açık listede f'si en küçük olan d çıkarılır (f = 2 + 4,5 = 6,5). Hedef değil, komşuları incelenecek.
g(e) = 2 + 3 = 5, f = 7.
Açık listede f'si en küçük olan e çıkarılır (f = 5 + 2 = 7). Hedef değil, komşuları incelenecek.
g(t) = 5 + 2 = 7, f = 7.
En küçük f'li düğüm t (f = 7): hedef açık listeden çıktı → return g[t] = 7. Ebeveyn dizisinden yol: s → d → e → t; c hiç açılmadı.
A* Arama
A* Örnek: Izgarada Duvarın Etrafından
A genişletilir: 8 komşu açılır. Düz adım 10, çapraz 14; h = oktil uzaklık (duvarlar yok sayılır). En küçük f = 42.
2. genişletme: en küçük f = 42 olan hücre (turuncu çerçeve) kapalı listeye geçer, komşuları açılır/güncellenir.
4. genişletme: en küçük f = 48 olan hücre (turuncu çerçeve) kapalı listeye geçer, komşuları açılır/güncellenir.
7. genişletme: en küçük f = 54 olan hücre (turuncu çerçeve) kapalı listeye geçer, komşuları açılır/güncellenir. Duvarın altındaki hücreler f = 42…62 ile önce denenir.
9. genişletme: en küçük f = 62 olan hücre (turuncu çerçeve) kapalı listeye geçer, komşuları açılır/güncellenir.
13. genişletme: en küçük f = 68 olan hücre (turuncu çerçeve) kapalı listeye geçer, komşuları açılır/güncellenir. Alt yol tıkalı: f = 68 değerine çıkıldı, arama duvarın iki yanına yayılıyor.
17. genişletme (f = 68): duvarın sağından dolaşan yol B'ye ulaştı; B açık listede f = 68.
B çıkarıldı: yol A → yukarı → sağ üst çapraz → sol üst çapraz → duvar üstünden üç adım sola, maliyet 68 (2 çapraz × 14 + 4 düz × 10). 18 hücre genişletildi.
İlgili Yöntemler
BFS: Ağırlıksız Çizgede En Kısa Yol
- Tüm kenarlar eşit (ağırlık 1) ise en kısa yol = en az kenarlı yol.
- Genişlik öncelikli arama (BFS) düğümleri kaynağa uzaklık sırasıyla, katman katman ziyaret eder: d[v] = d[u] + 1.
- Kuyruk (FIFO), Dijkstra'nın öncelikli kuyruğunun yerini alır: O(V + E).
- Örnek (yandaki çizge): 0 → 6 en kısa yolu 0 → 2 → 4 → 6 (3 kenar).
- İki yönlü arama (bidirectional): BFS hem kaynaktan hem hedeften başlatılır, iki dalga buluşunca durulur; yaklaşık 2·bd/2 düğüm açılır.
Sayılar: BFS düzeyi (kenar sayısı). Yeşil: BFS ağacı.
Karşılaştırma
En Kısa Yol Algoritmalarının Karşılaştırması
| Algoritma | Problem | Negatif kenar | Negatif döngü | Zaman | Yöntem |
|---|---|---|---|---|---|
| BFS | tek kaynak, ağırlıksız | — | — | O(V + E) | katman katman |
| Dijkstra | tek kaynak | hayır | hayır | O(V²) / O((V + E) log V) | açgözlü |
| Bellman-Ford | tek kaynak | evet | tespit eder | O(V · E) | tekrarlı gevşetme (DP) |
| Floyd-Warshall | tüm çiftler | evet | tespit eder | Θ(V³) | dinamik programlama |
| A* | tek çift | hayır | hayır | en kötü O(bd) | sezgisel + açgözlü |
Özet
Özet
| Konu | Hatırlanacaklar |
|---|---|
| Gevşetme | d[u] + w < d[v] ise d[v] ve π[v] güncellenir; tüm algoritmaların ortak işlemi |
| Dijkstra | en küçük d'li düğümü kesinleştir, komşularını gevşet; ağırlıklar ≥ 0; O((V + E) log V) |
| Bellman-Ford | tüm kenarları V − 1 tur gevşet; V. turda gevşeyen kenar = kaynaktan ulaşılabilen negatif döngü; O(V · E) |
| Floyd-Warshall | D[i][j] = min(D[i][j], D[i][k] + D[k][j]), k en dışta; D[i][i] < 0 → negatif döngü; Θ(V³) |
| A* | f = g + h; kabul edilebilir h ile en kısa yol; h = 0 → Dijkstra |
| BFS | ağırlıksız çizgede en az kenarlı yol; O(V + E) |
| Yol | π (Π) işaretçileriyle hedeften geriye; en kısa yol ağacı |
Özet
Etkileşimli Simülatörler
Özet
Sık Yapılan Hatalar
Integer.MAX_VALUE + w negatife döner ve “daha kısa” görünür. Bu yüzden önce d[u] != SONSUZ denetlenir.Özet
Örnek Problemler
Yönlü çizge: A→B 4, A→C 2, C→B 1, B→D 5, C→D 8, C→E 10, D→E 3; kaynak A.
- Dijkstra düğümleri hangi sırayla kesinleştirir? Son d değerleri nedir?
- A'dan E'ye en kısa yolu π dizisiyle yazın.
- Kenarlar alfabetik sırayla (A→B, A→C, B→D, C→B, C→D, C→E, D→E) incelenirse Bellman-Ford'un her turunda kaç gevşetme olur?
- 1→2 (4), 2→3 (1), 1→3 (7), 3→1 (−2) çizgesinin Floyd-Warshall son D matrisi nedir? Negatif döngü var mı?
- V = 1000, E = 5000 ve negatif kenarlar var. Hangi algoritma, yaklaşık kaç işlem?
Cevapları göster
- A, C, B, D, E; d = A:0, B:3, C:2, D:8, E:11 (B, C üzerinden 2 + 1 ile iyileşir).
- π[E] = D, π[D] = B, π[B] = C, π[C] = A → A → C → B → D → E = 2 + 1 + 5 + 3 = 11.
- Tur 1: 5 (B=4, C=2, D=9, B=3, E=12); tur 2: 2 (D=8, E=11); tur 3–4: 0 → erken durma mümkün.
- D = [[0, 4, 5], [−1, 0, 1], [−2, 2, 0]]; köşegen 0 → döngüler 1→2→3→1 = +3 ve 1→3→1 = +5, negatif döngü yok.
- Bellman-Ford: V · E = 1000 · 5000 = 5 · 10⁶ gevşetme denemesi (Dijkstra negatif kenarda güvenilmez).
Özet
Alıştırmalar
- Dijkstra Örnek 1'deki çizgede kaynağı 5 alarak tüm uzaklıkları bulun.
dijkstra(kaynak, hedef): hedef kuyruktan çıkınca duran sürümü yazın.- Her düğüm için en kısa yol sayısını da hesaplayan Dijkstra yazın.
- Bellman-Ford'a erken durma ekleyin; en iyi durumda karmaşıklık nedir?
- Floyd-Warshall'ı boolean matrisle geçişli kapanış (Warshall) için uyarlayın.
- Manhattan uzaklığı 4 yönlü ızgarada neden kabul edilebilir, 8 yönlüde neden değildir?
Cevaplar / ipuçları
- d = 1:20, 2:21, 3:11, 4:6, 5:0, 6:9 (ör. 3: 5→6→3 = 9 + 2; 2: 5→4→2 = 6 + 15).
- Satır 13'ten önce
if (u == hedef) break;— eklenme anında değer henüz kesin değildir. sayi[kaynak] = 1; d[u] + w < d[v] isesayi[v] = sayi[u], eşitsesayi[v] += sayi[u].degistibayrağı false kalırsa döngüden çıkılır; en iyi durum O(E).t[i][j] = t[i][j] || (t[i][k] && t[k][j]); yine k en dışta, Θ(V³).- Her adım |Δx| + |Δy|'yi en çok 1 azaltır → h ≤ h*. Çapraz adım 2 azaltır ama 1 (ya da 1,4) tutar → fazla tahmin.
Özet
Kaynaklar
- Cormen, Leiserson, Rivest ve Stein, Introduction to Algorithms, 4. baskı, 2022 (Bölüm 22–23).
- Sedgewick ve Wayne, Algorithms, 4. baskı, 2011 (Bölüm 4.4: Shortest Paths).
- E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik 1, 1959.
- R. Bellman, "On a Routing Problem", Quarterly of Applied Mathematics 16, 1958.
- R. W. Floyd, "Algorithm 97: Shortest Path", Communications of the ACM 5(6), 1962; S. Warshall, "A Theorem on Boolean Matrices", Journal of the ACM 9(1), 1962.
- P. E. Hart, N. J. Nilsson ve B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Trans. SSC 4(2), 1968.