En kısa yol ve döngü tespiti: BFS, Dijkstra, Bellman-Ford

Geçen hafta grafı nasıl saklayacağını ve BFS/DFS ile nasıl gezeceğini gördün. Bu hafta o gezintileri işe koşuyoruz: bir kaynaktan (single-source) her düğüme en kısa yol ve grafta döngü var mı soruları. Sınavda neredeyse kesin bir “Dijkstra tablosunu doldur” sorusu gelir. Yanında “Dijkstra burada neden yanlış?” ya da “bu grafta döngü var mı?” türü kısa sorular olur.

Altın kurallar:

1. Ağırlık yoksa BFS yeter. En kısa yol = en az kenar sayısı = BFS katmanı.
2. Ağırlık pozitifse Dijkstra. Her adımda bilinmeyenler içinde en küçük mesafeli düğümü seç, kesinleştir, kenarlarını gevşet.
3. Negatif kenar varsa Bellman-Ford. Dijkstra sessizce yanlış cevap verebilir.
4. Yol, prev dizisinden geriye okunur. Hedeften kaynağa yürü, sonra ters çevir.
5. Yönlü grafta döngü = gri düğüme kenar. Yönsüzde = iki ucu aynı kümede olan kenar.

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

Her kenarın maliyeti 1 ise en kısa yol, en az kenarlı yoldur. BFS düğümleri kaynaktan uzaklık sırasına göre (katman katman) çıkardığı için bir düğümü ilk keşfettiği an mesafesi kesindir. Kural: dist[w] = dist[v] + 1, prev[w] = v.

Örnek yönsüz graf (komşu listeleri artan sırada):

      0
     / \
    1   2
     \ /
      3
      |
      4
     / \
    5   6
     \ /
      7

kuyruk         çıkan  keşfedilen (dist)
[0]            0      1(1) 2(1)
[1,2]          1      3(2)
[2,3]          2      -    (3 zaten görüldü)
[3]            3      4(3)
[4]            4      5(4) 6(4)
[5,6]          5      7(5)
[6,7]          6      -
[7]            7      -

BFS dist: [0, 1, 1, 2, 3, 4, 4, 5]
BFS prev: [-1, 0, 0, 1, 3, 4, 4, 5]
BFS path 0->7: [0, 1, 3, 4, 5, 7]

Süre $O(V + E)$: her düğüm kuyruğa bir kez girer, her kenar bir kez (yönsüzde iki kez) bakılır.

TUZAK · mesafeyi kuyruktan çıkarken değil, keşfederken yaz. Düğümü kuyruğa koyduğun anda dist ve prev ver ve “görüldü” say. Yoksa aynı düğüm kuyruğa iki kez girer.

Dijkstra algoritması

Kenarların ağırlığı var ve hepsi negatif değil. Fikir: kaynaktan en yakın düğüm, başka hiçbir düğüm üzerinden daha kısa yola sahip olamaz (her ek kenar maliyeti artırır). O yüzden en küçük geçici mesafeli düğümü kesinleştir (known) ve ondan çıkan kenarları gevşet (relax):

$d_u > d_v + w(v,u) \;\Rightarrow\; d_u = d_v + w(v,u),\; prev_u = v$

Adımlar:

1. d[kaynak] = 0, diğerleri ∞. Hiçbiri bilinmiyor.
2. Bilinmeyenler içinden d değeri en küçük olan v’yi seç. Eşitlikte küçük etiketi seç.
3. v’yi bilinen yap. Bilinmeyen her komşu u için gevşet.
4. Bilinmeyen kalmayana (ya da hepsi ∞ olana) kadar 2’ye dön.

Çözümlü örnek

G1 grafı (yönlü), komşu listesi gösterimiyle:

A: B(4) C(1)
B: D(5)
C: B(2) D(8) E(10)
D: E(2) F(6)
E: F(2)
F: -

Sınavda tablo şöyle doldurulur. Her satır bir seçim; * bilinen demek.

adım seç  A   B   C   D   E   F
 0    -   0   ∞   ∞   ∞   ∞   ∞
 1    A   0*  4   1   ∞   ∞   ∞
 2    C   0*  3   1*  9   11  ∞
 3    B   0*  3*  1*  8   11  ∞
 4    D   0*  3*  1*  8*  10  14
 5    E   0*  3*  1*  8*  10* 12
 6    F   0*  3*  1*  8*  10* 12*

Programın çıktısı:

Dijkstra order: A C B D E F
Dijkstra final: A=0 B=3 C=1 D=8 E=10 F=12
prev: A=- B=C C=A D=B E=D F=E
  path to F: [A, C, B, D, E, F] cost 12

Dikkat edilecek iki an: 2. adımda B’nin değeri 4’ten 3’e düştü (C üzerinden daha ucuz). 4. adımda E, 11’den 10’a düştü. Gevşetme budur: daha iyi bir yol bulunca değeri ve prev’i güncellersin.

İPUCU · tabloda prev sütunu da tut. Sınav “path from A to F” diye sorarsa her güncellemede kimin üzerinden geldiğini yazmış olman gerekir. Sonradan geri hesaplamak zaman kaybettirir.

Karmaşıklık

Java’da PriorityQueue ile yazarken “decreaseKey” yoktur. Pratik çözüm: mesafe düşünce düğümü yeni değeriyle tekrar ekle, kuyruktan çıkan düğüm zaten biliniyorsa atla (lazy deletion).

PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> x[1] - y[1]);
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
    int[] top = pq.poll();
    int v = top[0];
    if (known[v]) continue;          // eski kopya
    known[v] = true;
    for (int[] e : adj.get(v)) {     // e = {komşu, ağırlık}
        int u = e[0], w = e[1];
        if (!known[u] && d[v] + w < d[u]) {
            d[u] = d[v] + w;
            prev[u] = v;
            pq.add(new int[]{u, d[u]});
        }
    }
}

Negatif kenar ve Bellman-Ford

Dijkstra’nın “en yakını kesinleştir” adımı, sonradan bulunan bir kenarın mesafeyi azaltamayacağına güvenir. Negatif kenar bu güveni bozar.

A --2--> B --1--> D
|        ^
5       -4
|        |
+-> C ---+

Dijkstra order: A B D C
Dijkstra final: A=0 B=2 C=5 D=3
BF round 1: A=0 B=1 C=5 D=2

Dijkstra B’yi 2 ile kesinleştirdi, D’yi 3 yaptı. C en son geldi; C→B kenarı B’yi 1’e indirebilirdi ama B kapandı. Gerçek cevap D = 2.

Bellman-Ford seçim yapmaz: her turda bütün kenarları sırayla gevşetir. En kısa yol en fazla V−1 kenar içerdiği için V−1 tur yeter. Süre $O(V \cdot E)$, Dijkstra’dan yavaş ama negatif kenarla doğru çalışır.

Arrays.fill(d, INF);
d[src] = 0;
for (int round = 1; round <= V - 1; round++)
    for (Edge e : edges)
        if (d[e.from] != INF && d[e.from] + e.w < d[e.to])
            d[e.to] = d[e.from] + e.w;

Kenar sırası tur sayısını etkiler. e1 B→C 2, e2 A→B −1, e3 S→A 4, e4 S→B 5, e5 C→D 3, e6 A→C 6 sırasıyla, S’den:

BF round 1: S=0 A=4 B=5 C=10 D=inf
BF round 2: S=0 A=4 B=3 C=7 D=10
BF round 3: S=0 A=4 B=3 C=5 D=8
BF round 4: S=0 A=4 B=3 C=5 D=8 (no change)

Bir turda hiçbir şey değişmediyse erken durabilirsin. V−1 turdan sonra bir kenar hâlâ gevşiyorsa toplamı negatif bir döngü var demektir; o zaman “en kısa yol” tanımsızdır (döngüde dönüp durarak maliyet sonsuza kadar azalır). S→A 1, A→B 2, B→C −4, C→A 1 grafında A→B→C→A toplamı −1 ve program BF negative cycle: true basar.

TUZAK · “tüm ağırlıklara sabit ekle” hilesi çalışmaz. Negatif kenardan kurtulmak için her kenara 5 eklersen çok kenarlı yollar daha fazla ceza alır, en kısa yol değişir.

Döngü tespiti (cycle detection)

Yönlü graf: üç renkli DFS

• Beyaz (0): hiç görülmedi.
• Gri (1): DFS’e girildi, henüz bitmedi (özyineleme yığınında).
• Siyah (2): tüm torunları bitti.

Gri bir düğüme giden kenar, şu anki yolun bir atasına geri dönüyor demek: geri kenar (back edge), yani döngü. Siyah düğüme giden kenar döngü değildir; o dal zaten bitmiş.

0 --> 1 --> 2
|     ^     |
v     |     v
4     +---- 3

DFS 0, 1, 2, 3 sırasıyla iner, dördü de gri. 3→1 gri düğüme gidiyor:

G2 directed cycle: true back edge 3->1
DAG directed cycle: false

Döngüsüz yönlü grafa DAG denir. Sadece DAG’ların topolojik sırası vardır; Kahn algoritmasında (geçen hafta) tüm düğümler çıkarılamıyorsa da döngü var demektir.

Yönsüz graf

Yönsüz grafta her kenar iki yönlü olduğu için “komşu zaten görülmüş” her zaman döngü değildir: geldiğin ebeveyn de görülmüştür. İki yol:

• DFS + parent: görülmüş bir komşu, ebeveynin değilse döngü.
• Union-find: kenarları tek tek ekle. İki uç zaten aynı kümedeyse bu kenar döngü kapatır. Kruskal (13. hafta) tam olarak bunu kullanır.

undirected: first cycle-closing edge 1-3

Hızlı kontrol: bağlantılı yönsüz grafta $E \ge V$ ise mutlaka döngü vardır (ağaçta $E = V - 1$).

Hangi algoritma ne zaman?

Sık yapılan hatalar

pick A: B=4 C=1
pick C: B=min(4,1+2)=3 D=9 E=11
pick B: D=min(9,3+5)=8
pick D: E=min(11,8+2)=10 F=14
pick E: F=min(14,10+2)=12
pick F: bitti

static boolean hasCycle(List<List<Integer>> adj) {
    int[] color = new int[adj.size()];
    for (int v = 0; v < adj.size(); v++)
        if (color[v] == 0 && dfs(adj, v, color)) return true;
    return false;
}
static boolean dfs(List<List<Integer>> adj, int v, int[] color) {
    color[v] = 1;                       // gray
    for (int w : adj.get(v)) {
        if (color[w] == 1) return true; // back edge
        if (color[w] == 0 && dfs(adj, w, color)) return true;
    }
    color[v] = 2;                       // black
    return false;
}