Bölüm 18: En Kısa Yol ve Aktivite Ağları

18.1En kısa yol problemi

Bir haritada şehirler ve aralarındaki demiryolu hatları düşünülsün. Her hattın bir uzunluğu vardır. Yolcunun sorusu basittir: bir şehirden ötekine en kısa yol hangisidir? Aynı soru bir bilgisayar ağında da sorulur. Orada düğümler yönlendiriciler (router), kenarlar iki yönlendirici arasındaki bağlantılardır. Kenarın değeri bu kez uzunluk değil, paketin o bağlantıda beklediği süredir; trafik sıkıştıkça bu süre artar. Bir yönlendiricinin paketi hangi komşusuna göndereceğine karar vermesi, en kısa yol probleminin her saniye yeniden çözülmesi demektir.

İki örneğin ortak modeli ağırlıklı yönlü çizgedir (weighted directed graph). Düğümler şehirleri ya da yönlendiricileri, kenarlar bağlantıları gösterir. Her kenarın bir maliyeti (ağırlığı) vardır. Kenarın yönlü olması gerçekçidir: tek yönlü bir yol ya da yalnız bir yönde yoğun olan bir bağlantı, iki yönde farklı maliyetler doğurur. Bir yolun uzunluğu, üzerindeki kenarların maliyetlerinin toplamıdır. Kenar sayısı burada önemli değildir; üç kenarlı bir yol, tek kenarlı bir yoldan kısa olabilir.

Problemin içinde iki ayrı soru vardır. Birincisi, x'ten y'ye herhangi bir yol var mıdır? Bu bir erişilebilirlik sorusudur ve çizgede önce derinliğine ya da önce genişliğine bir gezinmeyle cevaplanır. İkincisi, birden çok yol varsa en kısası hangisidir? Bu notun konusu ikinci sorudur. Problem birkaç biçimde sorulabilir. Tek kaynaktan tek hedefe sürümünde bir başlangıç ve bir varış düğümü verilir. Tek kaynaktan bütün hedeflere sürümünde bir kaynak düğümden öteki bütün düğümlere giden en kısa yollar istenir. Tüm çiftler arası sürümde ise her düğüm çifti için ayrı bir cevap aranır.

En kısa yol problemi, adı benzeyen başka bir problemle karıştırılmamalıdır. Bütün düğümlere birer kez uğrayıp başlangıca dönen en kısa turu bulmak gezgin satıcı problemidir. Gezgin satıcıda bütün düğümlerin sırası seçilir; en kısa yolda ise yalnız iki düğüm arasındaki güzergâh aranır. İlki için bilinen bütün kesin algoritmalar üstel zaman ister, ikincisi ise çok verimli çözülür.

Not boyunca Şekil 18.1'deki altı düğümlü çizge kullanılır. Bu, Horowitz ve Sahni'nin ders kitabındaki örnektir. 0'dan çıkan kenarlar 1'e (50), 2'ye (10) ve 4'e (45) gider. 2'den 3'e 15 maliyetli, 3'ten 1'e 20 maliyetli kenarlar vardır. 5 numaralı düğümden yalnız çıkan bir kenar vardır (5 → 3); hiçbir düğümden 5'e gelinemez.

0 kaynak alınırsa bütün en kısa yolların uzunlukları Tablo 18.1'de görülür. Sonuçların bazıları çizgeye bir bakışta okunmaz. 0'dan 1'e doğrudan 50 maliyetli bir kenar vardır, ama en kısa yol bu kenar değildir: 0 → 2 → 3 → 1 yolunun uzunluğu 10 + 15 + 20 = 45'tir. Üç kenar, tek kenardan daha ucuzdur. 0'dan 4'e ise doğrudan kenar (45) en iyisidir. 0 → 2 → 3 → 4 yolu 10 + 15 + 35 = 60 tutar. 5'e giden kenar olmadığı için 0'dan 5'e yol yoktur.

Tablonun satırları uzunluğa göre sıralanmıştır. Bu sıralama rastlantı değildir; en verimli algoritma hedefleri tam da bu sırayla bulur. Satırlar arasında bir bağ da göze çarpar. 1'e giden en kısa yol 3'ün en kısa yolundan geçer, 3'ünki de 2'ninkinden. Her en kısa yol, kendinden kısa bir en kısa yolun sonuna tek kenar eklenerek elde edilir. Bu iki gözlem notun ilk yarısının temelidir.

18.2Kaba kuvvet çözümü

Bir problemin akla gelen ilk çözümü çoğu zaman kaba kuvvettir (brute force): bütün adaylar tek tek denenir, en iyisi seçilir. En kısa yol için adaylar, kaynaktan hedefe giden bütün basit yollardır. Basit yol, aynı düğümden iki kez geçmeyen yoldur. Negatif ağırlık yokken en kısa yolun basit olduğu kolayca görülür: bir yol aynı düğüme iki kez uğruyorsa aradaki döngü atılır, uzunluk artmaz. Bu yüzden yalnız basit yolları denemek yeterlidir.

Algoritma tek kaynaklı, tek hedefli sürüm için şöyle kurulur. Kaynaktan başlanır, ziyaret edilmemiş her komşuya geçilir ve hedefe varılınca o yolun uzunluğu en iyi değerle karşılaştırılır. Bu, geri izleme ile yapılan bir önce derinliğine aramadır. Mantık doğrudur, sonuç da doğrudur. Sorun, denenecek yol sayısındadır.

En kötü durum, her düğümün öteki bütün düğümlere bağlı olduğu tam çizgedir (complete graph). n düğümlü tam çizge K_n diye yazılır. Şekil 18.2 K₄ ve K₅'i gösterir. K₄'te 0'dan 3'e beş yol vardır: 0-3, 0-1-3, 0-2-3, 0-1-2-3 ve 0-2-1-3. K₅'te 0'dan 4'e giden yollar ara düğüm sayısına göre sayılır. Ara düğümsüz yol 1 tanedir (0-4). Tek ara düğümlü yollar 3 tanedir; ara düğüm 1, 2 ya da 3 olabilir. İki ara düğümlü yollarda ilk ara düğüm 3, ikincisi 2 biçimde seçilir: 6 yol. Üç ara düğümlü yollarda 1, 2 ve 3'ün bütün sıralamaları denenir: 3! = 6 yol. Toplam 1 + 3 + 6 + 6 = 16 yoldur.

Aynı sayma genel n için de yapılır. Kaynak ve hedef dışında n − 2 düğüm vardır. k ara düğümlü bir yol, bu düğümlerden k tanesinin sıralı seçimidir. Sıralı seçimlerin sayısı (n − 2)(n − 3)⋯(n − 1 − k)'dir. Bütün k değerleri toplanınca yol sayısı bulunur.

Formül bir programla da sınandı. Program, tam çizgede 0'dan n − 1'e giden yolları geri izlemeyle tek tek sayar. Sonuçlar Tablo 18.2'de formülle yan yana verilmiştir; her satırda iki değer aynıdır. Son sütun, aramanın kaç kez bir kenar boyunca ilerlediğini gösterir. Bu sayı yol sayısının yaklaşık iki katıdır, yani iş miktarı yol sayısıyla aynı hızda büyür.

Büyüme faktöriyel hızdadır. 11 düğümde bir milyona yakın yol vardır; 20 düğümde bu sayı 18! ≈ 6 · 10¹⁵ mertebesine çıkar. Saniyede bir milyar yol deneyen bir bilgisayar bile bu kadar yolu yaklaşık iki ayda bitirir. Üstelik bu, tek bir hedef içindir.

Sunumdaki O(nⁿ) gösterimi bu büyümenin kaba ama doğru bir üst sınırıdır. (n − 2)! ≤ nⁿ olduğu için Y(n) = O(nⁿ) yazılabilir. Daha sıkı sınır O((n − 2)!)'dir; ikisi de üsteldir ve pratikte aynı sonucu söyler: bu yol ancak birkaç düğümlük çizgelerde kullanılabilir. Kaba kuvvetin mantığı doğrudur. Ama tek bir hedef için bile bu kadar pahalı olan bir yöntemle problem çözülmez. Daha iyisi için yolların yapısındaki düzen kullanılmalıdır.

18.3Dijkstra algoritması

18.3.1Açgözlü fikir

Kaba kuvvet her yolu baştan kurar. Oysa Tablo 18.1'deki gözlemler daha akıllı bir yol gösterir: en kısa yollar kısadan uzuna doğru bulunabilir ve her yeni yol, daha önce bulunmuş bir yolun bir kenar uzatılmasıdır. Edsger W. Dijkstra 1959'da bu fikirden çok verimli bir algoritma çıkardı. Algoritma açgözlüdür (greedy): her adımda o an en iyi görünen seçimi yapar ve bu seçimi bir daha değiştirmez.

Algoritma bir S kümesi tutar. S, en kısa yolu kesinleşmiş düğümlerden oluşur; başta yalnız kaynak, yani 0 vardır. S dışındaki her w düğümü için bir de uzaklik[w] değeri tutulur.

Tanımdaki kısıt önemlidir: uzaklik[w] bütün yolların değil, yalnız S'nin içinden geçen yolların en kısasıdır. Başta S = {0} olduğu için bu yollar tek kenarlıdır ve uzaklik[w], 0'dan w'ye giden kenarın maliyetine eşittir. Algoritma üç gözleme dayanır.

1. Bir sonraki kesinleşecek u düğümünün en kısa yolu, u dışında yalnız S'deki düğümlerden geçer. Yolun ortasında S dışından bir x bulunsaydı, kaynaktan x'e giden kısım daha kısa olurdu ve x daha önce seçilirdi.
2. Bu yüzden bir sonraki düğüm, S dışında uzaklik değeri en küçük olan düğümdür. Eşitlik varsa herhangi biri seçilebilir.
3. u seçilip S'ye katılınca, u'dan geçen yeni yollar açılır. S dışındaki bir w için uzaklik[u] + maliyet(<u, w>) < uzaklik[w] ise uzaklik[w] bu küçük değerle güncellenir. Yeni yolda u ile w arasında ara düğüm yoktur; u'dan sonra doğrudan w'ye geçilir.

Üçüncü gözlemdeki işleme gevşetme (relaxation) denir. Ad, uzaklik[w]'nin bir üst sınır olmasından gelir: değer gerçek en kısa uzaklıktan hiçbir zaman küçük değildir. Gevşetme bu sınırı aşağı çeker, yani “gerilmiş” bir tahmini gevşetir. Şekil 18.3 bir gevşetme adımını gösterir: yeni katılan u'nun komşuları w₁, w₂, w₃ için u üzerinden yeni yollar denenir.

Birinci gözlemin gerekçesi bir koşula dayanır: kenar ağırlıkları negatif olmamalıdır. Bu koşul olmadan algoritma yanılır. Doğruluğu kesin biçimde ifade etmek için bir teorem yazılabilir.

Kanıtın tek zayıf halkası “kalan kısım 0 ya da daha büyüktür” cümlesidir. Negatif bir kenar bu cümleyi bozar: y'den u'ya negatif bir kenarla inilirse P, uzaklik[u]'dan kısa olabilir. Bu durumun somut bir örneği ve çaresi negatif kenarlar kesiminde verilir.

18.3.2Adım adım bir örnek

Algoritmanın işleyişini görmek için yedi düğümlü küçük bir çizge alınsın. Kenarlar şunlardır: v0 → v1 (10), v1 → v2 (10), v2 → v4 (10), v4 → v5 (10), v0 → v3 (30), v3 → v5 (20), v3 → v6 (2) ve v6 → v5 (10). Kaynak v0'dır. Şekil 18.4 yedi adımın dördünü, Tablo 18.3 hepsini verir. Şekillerde koyu renkli düğümler S'dedir; sağdaki tablo gidildi işaretini (T) ve uzaklik değerini gösterir.

Tablonun iki satırı özellikle öğreticidir. Dördüncü adımda v5'in değeri 50'den 40'a iner. v5'e ilk bulunan yol v0 → v3 → v5'tir (30 + 20). v4 katılınca dört kenarlı v0 → v1 → v2 → v4 → v5 yolu (10 + 10 + 10 + 10) bulunur ve daha kısadır. Bir düğümün değeri, düğüm S'ye girene kadar birkaç kez değişebilir; kesinleşmiş sayılmaz.

Beşinci adımda ise v6, v5'ten önce seçilir. v6'nın numarası daha büyüktür, ama uzaklığı (32) v5'inkinden (40) küçüktür. Seçim sırası düğüm numarasına göre değil, uzaklığa göre belirlenir. Üçüncü ve dördüncü adımlarda ise v3 ile v4'ün uzaklıkları eşittir (30). Kuramsal olarak hangisinin önce seçildiği fark etmez. C kodu eşitlikte küçük numaralı düğümü seçtiği için önce v3 katılır.

18.3.3C gerçeklemesi: veri ve minimumBul

Algoritmanın C sürümü çizgeyi bir maliyet matrisiyle tutar. maliyet[i][j], <i, j> kenarının maliyetidir. Kenar yoksa ∞ yerine büyük bir sabit yazılır; köşegendeki değerler 0'dır. Kesinleşmiş düğümler gidildi dizisinde işaretlenir; S kümesi budur. uzaklik dizisi tanımdaki değerleri taşır. Aşağıdaki kod örnek çizgenin matrisini ve en küçük uzaklıklı işaretsiz düğümü bulan yordamı verir.

#include <limits.h>
#define MAX_DUGUM 6
#define SONSUZ 1000      /* baglanti yok */
int maliyet[][MAX_DUGUM] = {
    {   0,   50,  10, 1000,   45, 1000},
    {1000,    0,  15, 1000,   10, 1000},
    {  20, 1000,   0,   15, 1000, 1000},
    {1000,   20, 1000,   0,   35, 1000},
    {1000, 1000, 1000,  30,    0, 1000},   /* eksik satir */
    {1000, 1000, 1000,   3, 1000,    0}};  /* 100 -> 1000 */
int minimumBul(int uzaklik[], int n, short gidildi[])
{
    int i, min = INT_MAX, pos = -1;
    for (i = 0; i < n; i++)
        if (uzaklik[i] < min && !gidildi[i]) {
            min = uzaklik[i];  pos = i;
        }
    return pos;
}

• Satır 1. INT_MAX sabiti limits.h başlık dosyasındadır; int türünün alabileceği en büyük değerdir. Başlık eklenmezse derleyici INT_MAX'ı tanımaz.
• Satır 2–3. Düğüm sayısı ve sonsuzu temsil eden sabit. SONSUZ için 1000 seçilmiştir; örnekteki hiçbir gerçek yol bu kadar uzun değildir.
• Satır 4–10. Maliyet matrisi. Satır kenarın çıktığı düğümü, sütun vardığı düğümü gösterir. 0. satırdaki 50, 10, 1000, 45 değerleri 0 → 1, 0 → 2, 0 → 3 (kenar yok) ve 0 → 4 kenarlarıdır. İlk boyut boş bırakılmıştır; derleyici satır sayısını ilk değer listesinden çıkarır. İkinci boyut ise yazılmak zorundadır, çünkü derleyici bir satırın kaç int tuttuğunu bilmelidir.
• Satır 11–19. minimumBul. min en büyük int ile, pos da geçersiz bir indisle (−1) başlar. Döngü işaretsiz düğümler arasında uzaklik değeri en küçük olanı arar. Karşılaştırma katı küçüktür (<); eşit değerler arasında ilk görülen, yani küçük numaralı düğüm kalır.

Matrisin iki satırında açıklama vardır. Ders kitabındaki matriste 4. satır eksiktir; bu satır çizgeden okunarak tamamlanmıştır (4'ten tek kenar 4 → 3, maliyet 30). 5. satırda da kitap sonsuz için 100 yazar; öteki satırlarla tutarlı olsun diye 1000'e çevrilmiştir. Ders kitaplarındaki küçük yazım hataları, kodu gerçekten çalıştırınca hemen ortaya çıkar. Kâğıt üzerinde izlenen kodla çalışan kodun aynı olması bu yüzden önemlidir.

SONSUZ değerinin seçimi göründüğünden inceliklidir. İlk akla gelen INT_MAX'tır, ama bu değer gevşetmede taşmaya yol açar: uzaklik[u] + maliyet[u][w] toplamında iki terimden biri INT_MAX ise sonuç int'e sığmaz. C'de işaretli tamsayı taşması tanımsız davranıştır; pratikte değer çoğu zaman negatif bir sayıya döner ve “daha kısa yol bulundu” sanılır. 1000 gibi bir sabitte bu tehlike yoktur: SONSUZ + SONSUZ 2000'dir ve rahatça sığar. Bedeli de vardır: sabit, çizgedeki en uzun gerçek yoldan büyük seçilmelidir. Aksi hâlde gerçek bir yol “yol yok” ile karışır.

Yordamın −1 döndürdüğü tek durum, işaretsiz düğüm kalmamasıdır. Erişilemeyen bir düğüm kalmışsa yordam yine onu seçebilir, çünkü değeri 1000'dir ve INT_MAX'tan küçüktür. Bu zararsızdır. Erişilemeyen düğümün değeri 1000'dir; üzerinden yapılan gevşetmeler 1000'den küçük bir değer üretmez, çünkü ağırlıklar negatif değildir. Yine de çağıran yordam −1 dönüşünü denetlemelidir; denetimsiz bir gidildi[-1] erişimi dizinin dışına yazar.

18.3.4EnKisaYolBul: ana yordam

Ana yordam kaynak düğümü, maliyet matrisini ve üç diziyi alır. uzaklik ve gidildi yukarıdaki anlamlarıyla kullanılır. onceki dizisi ise yolun kendisini bulmak için tutulur; ayrıntısı bir sonraki kesimdedir.

void EnKisaYolBul(int v, int maliyet[][MAX_DUGUM],
                  int uzaklik[], int onceki[],
                  int n, short gidildi[])
{
    int i, u, w;
    for (i = 0; i < n; i++) {                  /* A1 */
        gidildi[i] = FALSE;
        uzaklik[i] = maliyet[v][i];
        onceki[i] = v;             /* yol icin tutulur */
    }
    gidildi[v] = TRUE;  uzaklik[v] = 0;
    for (i = 2; i < n; i++) {        /* n-2 tur */
        u = minimumBul(uzaklik, n, gidildi);
        if (u < 0) break;            /* kalan yok */
        gidildi[u] = TRUE;
        for (w = 0; w < n; w++)
            if (!gidildi[w] &&
                uzaklik[u] + maliyet[u][w] < uzaklik[w]) {
                uzaklik[w] = uzaklik[u] + maliyet[u][w];
                onceki[w] = u;
            }
    }
}

Yordamın dört bölümü vardır ve analizde bu bölümlerin adları kullanılır:

• A1 (satır 6–10). Başlangıç değerleri. Her düğüm işaretsizdir. uzaklik[i], kaynaktan i'ye doğrudan kenarın maliyetidir; bu, S = {v} için tanımın verdiği değerdir. onceki[i] = v atamasıyla her düğümün öncülü başta kaynak sayılır.
• Satır 11. Kaynak işaretlenir, uzaklığı 0 yapılır. Matrisin köşegeni zaten 0'dır; atama yine de açık yazılmıştır, çünkü kod köşegene güvenmemelidir.
• A2 (satır 12). Dış döngü i = 2'den n − 1'e, yani n − 2 tur döner. Kaynak zaten kesindir. Her tur bir düğümü daha kesinleştirir. n − 2 tur sonunda tek bir işaretsiz düğüm kalır. O düğüm için bütün öteki düğümler S'dedir ve tanımdaki değer en kısa yolun kendisidir. Son bir tur yalnız onu işaretlerdi; güncellenecek işaretsiz düğüm kalmadığı için hiçbir şey değişmezdi.
• A3 (satır 13–15). En küçük uzaklıklı işaretsiz düğüm u bulunur ve işaretlenir. −1 dönerse işaretsiz düğüm kalmamıştır, döngüden çıkılır.
• A4 (satır 16–21). Gevşetme. İşaretsiz her w için u üzerinden geçen yol denenir. Daha kısaysa hem uzaklık hem öncül güncellenir.

Satır 17–18'deki koşul iki parçalıdır ve sıra önemlidir. && işleci soldan sağa, kısa devreyle değerlendirilir: gidildi[w] doğruysa toplama hiç yapılmaz. Bu, kesinleşmiş düğümlerin değerlerinin bozulmasını önler. Kesinleşmiş bir düğüme daha kısa bir yol zaten bulunamaz (Teorem 18.2), ama kodun bunu açıkça denetlemesi hem okunurluğu hem güvenliği artırır.

Maliyet matrisi parametresi int maliyet[][MAX_DUGUM] biçiminde yazılmıştır. C bir diziyi fonksiyona kopyalamaz; ilk öğenin adresini geçirir. İki boyutlu bir dizide maliyet[u][w]'nin adresini hesaplamak için satır uzunluğu gerekir: adres, başlangıç + (u · MAX_DUGUM + w) · sizeof(int)'tir. Bu yüzden ikinci boyut parametrede yazılmak zorundadır. Aynı nedenle uzaklik, onceki ve gidildi dizilerine yordamın içinde yapılan atamalar çağıranın dizilerini değiştirir; sonuçlar bu yolla geri döner.

18.3.5Kod izlemesi

EnKisaYolBul(0, maliyet, …) çağrısı örnek çizgede izlenir. Tablo 18.4 her turda seçilen düğümü, yapılan gevşetmeleri ve tur sonundaki uzaklik dizisini verir. Değerler programın her tur sonunda yazdırdığı çıktıdan alınmıştır.

Üçüncü turda 3 üzerinden 4'e de bir yol denenir: 25 + 35 = 60. Bu, 45'ten büyük olduğu için değer değişmez. Dördüncü turda 1 ile 4'ün uzaklıkları eşittir (45). minimumBul katı küçük karşılaştırması yaptığı için ilk gördüğü 1'i seçer. Döngü n − 2 = 4 tur döner ve biter. 5 hiç seçilmemiştir; değeri 1000 kalır ve “yol yok” diye okunur. Şekil 18.5 izlemenin ilk ve son anını gösterir.

Sonuç Tablo 18.1 ile birebir aynıdır: 2 → 10, 3 → 25, 1 → 45, 4 → 45, 5'e yol yok. Seçilme sırası da uzunluk sırasıdır. Kaynak 2 alınırsa uzaklıklar 0'a 20, 3'e 15, 1'e 35 (3 üzerinden), 4'e 45 (3 ve 1 üzerinden) olur; 5'e yine yol yoktur. Bu değerler de programla bulunmuştur.

18.3.6Analiz ve daha iyi veri yapıları

Maliyet her bölüm için ayrı hesaplanır. A1 bir kez n tur döner: O(n). A2'nin dış döngüsü n − 2 tur döner. Her turda A3, yani minimumBul, bütün diziyi tarar: O(n). A4 de her w'yi bir kez dener: O(n). Toplam

n + (n − 2) · (n + n) ≈ n + 2n² = O(n²)

olur. Bu sınır en iyi durumda da geçerlidir: kenar sayısı ne olursa olsun her tur iki tam tarama yapar. Yani algoritmanın süresi Θ(n²)'dir. Ek bellek üç dizidir: O(n). Kaba kuvvetin faktöriyel büyümesiyle karşılaştırıldığında fark çarpıcıdır. 20 düğümde kaba kuvvet aylar sürerken bu yordam birkaç yüz işlemle biter. Matrisin en büyük öğesini bulmak bile n² öğeye bakmayı gerektirir; Dijkstra bütün en kısa yolları aynı mertebede bir sürede bulur.

O(n²) yoğun çizgeler için iyidir. Seyrek çizgelerde ise iki darboğaz vardır. Birincisi A3'tür: en küçük öğeyi bulmak için her turda bütün dizi taranır. Oysa en küçük öğeyi hızlı vermek, min-heap ile gerçeklenen bir öncelikli kuyruğun (priority queue) işidir. Uzaklıklar min-heap'te tutulursa en küçük öğe O(log n)'de alınır. İkincisi A4'tür: matris kullanıldığı için her turda n sütun taranır, oysa gerçekte yalnız u'nun komşuları ilgilenilmesi gereken düğümlerdir. Komşuluk listesi kullanılırsa A4, u'nun çıkış derecesi kadar sürer.

İki iyileştirme birlikte uygulanınca toplam maliyet kolayca yanlış hesaplanır. Sık yapılan hata sonucu O(n log n) sanmaktır. Doğru hesap şöyledir. Her düğüm heap'ten bir kez alınır: n kez O(log n). Her kenar bir kez gevşetilir ve başarılı her gevşetme heap'teki bir değeri küçültür; bu da O(log n) sürer. Kenar sayısı e olduğundan toplam

O(n log n + e log n) = O((n + e) log n)

olur. Fibonacci heap adlı daha karmaşık bir yapı değer küçültmeyi ortalama O(1)'e indirir ve sınırı O(e + n log n)'ye çeker. Tablo 18.5 üç yaklaşımı yan yana koyar.

Hangi sürümün daha iyi olduğu çizgeye bağlıdır. Seyrek bir çizgede, örneğin bir yol haritasında, her düğümün birkaç komşusu vardır ve e, n mertebesindedir. Heap sürümü burada O(n log n)'e iner ve dizi sürümünü açık farkla geçer. Yoğun bir çizgede ise e ≈ n² olur ve heap sürümü O(n² log n)'ye çıkar; basit dizi sürümü daha hızlıdır. Öncelikli kuyruk öğrenildikten sonra dizide en küçük öğeyi aramak hantal görünebilir. Ama doğru soru “hangi yapı daha zarif?” değil, “bu çizgede hangi işlem kaç kez yapılıyor?” sorusudur.

18.4Yolu bulmak: öncüller dizisi

18.4.1Tek dizi neden yeter?

EnKisaYolBul uzunlukları bulur, ama yolcu yalnız uzunlukla yetinmez; hangi şehirlerden geçeceğini de bilmek ister. Maliyet bulunduktan sonra sıra yoldadır. İlk akla gelen, her düğüm için yolun bütün düğümlerini ayrı bir listede tutmaktır. Bu hem bellek israfıdır hem de her güncellemede listeyi kopyalamayı gerektirir. Yolu kaynaktan ileri doğru kurmak da mümkün değildir: kaynaktan çıkarken hangi kenardan gidileceği, algoritma bitene kadar belli olmaz.

Çözüm tek bir dizidir. Her düğümün en kısa yolu, öncülünün (predecessor) en kısa yolunun sonuna tek bir kenar eklenerek elde edilir. Bu yüzden her düğüm için yalnız yoldaki bir önceki düğümü saklamak yeterlidir.

Tek dizinin yetmesinin nedeni en kısa yolların bir özelliğidir. Kaynaktan h'ye giden bir en kısa yol u'dan geçiyorsa, bu yolun kaynaktan u'ya kadarki parçası da kaynaktan u'ya bir en kısa yoldur. Parça daha kısa bir yolla değiştirilebilseydi bütün yol da kısalırdı. Bu özelliğe en iyi alt yapı (optimal substructure) denir. Sonuç olarak bütün en kısa yollar bir ağaç oluşturur. Kökü kaynaktır ve her düğümün ebeveyni öncülüdür. Bu ağaca en kısa yol ağacı denir. Öncüller dizisi, kümeler için kullanılan ebeveyn dizisi gibi, bu ağacın her düğümünden ebeveynine giden bağları tutar.

Dizi gevşetme sırasında güncellenir. EnKisaYolBul'un 20. satırı, gevşetme başarılı olduğunda onceki[w] = u atamasını yapar: w'ye giden en iyi yol artık u'dan geçer. Maliyet değiştikçe öncül de değişir. Örnekte 1'in değeri 50'den 45'e inerken öncülü de 0'dan 3'e geçmiştir. Algoritma bittiğinde örnek çizge için öncüller dizisi onceki = {0, 3, 0, 2, 0, 0} olur. 1'in öncülü 3, 3'ünki 2, 2'ninki 0'dır.

Dizi ileriye değil geriye doğru okunur. Hedeften başlanıp öncüllere yürünerek kaynağa varılır: 1 ← 3 ← 2 ← 0. Bu sıra yolun tersidir. Doğru sırada yazmak için ya özyineleme ya da bir yığın kullanılır. İkisi de aynı ilkeye dayanır: son giren ilk çıkar.

18.4.2Özyinelemeli yol yazdırma

Özyinelemeli çözüm kısa ve zariftir:

void yol_yaz(int onceki[], int s, int h)
{
    if (h == s) {
        printf("%d", s);
        return;
    }
    yol_yaz(onceki, s, onceki[h]);   /* once oncul */
    printf(" -> %d", h);
}

• Satır 3–6. Temel durum: hedef kaynağın kendisiyse yol tek düğümdür; kaynak yazılır ve dönülür.
• Satır 7. Önce öncüle kadar olan yol yazdırılır. Özyinelemeli çağrı, h'yi öncülüyle değiştirerek kaynağa bir adım yaklaşır.
• Satır 8. Öncüle kadarki yol yazıldıktan sonra h yazılır. Yazma işi çağrıdan sonra yapıldığı için düğümler geri dönüş sırasında, yani kaynaktan hedefe doğru çıkar.

Yordamın doğru çalışması, öncül zincirinin sonunda kaynağa varmasına bağlıdır. Erişilebilen her düğüm için bu böyledir, çünkü öncüller en kısa yol ağacının ebeveyn bağlarıdır. Erişilemeyen bir düğümde ise onceki değeri anlamsızdır. Örnekte onceki[5] = 0'dır, ama 0'dan 5'e yol yoktur; bu değer A1'deki başlangıç atamasından kalmıştır. yol_yaz(onceki, 0, 5) çağrılırsa “0 -> 5” gibi gerçekte var olmayan bir yol yazılır. Bu yüzden çağıran yordam önce uzaklik[h] >= SONSUZ koşulunu denetlemeli, öyleyse “yol yok” yazmalıdır.

yol_yaz(onceki, 0, 1) çağrısının izlemesi Tablo 18.6'dedir. Çağrı yığını sütununda en soldaki çerçeve en eski, en sağdaki en yeni çağrıdır.

İzleme yolun hedeften geriye yürünerek bulunduğunu, yazarken ise çağrı yığınının sırayı düzelttiğini gösterir. Yolun maliyeti 10 + 15 + 20 = 45'tir ve uzaklik[1] ile tutarlıdır. Şekil 18.6 öncül bağlarını çizge üzerinde gösterir.

Yordamın maliyeti yolun uzunluğuyla orantılıdır. Yolda k kenar varsa k + 1 çağrı yapılır ve her çağrı sabit iş yapar: O(k). k en çok n − 1 olabilir. Çağrı yığınının derinliği de k + 1'dir; bu yüzden ek bellek de O(k)'dir.

18.4.3Yığınla yol yazdırma

Aynı iş özyineleme kullanmadan, açık bir yığınla da yapılır. Önce hedeften kaynağa yürünür ve geçilen düğümler yığına konur. Sonra kaynak yazılır ve yığındaki düğümler çıkış sırasıyla yazılır. Yığın, öncül zincirinin sırasını tersine çevirir.

void yol_yaz_yigin(int onceki[], int s, int h)
{
    int yigin[MAX_DUGUM], ust = -1;
    while (h != s) {                  /* hedeften kaynaga yuru */
        yigin[++ust] = h;
        h = onceki[h];
    }
    printf("%d", s);
    while (ust >= 0)                  /* ters sirada yaz */
        printf(" -> %d", yigin[ust--]);
}

Yığın burada bir dizi ile bir ust indisinden oluşur. yigin[++ust] = h ifadesi önce ust'ü artırır, sonra o hücreye yazar; bu bir ekleme (push) işlemidir. yigin[ust--] ise önce hücreyi okur, sonra ust'ü azaltır; bu bir çıkarma (pop) işlemidir. Yolda en çok n − 1 kenar olduğu için MAX_DUGUM boyutlu dizi yeter. Program, örnek çizgedeki dört erişilebilir hedef için iki yordamın aynı çıktıyı verdiğini doğruladı. Özyinelemeli sürüm daha kısadır, yığınlı sürüm ise çağrı yığınının derinliğine bağlı değildir. Çok uzun yolların olabileceği büyük çizgelerde ikincisi daha güvenlidir.

18.4.4Küçük yordamlar ve yazılım kalitesi

Bu bölümdeki kodlar bilinçli olarak küçük yordamlara bölünmüştür: minimumBul, EnKisaYolBul, yol_yaz. Her biri tek bir iş yapar ve ayrı ayrı sınanabilir. Bölmenin değeri en çok hatalı örneklerde anlaşılır. Bir sınavda en kısa yol sorusunu tek bir büyük özyinelemeli yordamla çözmeye çalışan öğrencilerin kodları çoğu zaman ne okunabildi ne de çalıştı. Bazı çözümlerde de yordam AgirlikBul(…); biçiminde çağrılmıştı. Yordam bir int döndürüyordu, ama dönen değer hiçbir değişkene atanmamıştı; değer hesaplanıp kayboluyordu. Derleyici böyle bir satırı hata saymaz. Hatayı ancak kodu okuyan biri görür.

Yazılım mühendisliği, bir çözümün yalnız doğru değil, aynı zamanda modüler, basit, okunabilir, yeniden kullanılabilir ve bakımı kolay olmasını ister. Bu nitelikler ders kitaplarında İngilizce adlarıyla listelenir. Tablo 18.7 en sık geçenleri Türkçe karşılıklarıyla verir.

Tablodaki niteliklerin çoğu küçük yordamlarla doğrudan ilgilidir. minimumBul ayrı bir yordam olduğu için heap sürümüne geçerken yalnız onun değiştirilmesi yeter: değiştirilebilirlik. yol_yaz ayrı olduğu için kendi başına küçük bir öncül dizisiyle sınanabilir: sınanabilirlik. Fonksiyonların dönüş değerlerinin kullanılması, NULL denetimleri ve açıklama satırları da güvenilirliğin ve anlaşılabilirliğin parçasıdır.

18.5Negatif kenarlar ve tüm çiftler

18.5.1Dijkstra negatif kenarda neden yanılır?

Gerçek problemlerde kenar ağırlığı her zaman bir uzunluk değildir. Bir kenar kazancı, bir enerji geri kazanımını ya da bir indirimi gösterebilir; bu durumda ağırlık negatif olur. Dijkstra'nın doğruluk kanıtı negatif olmayan ağırlıklara dayanıyordu. Şekil 18.7'deki dört düğümlü çizge bu varsayım bozulunca ne olduğunu gösterir. Kenarlar 0 → 1 (4), 0 → 2 (5), 1 → 3 (2) ve 2 → 1 (−3)'tür.

Dijkstra'nın izlemesi programla yapıldı. Başta uzaklıklar 1 için 4, 2 için 5, 3 için ∞'dur. İlk turda en küçük değerli 1 seçilir (4) ve kesinleşir; 1 üzerinden 3'ün değeri 6 olur. İkinci turda 2 seçilir (5). 2 → 1 kenarı 5 − 3 = 2 değerinde bir yol açar, ama 1 artık işaretlidir; gevşetme yapılmaz. Sonuç Tablo 18.8'dedir: 1 ve 3 yanlıştır.

Hatanın kaynağı açgözlü seçimin varsayımıdır. Dijkstra, seçtiği düğüme daha sonra daha ucuz bir yoldan gelinemeyeceğini varsayar. Ağırlıklar negatif değilse bu doğrudur: henüz seçilmemiş düğümler daha uzaktadır ve onlardan geçen yol ancak uzayabilir. Negatif bir kenar ise uzaktaki bir düğümden geri dönüp yolu kısaltabilir. 1'in yanlış değeri 3'e de geçer, çünkü 3'ün yolu 1'den geçer. Ağırlıkların hepsine aynı sabit eklenerek negatiflikten kurtulmak da çözüm değildir. Bu dönüşüm çok kenarlı yolları tek kenarlılardan daha fazla cezalandırır ve en kısa yolun kendisini değiştirir.

Negatif kenarlarda bir tehlike daha vardır: negatif döngü (negative cycle). Ağırlıkları toplamı negatif olan bir döngü kaynaktan erişilebilir durumdaysa, döngüde her dönüş yolu biraz daha kısaltır. Bu durumda en kısa yol tanımsızdır; “en küçük” uzunluk yoktur, değer sınırsız azalır. İyi bir algoritma böyle bir döngüyü bulup bildirebilmelidir.

18.5.2Bellman-Ford algoritması

Richard Bellman ve Lester Ford'un adıyla anılan algoritma açgözlü değildir; hiçbir düğümü erken kesinleştirmez. Bunun yerine bütün kenarları defalarca gevşetir. Algoritma kenarları bir kenar listesinde tutar. Her öğe kenarın iki ucunu ve ağırlığını taşır:

typedef struct {
    int u, v, w;        /* kenar <u,v>, agirlik w */
} kenar;
int BellmanFord(kenar K[], int n, int e, int s, int d[])
{
    int i, j, t, u, v;
    for (i = 0; i < n; i++) d[i] = SONSUZ;
    d[s] = 0;
    for (t = 1; t <= n - 1; t++)          /* n-1 tur */
        for (j = 0; j < e; j++) {
            u = K[j].u;  v = K[j].v;
            if (d[u] != SONSUZ && d[u] + K[j].w < d[v])
                d[v] = d[u] + K[j].w;
        }
    for (j = 0; j < e; j++)               /* n. tur */
        if (d[K[j].u] != SONSUZ &&
            d[K[j].u] + K[j].w < d[K[j].v]) return -1;
    return 0;              /* -1: negatif dongu var */
}

Kodun gövdesi sunumdaki parçanın aynısıdır; çevresine yalnız yordam başlığı ve yerel değişkenler eklenmiştir. K kenar listesi, n düğüm sayısı, e kenar sayısı, s kaynak, d de sonuç dizisidir.

• Satır 7–8. Bütün uzaklıklar sonsuz, kaynağınki 0 yapılır. Başlangıçta yalnız kaynağa ulaşılabildiği bilinir.
• Satır 9–14. Ana döngü n − 1 tur döner. Her turda bütün kenarlar sırayla gevşetilir. Koşulun ilk parçası d[u] != SONSUZ, henüz ulaşılmamış bir düğümden yapılan gevşetmeyi engeller. Bu denetim negatif kenarlar yüzünden zorunludur: SONSUZ + (−3) sonsuzdan küçüktür ve denetim olmasaydı ulaşılmamış bir düğüm “ulaşılmış” görünürdü.
• Satır 15–17. n. tur: kenarlar bir kez daha denenir, ama bu kez değer değiştirilmez. Bir kenar hâlâ gevşeyebiliyorsa negatif bir döngü vardır ve yordam −1 döndürür.
• Satır 18. Döngü yoksa 0 döner; d dizisi en kısa uzaklıkları taşır.

Neden tam n − 1 tur? Negatif döngü yoksa her en kısa yol basit seçilebilir ve basit bir yolda en çok n − 1 kenar vardır. Gevşetmenin yaptığı iş bir yolu kenar kenar ilerletmektir.

Teoremin tersi döngü testini açıklar. Negatif döngü yoksa n − 1 turdan sonra bütün değerler kesindir ve hiçbir kenar gevşeyemez. n. turda bir kenar hâlâ gevşiyorsa varsayım bozulmuştur: erişilebilir bir negatif döngü vardır. Program bu durumu 1 → 2 → 1 döngüsünün toplamı −1 olan bir çizgede denedi; yordam −1 döndürdü.

Örnek çizgedeki izleme Tablo 18.9'dedir. Kenar listesinin sırası 0 → 1, 0 → 2, 1 → 3, 2 → 1'dir; sonuç bu sıraya bağlı değildir, ama ara değerler bağlıdır.

İkinci turdaki gevşeme önemlidir. 3'ün değeri ilk turda 1'in eski değeri (4) üzerinden 6 olmuştu. 1'in değeri aynı turda 2'ye inince, 3'ün doğru değeri ancak bir sonraki turda görülebildi. Kenarların sırası buna yol açar: 1 → 3 kenarı listede 2 → 1'den önce gelir. Sıra farklı olsaydı doğru değerler daha erken bulunabilirdi. Algoritmanın garantisi, sıra ne olursa olsun n − 1 turun yettiğidir. Şekil 18.8 izlemenin son durumunu gösterir.

Maliyet açıktır: n − 1 turun her birinde e kenar denenir, son tur da e kenar dener. Toplam O(n · e)'dir. Ek bellek d dizisidir: O(n). Yoğun bir çizgede e ≈ n² olduğu için süre O(n³)'e çıkar. Bellman-Ford bu yüzden Dijkstra'dan yavaştır; yalnız negatif ağırlıklar varken ya da negatif döngü aranırken tercih edilir. Pratikte bir turda hiçbir değer değişmezse döngüden erken çıkmak da sık kullanılan bir iyileştirmedir. Örnekte üçüncü tur hiçbir şey değiştirmemiştir; bu iyileştirmeyle algoritma orada durabilirdi.

18.5.3Tüm çiftler: Floyd-Warshall algoritması

Bazen tek bir kaynak yetmez; bir yol haritasındaki uzaklık tablosu gibi her düğüm çifti için en kısa uzunluk istenir. Bu, tüm çiftler arası en kısa yollar (all-pairs shortest paths) problemidir. Dijkstra'yı her düğümden bir kez çalıştırmak bir çözümdür, ama negatif kenar varsa işe yaramaz. Robert Floyd ve Stephen Warshall'ın adıyla anılan algoritma problemi çok kısa bir kodla çözer.

Algoritmanın fikri, yollarda kullanılabilecek ara düğümleri birer birer serbest bırakmaktır.

A^k ile A^k−1 arasındaki bağ iki durumla kurulur. i'den j'ye en kısa yol k'den geçmiyorsa ara düğümleri k − 1'e kadardır ve uzunluğu A^k−1[i][j]'dir. k'den geçiyorsa yol iki parçaya ayrılır: i'den k'ye ve k'den j'ye. Negatif döngü olmadığı için iki parça da k'yi ara düğüm olarak kullanmaz ve uzunlukları A^k−1'de bulunur. Böylece

A^k[i][j] = min { A^k−1[i][j], A^k−1[i][k] + A^k−1[k][j] }

bağıntısı elde edilir. Bu bağıntıyı k = 0, 1, …, n − 1 için sırayla uygulamak bir dinamik programlama çözümüdür: büyük problem, sonuçları bir tabloda saklanan küçük alt problemlerden kurulur. Aⁿ⁻¹ bütün düğümlerin ara düğüm olabildiği durumdur ve sonucun kendisidir.

void Floyd(int maliyet[][MAX_DUGUM], int A[][MAX_DUGUM], int n)
{
    int i, j, k;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            A[i][j] = maliyet[i][j];
    for (k = 0; k < n; k++)              /* ara dugum k */
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                if (A[i][k] + A[k][j] < A[i][j])
                    A[i][j] = A[i][k] + A[k][j];
}

• Satır 4–6. A matrisine maliyet matrisi kopyalanır; bu A⁻¹'dir.
• Satır 7. Dış döngü ara düğümü seçer. Döngülerin sırası önemlidir: k en dışta olmalıdır. Her k turu, bir önceki turun bütün matrisini kullanır.
• Satır 8–11. Her (i, j) çifti için k üzerinden geçen yol denenir; kısaysa yazılır.

Bağıntı A^k−1 ve A^k diye iki ayrı matrisle yazılmıştır, ama kod tek bir A matrisini yerinde günceller. Bu güvenlidir. k. turda A[i][k] ve A[k][j] değişmez, çünkü A[i][k] + A[k][k] ifadesinde A[k][k] = 0'dır ve toplam A[i][k]'dan küçük olamaz. Tur boyunca okunan değerler bu yüzden A^k−1'deki değerlerle aynıdır.

Algoritma Horowitz'in üç düğümlü örneğinde izlenir. Maliyet matrisinde 0 → 1 = 4, 0 → 2 = 11, 1 → 0 = 6, 1 → 2 = 2, 2 → 0 = 3'tür ve 2'den 1'e doğrudan kenar yoktur. Program her k turunda değişen hücreleri yazdırdı; her turda yalnız bir hücre değişti (Tablo 18.10).

Her değişiklik bir yolun keşfidir. k = 0'da 2'den 1'e 0 üzerinden bir yol bulunur: 2 → 0 → 1. k = 1'de 0'dan 2'ye 1 üzerinden geçmek doğrudan kenardan ucuzdur. k = 2'de 1'den 0'a 2 üzerinden giden yol (2 + 3 = 5) doğrudan kenardan (6) kısadır. Bu değişikliğin ancak k = 2 turunda olabilmesinin nedeni basittir: yol 2'yi ara düğüm olarak kullanır ve 2'nin kullanılması bu turda serbest kalır. Şekil 18.9 başlangıç ve bitiş matrislerini gösterir.

Analiz kısadır: üç iç içe döngünün her biri n tur döner. Süre Θ(n³)'tür ve çizgenin kenar sayısına bağlı değildir. Bellek n × n matristir. Aynı yordam altı düğümlü ana örneğe de uygulandı. Matrisin 0. satırı 0 45 10 25 45 1000 çıktı; Dijkstra'nın sonucuyla aynıdır. 5. satır 58 23 38 3 33 0'dır: 5'ten çıkan tek kenar 3'e gittiği için 5'in bütün yolları 3'ten geçer. 5. sütundaki 1000'ler ise hiçbir düğümden 5'e gidilemediğini gösterir.

Floyd-Warshall negatif kenarlara izin verir, negatif döngüye vermez. Negatif döngü varsa çalıştırma sonunda köşegende negatif bir değer belirir: bir düğümden kendine negatif uzunlukta bir yol bulunmuştur. Bu, döngünün varlığını sınamanın basit bir yoludur.

18.5.4Hangi algoritma, ne zaman?

En kısa yol için tek bir “en iyi” algoritma yoktur. Seçim problemin biçimine ve çizgenin yapısına bağlıdır. Tablo 18.11 karar için bir özet verir.

İlk satır bir hatırlatmadır: bütün kenarların ağırlığı eşitse en kısa yol, en az kenarlı yoldur. Önce genişliğine arama düğümleri kaynaktan kenar sayısı sırasıyla ziyaret ettiği için bu yolu doğrusal zamanda bulur. Beşinci satır ise notun ikinci yarısının konusudur. Çizgede döngü yoksa düğümler, her kenarın başlangıcı bitişinden önce gelecek biçimde sıralanabilir. Bu sırada her düğümün kenarları bir kez gevşetilirse, bir düğüme gelindiğinde onun bütün öncülleri zaten kesinleşmiştir. Kenar ağırlıkları negatif olsa bile tek geçiş yeter. Aktivite ağlarındaki zaman hesapları tam olarak bu fikre dayanır.

18.6Aktivite ağları ve topolojik sıra

18.6.1Proje ve aktiviteler

Büyük bir iş, daha küçük işlerin toplamıdır. Bir binanın inşaatı temel atmakla başlar; temel donduktan belli bir süre sonra ilk kat, ardından ikinci kat dökülür. Elektrik tesisatı duvarlar örülmeden çekilemez, ama boya ile bahçe düzenlemesi aynı anda yürüyebilir. Bir üniversite programı da böyledir: mezuniyet, derslerin her birinin geçilmesiyle gelir ve bazı derslere ancak başka dersler alındıktan sonra girilebilir. Bu küçük işlere aktivite (activity), aktivitelerin bütününe proje denir. Proje, aktivitelerinin hepsi bitince biter.

Proje yöneticisinin soruları bellidir. İşler hangi sırayla yapılabilir? Proje en erken ne zaman biter? Hangi işler kritiktir, yani bir gün gecikirse bütün proje bir gün gecikir? Hangi işlerde bolluk vardır, yani biraz gecikse de bir şey olmaz? Bu soruları cevaplamak için aktiviteler ile aralarındaki önce-sonra ilişkileri bir çizgeyle gösterilir. Bu çizgeye aktivite ağı (activity network) denir.

Tablo 18.12 bir bilgisayar bilimi programının on beş dersini ve ön koşullarını verir. Örnek, Horowitz ve Sahni'nin kitabından alınmıştır; ders adları da orada olduğu gibi İngilizce bırakılmıştır.

18.6.2Düğümde aktivite ağları ve öncül ilişkisi

Tablodaki bilgiyi çizgeye çevirmenin doğal yolu, her dersi bir düğüm yapmaktır. i dersi j'nin ön koşuluysa i'den j'ye yönlü bir kenar çizilir. On beş düğümlü ve on dört kenarlı çizge Şekil 18.10'dedir.

Ağdaki ilişkileri adlandırmak için birkaç terim gerekir. Bunlar aile ilişkilerine benzer, ama yön kenarlarla belirlenir.

Ders ağında C3 ve C6, C7'nin yakın öncülleridir. C9, C10, C12 ve C13 C7'nin yakın ardıllarıdır. C14 ise C3'ün ardılıdır, ama yakın ardılı değildir: C3'ten C14'e C3 → C7 → C13 → C14 yoluyla varılır. Şekil 18.11 C7'nin yakın öncül ve ardıllarını vurgular. Öncül ilişkisinin iki temel özelliği vardır.

• Geçişlilik. i, j'nin; j de k'nin öncülüyse i, k'nin öncülüdür. C1 C3'ün, C3 C7'nin ön koşuluysa C1 de dolaylı olarak C7'nin ön koşuludur.
• Döngüsüzlük. Hiçbir aktivite kendisinin öncülü olamaz. A, B'nin öncülüyse B, A'nın öncülü olamaz: A bitmeden B başlayamaz, B bitmeden A başlayamaz ve proje hiç bitmez. Bu, çizgede yönlü döngü bulunmaması demektir.

İkinci özellik yalnız kuramsal bir koşul değildir; gerçek projelerde planlama hatası olarak sık görülür. Yönlü döngü içermeyen yönlü çizgeye yönlü döngüsüz çizge (directed acyclic graph, DAG) denir. Geçerli bir AoV ağı her zaman bir DAG'dir. Bu yüzden ağ kurulurken döngü bulunup bulunmadığı denetlenmelidir.

Ders örneğinin sayısal analiz ve doğrusal cebir gibi derslerle örülmüş olması bir rastlantı değildir. Proje planlaması, kaynak dağıtımı ve en kısa yol gibi konuların kökü yöneylem araştırmasına uzanır. Yöneylem ve sayısal analiz derslerinin müfredatlardan çıkarılması, öğrencilerin bu tür problemlerin matematiğinde zayıf kalmasına yol açar.

18.6.3Topolojik sıra

Ders ağı bir öğrencinin önüne pratik bir soru koyar: dersler hangi sırayla alınabilir? Sıra, her dersin ön koşullarının kendisinden önce geldiği bir sıra olmalıdır.

Tanımın üç sonucu vardır. Birincisi, topolojik sıra çoğu zaman tek değildir. Aralarında öncül ilişkisi olmayan iki aktivite herhangi bir sırada yazılabilir. İkincisi, çizgede yönlü döngü varsa topolojik sıra yoktur. Döngüdeki düğümlerden hangisi önce yazılırsa yazılsın, döngüdeki bir kenar ters yöne bakar. Üçüncüsü, döngü yoksa en az bir topolojik sıra vardır; bunun kanıtı aşağıdaki algoritmadır.

Ders ağı için iki geçerli sıra şunlardır:

• C1, C2, C4, C5, C3, C6, C8, C7, C10, C13, C12, C14, C15, C11, C9
• C4, C5, C2, C1, C6, C3, C8, C15, C7, C9, C10, C11, C12, C13, C14

Bir sıranın topolojik olup olmadığı kolayca sağlanır. Her düğümün sıradaki yeri bulunur. Sonra her <i, j> kenarı için i'nin yerinin j'ninkinden küçük olduğu denetlenir. Ders ağında 14 kenar vardır ve iki sıra da 14 kenarın hepsini sağlar; bu denetim bir programla yapıldı. Aynı ağa aşağıda yazılacak TopolojikSira yordamı uygulanınca üçüncü bir geçerli sıra çıktı: C15, C4, C5, C6, C2, C1, C3, C8, C7, C13, C14, C12, C10, C11, C9. Üç sıranın üçü de geçerlidir; hangisinin çıkacağı yalnız algoritmanın düğümleri seçme biçimine bağlıdır.

Topolojik sıranın kullanım alanı geniştir. Ders planlaması bunlardan yalnız biridir. Bir yazılım projesinde kaynak dosyaların derlenme sırası (make aracının yaptığı iş), bir işletim sisteminde görevlerin zamanlanması ve bir hesap tablosunda hücrelerin yeniden hesaplanma sırası da topolojik sıradır. Hesap tablosunda bir hücrenin formülü başka hücrelere başvuruyorsa o hücreler önce hesaplanmalıdır; iki hücre birbirine başvuruyorsa program “döngüsel başvuru” hatası verir. Bu, AoV ağındaki döngünün bir başka yüzüdür. Aktivite ağlarındaki en erken zaman hesabı da topolojik sırada yapılır.

18.6.4Öncülsüz düğümü silme yöntemi

Topolojik sırayı bulmanın yolu basit bir gözleme dayanır: sıranın ilk düğümünün hiç öncülü olamaz. Öyleyse öncülü olmayan bir düğüm seçilip yazılır. Sonra bu düğüm ve ondan çıkan kenarlar çizgeden silinir. Kalan çizge de bir AoV ağıdır ve aynı işlem onda tekrarlanır. Bütün düğümler yazılınca sıra tamamlanmış olur.

Yöntem altı düğümlü bir ağda izlenir (Şekil 18.12). Kenarlar <0,1>, <0,2>, <0,3>, <1,4>, <2,4>, <2,5>, <3,4>, <3,5>'tir.

Başta yalnız v0'ın öncülü yoktur ve ilk o yazılır. v0'ın üç kenarı silinince v1, v2 ve v3'ün öncülü kalmaz. Üçünden herhangi biri seçilebilir; örnekte v3 seçilmiştir. v3'ün kenarları <3,4> ve <3,5> silinir. Sonra v2, ardından v5, v1 ve en son v4 yazılır. Sonuç v0, v3, v2, v5, v1, v4'tür. Programla sayıldığında bu küçük ağın 14 farklı topolojik sırası olduğu görüldü; seçim her adımda farklı yapılarak hepsine ulaşılabilir.

Yöntem döngüyü de bulur. Bir adımda henüz yazılmamış düğümler varken hiçbiri öncülsüz değilse, kalan çizgede her düğümün en az bir öncülü vardır. Öncüllerden geriye doğru yüründüğünde sonlu sayıda düğüm olduğu için bir düğüme ikinci kez gelinir: bu bir yönlü döngüdür. Tersi de doğrudur: döngü yoksa her adımda en az bir öncülsüz düğüm bulunur ve yöntem bütün düğümleri yazar. Böylece yöntem hem sırayı bulur hem de ağın geçerli olup olmadığını sınar.

Yöntemin verimli bir koda dönüşmesi için iki işlemin hızlı yapılması gerekir: öncülsüz düğümü bulmak ve bir düğümün çıkan kenarlarını silmek. Her adımda bütün düğümler taranıp öncülsüz olan aranırsa maliyet O(n²)'ye çıkar. Daha iyisi, her düğümün kaç öncülü kaldığını bir sayaçta tutmak ve sayacı sıfıra düşen düğümleri ayrı bir yerde biriktirmektir.

18.6.5Veri yapısı: sayaçlı başlıklar

Çizge komşuluk listesiyle tutulur. Her düğümün bir başlık öğesi vardır. Başlıkta listenin ilk öğesini gösteren bağın yanında bir de sayac alanı bulunur. Bu alan düğümün kaç yakın öncülü olduğunu, yani giriş derecesini (in-degree) tutar.

typedef struct oge *oge_gost;
typedef struct oge {
    int dugum;
    oge_gost bag;
} oge;
typedef struct {
    int sayac;      /* <i,j> icin: basi j olan kenar sayisi */
    oge_gost bag;
} basoge;
basoge baslik[MAX_DUGUM];

• Satır 1. oge_gost, bir liste öğesini gösteren işaretçi türüdür. Tür adı, yapı tanımlanmadan önce bildirilebilir; C buna eksik tür (incomplete type) üzerinden izin verir. Böylece yapının içinde kendi türünü gösteren bir alan yazılabilir.
• Satır 2–5. Liste öğesi: kenarın vardığı düğüm (dugum) ve listedeki bir sonraki öğe (bag).
• Satır 6–9. Başlık öğesi: öncül sayacı ve listenin başı. Başlıklar bir dizide durur; liste öğeleri ise malloc ile heap bellekten alınır.
• Satır 10. Bütün düğümlerin başlıkları. Küresel bir dizi olduğu için program başlarken bütün alanları sıfırdır: sayaçlar 0, bağlar NULL'dur.

Kenarlar okunurken her <i, j> için i'nin listesine j eklenir ve baslik[j].sayac bir artırılır. Ders kitabı bu adımı ayrıca yazmaz; aşağıdaki yordam onu tamamlar. Öğeyi listenin sonuna ekler, böylece listeler kenarların veriliş sırasını korur.

int kenar_ekle(basoge baslik[], int i, int j)
{
    oge_gost *son = &baslik[i].bag;   /* bag alaninin adresi */
    oge_gost yeni = malloc(sizeof(oge));
    if (yeni == NULL)
        return 0;                     /* bellek yetmedi */
    yeni->dugum = j;
    yeni->bag = NULL;
    while (*son != NULL)              /* listenin sonunu bul */
        son = &(*son)->bag;
    *son = yeni;
    baslik[j].sayac++;                /* j'nin bir onculu daha var */
    return 1;
}

Yordamın ilginç yanı son değişkenidir. son bir öğeyi değil, bir bağ alanını gösterir; türü işaretçinin işaretçisidir (oge_gost *). Başta baslik[i].bag alanının adresini tutar. Liste boşsa bu alan NULL'dur ve yeni öğe doğrudan oraya yazılır. Liste boş değilse döngü her adımda bir sonraki öğenin bag alanına geçer ve NULL olan son bağda durur. *son = yeni ataması, boş liste ile dolu listeyi aynı satırla karşılar. İşaretçinin işaretçisi kullanılmasaydı boş liste için ayrı bir if yazmak gerekirdi.

malloc'un dönüşü her zaman denetlenmelidir. Bellek yetmezse malloc NULL döndürür ve yeni->dugum ataması tanımsız davranışa yol açar. Yordam bu durumda 0 döndürerek çağırana haber verir. Ekleme listenin sonuna yapıldığı için bir düğümün çıkış derecesi d ise maliyet O(d)'dir. Başa ekleme O(1) sürerdi, ama listeler kenarların tersi sırasında olurdu; bu da topolojik sıranın çıktısını değiştirirdi.

Altı düğümlü ağın kenarları <0,1>, <0,2>, <0,3>, <1,4>, <2,4>, <2,5>, <3,5>, <3,4> sırasıyla eklenince Şekil 18.13'teki yapı oluşur. v3'ün listesinde v5'in v4'ten önce gelmesi, kenarların bu sırayla verilmesindendir. Sayaçlar 0, 1, 1, 1, 3, 2'dir: v4'ün üç öncülü (v1, v2, v3), v5'in iki öncülü (v2, v3) vardır.

Bellekte her liste öğesi bir int ve bir işaretçiden oluşur. 64 bitlik bir sistemde int 4 bayt, işaretçi 8 bayttır. İşaretçi 8'in katı bir adreste durmak zorunda olduğu için int'ten sonra 4 baytlık bir dolgu eklenir ve sizeof(oge) 16 olur. Başlık öğesi de aynı nedenle 16 bayttır. Bu değerler zig cc derleyicisiyle x86-64'te ölçüldü. Altı düğüm ve sekiz kenarlık ağ başlıklar için 96, liste öğeleri için 128 bayt kullanır. Toplam bellek O(n + e)'dir.

Listeler artık gerekmediğinde bellek geri verilmelidir. Aşağıdaki yordam her listeyi baştan sona gezer ve öğeleri tek tek bırakır:

void listeleri_birak(basoge baslik[], int n)
{
    int i;
    oge_gost p, sonraki;
    for (i = 0; i < n; i++) {
        for (p = baslik[i].bag; p; p = sonraki) {
            sonraki = p->bag;         /* free'den once sakla */
            free(p);
        }
        baslik[i].bag = NULL;
        baslik[i].sayac = 0;
    }
}

Döngüde sonraki değişkeni zorunludur. free(p)'den sonra p->bag'e erişmek, geri verilmiş belleği okumak demektir ve tanımsız davranıştır. Bu yüzden bir sonraki öğenin adresi free'den önce saklanır. Sızıntı denetimi için testlerde malloc ve free, çağrıları sayan küçük sarmalayıcılarla değiştirildi. Notun topolojik sıra testlerinde 24 malloc ve 24 free sayıldı; bellek sızıntısı yoktur. Windows'ta zig derleyicisi adres denetleyicisini (-fsanitize=address) bağlayamadığı için bu sayaç yöntemi kullanıldı.

18.6.6TopolojikSira yordamı

Yordam öncülsüz düğümleri bir yığında biriktirir. Yığın için ayrı bir dizi ayrılmaz; sayacı sıfıra düşmüş bir düğümün sayac alanı artık boştadır ve yığının bağı olarak kullanılır.

void TopolojikSira(basoge baslik[], int n)
{
    int i, j, k, ust = -1;
    oge_gost p;
    for (i = 0; i < n; i++)      /* sayac 0: yigina */
        if (!baslik[i].sayac) {
            baslik[i].sayac = ust;  ust = i; }
    for (i = 0; i < n; i++) {
        if (ust == -1) { printf("dongu"); break; }
        j = ust;  ust = baslik[ust].sayac;
        printf("%d ", j);
        for (p = baslik[j].bag; p; p = p->bag) {
            k = p->dugum;
            if (--baslik[k].sayac == 0) {
                baslik[k].sayac = ust;  ust = k; }
        }
    }
}

• Satır 3. ust yığının tepesindeki düğümdür. −1 yığının boş olduğunu, yani dibini gösterir.
• Satır 5–7. İlk döngü sayacı 0 olan bütün düğümleri yığına koyar. baslik[i].sayac = ust ataması, düğümün altında kalan düğümü onun sayac alanına yazar. Sonra ust = i ile yeni düğüm tepeye çıkar. Bu, bağlı listeyle gerçeklenmiş bir yığının başa ekleme işleminin aynısıdır; bağ alanı olarak sayac kullanılır.
• Satır 8. İkinci döngü n tur döner; her turda bir düğüm yazılır.
• Satır 9. Düğüm yazılacakken yığın boşsa öncülsüz düğüm kalmamıştır. Henüz n düğüm yazılmadığı için kalan düğümler bir döngü oluşturur. Yordam “dongu” yazar ve durur.
• Satır 10–11. Yığından çıkarma: tepedeki düğüm j'ye alınır, altındaki düğüm (baslik[ust].sayac) yeni tepe olur. j yazılır.
• Satır 12–16. j'nin listesi gezilir. Her yakın ardıl k'nin öncül sayısı bir azaltılır; j'nin silinmesi, j'den çıkan kenarların silinmesi demektir. Sayaç 0'a düşerse k'nin öncülü kalmamıştır ve yığına konur.

Gömülü yığın tekniği ilk bakışta şaşırtıcıdır. Kodda “yığın” diye bir değişken yoktur; yalnız açıklama satırı ve ust değişkeni ne olduğunu ele verir. Açıklama satırları tam da bu yüzden önemlidir: kodu okuyan biri yığının nerede ve nasıl kullanıldığını onlardan anlar. Teknik, kümelerde kullanılan ebeveyn dizisine benzer. Orada her öğe ebeveyninin numarasını tutar ve bağlar bir dizinin içine gömülüdür. Burada da yığının bağları başlık dizisinin içine gömülüdür. Bir alanın iki ayrı amaçla kullanılabilmesinin nedeni, iki amacın zamanda çakışmamasıdır. Sayaç 0'a düşene kadar alan öncül sayısını tutar; düştükten sonra bir daha öncül sayısına gerek kalmaz.

--baslik[k].sayac == 0 ifadesi iki işi birleştirir: önce sayacı azaltır, sonra yeni değeri 0 ile karşılaştırır. Ders kitabındaki sayac--; if (!sayac) ikilisiyle aynı anlamdadır. Önek azaltma işleci burada önemlidir. Sonek kullanılsaydı (baslik[k].sayac-- == 0) karşılaştırma eski değerle yapılırdı. Son öncül silinirken eski değer 1 olduğu için hiçbir ardıl yığına girmez; örnekte çıktı 0 dongu ile kesilirdi.

18.6.7Kod izlemesi

TopolojikSira(baslik, 6) çağrısının izlemesi Tablo 18.13'dedir. Yığın sütununda tepe soldadır. Program aynı ağda 0 3 2 5 1 4 yazdı.

Tablonun iki ayrıntısına dikkat edilmelidir. Yığına giren düğümün sayacına ust'ün o anki değeri yazılır: v2 yığına girerken tepe v1 olduğu için sayac[2] = 1 olur, v3 girerken tepe v2 olduğu için sayac[3] = 2 olur. Ayrıca v0 yığından alındıktan sonra yığın boşalmış, ama hemen v0'ın ardılları ile dolmuştur. Döngü testi yalnız bir turun başında yapılır; tur içindeki geçici boşluk döngü sayılmaz.

Çıktı sırası şekildeki elle bulunan sırayla aynıdır. Elle yapılan seçimde v3'ün seçilmesi keyfiydi; kodda ise yığının son giren ilk çıkar kuralından gelir. v1, v2, v3 bu sırayla yığına girdiği için ilk çıkan v3 olur. Şekil 18.14 izlemenin iki anını gösterir.

18.6.8Döngü tespiti, analiz ve kuyruklu sürüm

Döngü, iki aktivitenin karşılıklı olarak birbirinin öncülü olmasıdır ve bir planlama hatasıdır: döngü varsa proje hiç bitmez. Yordamın döngüyü nasıl yakaladığı küçük bir ağla sınandı. Kenarlar <0,1>, <1,2>, <2,1>, <2,3>'tür; 1 ile 2 birbirinin öncülüdür. Yordam önce 0'ı yazar. 1'in sayacı 2'den 1'e iner ve sıfıra düşmez, çünkü 2'den gelen kenar hâlâ vardır. İkinci turun başında yığın boştur, ama yalnız bir düğüm yazılmıştır. Çıktı 0 dongu olur.

Yordamın maliyeti iki döngüden gelir. İlk döngü n başlığa bir kez bakar: O(n). İkinci döngü en çok n tur döner. Her turda bir düğüm yığından alınır ve onun listesi gezilir. j'nin listesinde d_j öğe vardır, yani iç for çıkış derecesi kadar döner. Her düğüm yığından en çok bir kez alındığı için iç döngünün toplam tur sayısı bütün çıkış derecelerinin toplamıdır. Yönlü çizgede bu toplam kenar sayısına eşittir. Sonuç

O(n + d₀ + d₁ + ⋯ + d_n−1) = O(n + e)

olur. Kenar sayısı çizgenin bağlanışına göre değişir. Seyrek bir ağda e n mertebesindedir ve süre doğrusaldır. Çok yoğun bir ağda e n² mertebesine çıkabilir. Kenarların her biri en az bir kez okunmak zorunda olduğu için hiçbir algoritma O(n + e)'den hızlı olamaz; bu yordam en iyisidir.

Öncülsüz düğümleri biriktirmek için yığın şart değildir; herhangi bir kap işe yarar. Kuyruk kullanılırsa algoritmaya Kahn'ın adı verilir (Arthur Kahn, 1962). Aşağıdaki sürüm kuyruğu basit bir diziyle gerçekler:

void KuyrukluSira(basoge baslik[], int n)
{
    int kuyruk[MAX_DUGUM], on = 0, arka = 0, i, j, k;
    oge_gost p;
    for (i = 0; i < n; i++)
        if (!baslik[i].sayac)
            kuyruk[arka++] = i;       /* kuyruga ekle */
    while (on < arka) {
        j = kuyruk[on++];             /* kuyruktan al */
        printf("%d ", j);
        for (p = baslik[j].bag; p; p = p->bag) {
            k = p->dugum;
            if (--baslik[k].sayac == 0)
                kuyruk[arka++] = k;
        }
    }
    if (arka < n)
        printf("dongu");
}

Bu sürümde döngü testi sonda yapılır: kuyruğa giren düğüm sayısı n'den azsa bazı düğümlerin sayacı hiç sıfıra düşmemiştir. Aynı altı düğümlü ağda kuyruklu sürüm 0 1 2 3 5 4 yazdı. v1, v2, v3 bu kez girdikleri sırayla çıkar. v3 işlenirken önce v5'in, sonra v4'ün sayacı sıfıra düşer, çünkü v3'ün listesinde v5 öndedir. İki çıktı farklıdır, ama ikisi de geçerli topolojik sıradır. Kapın türü yalnız eşit derecede geçerli sıralar arasında seçim yapar. Kuyruklu sürüm döngülü ağda da 0 dongu yazdı ve iki sürümün bütün testlerinde bellek sızıntısı görülmedi.

18.7Kenarda aktivite ağları ve kritik yol

18.7.1Kenarda aktivite ağı

AoV ağı işlerin sırasını gösterir, ama süreleri göstermez. Proje süresini hesaplamak için ikinci bir model kullanılır. Bu modelde aktiviteler kenarlara, aktivitelerin bitişini belirleyen anlar da düğümlere konur.

Olay, projenin tamamlanması için ulaşılması gereken bir ara aşamadır. Bitmesi gereken iş bir düğümle ifade edilir: “temel bitti”, “kaba inşaat bitti” gibi. Ağın tek bir başlangıç olayı (giren kenarı olmayan düğüm) ve tek bir bitiş olayı (çıkan kenarı olmayan düğüm) vardır. Başlangıç projenin başladığı, bitiş projenin bittiği andır.

Notun geri kalanında Şekil 18.15'deki ağ kullanılır. Ağda dokuz olay (v0–v8) ve on bir aktivite (a0–a10) vardır. v0 başlangıç, v8 bitiş olayıdır.

Ağ paralelliği doğrudan gösterir. a0, a1 ve a2 aynı anda, projenin ilk günü başlayabilir; üçünün de tek koşulu başlangıç olayıdır. a6 ve a7 v4 olayından çıkar. v4'e de a3 ve a4 girer. Öyleyse a6 ve a7, a3 ile a4'ün ikisi de bitmeden başlayamaz. Benzer biçimde v7'ye a7 ve a8 girer; a10 ancak bu ikisi bitince başlar. Aktivite listesi Tablo 18.14'dedir.

18.7.2AoV'den AoE'ye: yapay aktivite

Bir AoV ağı AoE ağına çevrilebilir, ama çeviri her zaman kenarları birebir eşlemekle olmaz. Şekil 18.16'deki AoV ağında 4 numaralı aktivite hem 2'yi hem 3'ü bekler. AoE ağında 2 ve 3 birer kenardır; 4'ün başlayabilmesi için iki kenarın da aynı olaya varması gerekir. İki kenar farklı olaylarda bitiyorsa bu olaylar, süresi 0 olan bir kenarla birleştirilir.

Yapay aktiviteye ana örnekte de gerek doğabilir. a6 ve a7'nin a3 ve a4'ün yanında a5 bittikten sonra başlaması istenseydi, a5'in bittiği v5 olayından a6 ile a7'nin başladığı v4 olayına bir kenar gerekirdi. Bu kenar bir iş değildir, yalnız bir bekleme kuralıdır: <v5, v4> yapay aktivitesi, süre 0.

Bir ağı en az sayıda yapay aktiviteyle çizmek kolay görünen ama zor bir problemdir. Bu problemin NP-zor olduğu gösterilmiştir; yani bilinen hiçbir algoritma onu büyük ağlarda verimli çözemez. Çizgelerin okunaklı çizimiyle uğraşan alan (graph drawing) için tez düzeyinde çalışmaların yapıldığı bir araştırma konusudur.

AoE ağları proje yönetiminin klasik yöntemlerinin temelidir. PERT (Program Evaluation and Review Technique) 1958'de ABD Donanması'nın Polaris füze programı için geliştirildi. CPM (Critical Path Method, kritik yol yöntemi) aynı yıllarda sanayide, bakım ve inşaat projelerinin planlanması için ortaya çıktı. RAMPS (Resource Allocation and Multi-Project Scheduling) ise kaynakların birden çok proje arasında paylaştırılmasını ele alır. Bugünkü proje yönetimi yazılımlarının çoğu bu yöntemlerin hesaplarını yapar.

18.7.3Kritik yol

Aktiviteler paralel yürüyebildiği için proje süresi bütün sürelerin toplamı değildir. Toplam 6 + 4 + 5 + 1 + 1 + 2 + 9 + 7 + 4 + 2 + 4 = 45 gündür, ama proje bundan çok daha kısa sürede biter. Bitiş olayı, kendisine giden her yolun aktiviteleri bitince gerçekleşir. Öyleyse proje süresi, başlangıçtan bitişe giden yolların en uzununun uzunluğudur.

Örnek ağda iki kritik yol vardır: v0-v1-v4-v6-v8 (6 + 1 + 9 + 2 = 18) ve v0-v1-v4-v7-v8 (6 + 1 + 7 + 4 = 18). Proje en erken 18 günde biter. Başka yollar daha kısadır; örneğin v0-v3-v5-v7-v8 yolu 5 + 2 + 4 + 4 = 15 gündür. Şekil 18.17 kritik yolları kalın çizgiyle gösterir.

“En kısa süre” ile “en uzun yol”un aynı şey olması ilk anda çelişkili görünür. Çelişki yoktur: proje, en uzun bekleme zincirinden daha kısa sürede bitemez, ama o zincir bitince başka bekleyen iş de kalmaz. Genel bir çizgede en uzun basit yolu bulmak NP-zordur. AoE ağı ise döngüsüzdür ve döngüsüz çizgede en uzun yol, topolojik sırada tek geçişle bulunur. Aşağıdaki hesaplar bunu yapar.

Kritik yol kavramı yöneticiye iki şey söyler. Kritik yoldaki bir aktivite bir gün gecikirse proje de bir gün gecikir. Bu işlerin ustalarına “sakın 4 günü 5'e sarkıtmayın; 3 günde biterse memnun olurum” denir. Kritik yolda olmayan aktivitelerde ise bir miktar gecikme projeyi etkilemez. Bu miktarın ne olduğunu bulmak için her aktivitenin en erken ve en geç başlama zamanları hesaplanır. Problem bir yöneylem araştırması problemidir.

18.8En erken ve en geç zamanlar

Bu hesaplar kâğıt üzerinde basit görünür. Ama elle işletilmesi dikkat ister: hangi değerin hangi anda kesinleştiği, hangi değerin henüz değişebileceği karıştırılırsa sonuç bozulur. Bu yüzden hesaplar aşağıda tablo hâlinde, adım adım verilmiştir.

18.8.1En erken başlama zamanı

Bir aktivite, kuyruğundaki olay gerçekleşir gerçekleşmez başlayabilir. a_i = <k, m> aktivitesinin en erken başlama zamanı bu yüzden k olayının en erken zamanına eşittir. Olayların en erken zamanları EnErkenBas dizisinde tutulur.

Örneğin a1'in kuyruğu v0'dır ve en erken 0. günde başlar. a5'in kuyruğu v3'tür; v3'e yalnız a2 girer, o da 5 gün sürer. a5 en erken 5. günde başlar. a8'in kuyruğu v5'tir; v5'e 5. günde başlayan 2 günlük a5 girer, a8 en erken 5 + 2 = 7. günde başlar.

Bir olaya birden çok aktivite giriyorsa durum değişir. v4'e a3 ve a4 girer. a3, 6. günde başlar ve 6 + 1 = 7. günde biter. a4, 4. günde başlar ve 4 + 1 = 5. günde biter. v4 olayı ikisinin de bitmesini bekler; bu yüzden en geç biteni, yani 7. günü bekler. Kural genel olarak

EnErkenBas[m] = max { EnErkenBas[k] + süre(<k, m>) : k ∈ P(m) }

biçiminde yazılır. P(m), m'nin yakın öncüllerinin kümesidir. Başlangıç olayının değeri 0'dır. 0, projenin başladığı günü gösterir; proje 8 Mayıs'ta başlıyorsa 0. gün 8 Mayıs'tır. Başlangıca 10 verilseydi bütün değerler 10 gün kayardı.

Formülün bir koşulu vardır: EnErkenBas[m] hesaplanırken öncüllerin değerleri kesinleşmiş olmalıdır. Bu, hesabın topolojik sırada yapılması demektir. Dolayısıyla TopolojikSira yordamı küçük bir eklemeyle bu hesabı da yapar. Liste öğesine aktivitenin süresini tutan bir sure alanı eklenir:

typedef struct oge *oge_gost;
typedef struct oge {
    int dugum;
    int sure;            /* aktivitenin suresi */
    oge_gost bag;
} oge;
typedef struct {
    int sayac;
    oge_gost bag;
} basoge;
int EnErkenBas[MAX_DUGUM], EnGecBas[MAX_DUGUM];

Bu yapıyla öğe boyutu değişmez: dugum ile sure 4'er bayt yer kaplar ve önceki dolgunun yerini doldurur; sizeof(oge) yine 16'dır. Kenar ekleme yordamı da yalnız süreyi yazacak biçimde genişletilir:

int kenar_ekle(basoge baslik[], int i, int j, int sure)
{
    oge_gost *son = &baslik[i].bag;
    oge_gost yeni = malloc(sizeof(oge));
    if (yeni == NULL)
        return 0;
    yeni->dugum = j;
    yeni->sure = sure;
    yeni->bag = NULL;
    while (*son != NULL)
        son = &(*son)->bag;
    *son = yeni;
    baslik[j].sayac++;
    return 1;
}

TopolojikSira'nın iç döngüsünde, sayaç azaltılmadan önce şu iki satır çalıştırılır:

/* TopolojikSira icinde sayac azaltilmadan once: */
if (EnErkenBas[k] < EnErkenBas[j] + p->sure)
    EnErkenBas[k] = EnErkenBas[j] + p->sure;

j o an yığından alınmış ve yazılmış düğümdür, k de onun bir yakın ardılıdır. j üzerinden k'ye gelen yol daha uzun bir bekleme gerektiriyorsa k'nin değeri büyütülür. Bu, Dijkstra'daki gevşetmenin aynısıdır; tek fark < karşılaştırmasının yönü ve aranan değerin en büyük olmasıdır. EnErkenBas başta 0'larla doldurulur. Sürelerin hepsi negatif olmadığı için 0, her olay için geçerli bir alt sınırdır. Eklemelerle oluşan tam yordam şöyledir:

void EnErkenHesapla(basoge baslik[], int n)
{
    int i, j, k, ust = -1;
    oge_gost p;
    for (i = 0; i < n; i++)
        EnErkenBas[i] = 0;
    for (i = 0; i < n; i++)
        if (!baslik[i].sayac) {
            baslik[i].sayac = ust;  ust = i; }
    for (i = 0; i < n; i++) {
        if (ust == -1) { printf("dongu"); break; }
        j = ust;  ust = baslik[ust].sayac;   /* yigindan al */
        printf("%d ", j);
        for (p = baslik[j].bag; p; p = p->bag) {
            k = p->dugum;
            if (EnErkenBas[k] < EnErkenBas[j] + p->sure)
                EnErkenBas[k] = EnErkenBas[j] + p->sure;
            if (--baslik[k].sayac == 0) {
                baslik[k].sayac = ust;  ust = k;  /* yigina */
            }
        }
    }
}

• Satır 5–9. Diziye başlangıç değeri verilir ve öncülsüz düğümler yığına konur. Bu kısım TopolojikSira'nın ilk döngüsüyle aynıdır.
• Satır 12–13. Yığından bir olay alınır. Bu andan sonra EnErkenBas[j] bir daha değişmez, çünkü j'nin bütün öncülleri daha önce işlenmiştir.
• Satır 16–17. j'den çıkan her aktivite için ardılın değeri gerekirse büyütülür.
• Satır 18–20. Ardılın son öncülü de işlendiyse ardıl yığına girer. Satırların sırası önemlidir: değer güncellemesi sayaç azaltmadan önce yapılmalıdır. Aksi hâlde düğüm yığına girip başka bir turda yazıldığında, son kenardan gelen katkı henüz eklenmemiş olabilir.

18.8.2İleri çözümlemenin izlenmesi

Hesap başlangıçtan bitişe doğru ilerlediği için ileri çözümleme (forward stage) diye adlandırılır. Ağ listeleri Tablo 18.14'deki sırayla kurulmuştur: v0'ın listesi v1, v2, v3; v4'ün listesi v6, v7'dir. Tablo 18.15 her olay yazıldıktan sonraki durumu verir. Satırlar programın çıktısıyla karşılaştırılmıştır.

Tablonun en önemli dersi, hangi değerlerin kalıcı olduğudur. Ancak çıktıya yazılmış olayların en erken zamanları kesinleşmiştir; o andan sonra bir daha değişmez. Yazılmamış bir olayın değeri yalnız bir alt sınırdır. v5 işlenince EnErkenBas[7] 11 yapıldı. Ama v7'nin bir öncülü daha vardı: v4. v4 işlenince 7 + 7 = 14 bulundu ve değer 14'e çıktı. Benzer biçimde v4'ün değeri önce v2 üzerinden 5, sonra v1 üzerinden 7 oldu. Değişen hücreler tabloda vurgulanmıştır.

Son satırda EnErkenBas[8] = 18'dir: proje en erken 18 günde biter. Bu, kritik yolun uzunluğudur. v8'e iki aktivite girer: a10 (14 + 4 = 18) ve a9 (16 + 2 = 18). İkisi de 18 verir; bu yüzden iki kritik yol vardır. Şekil 18.19 ileri çözümlemenin iki anını gösterir.

18.8.3En geç başlama zamanı

En erken zamanlar “en çabuk ne zaman başlanabilir?” sorusunu cevaplar. Yöneticinin ikinci sorusu “projeyi geciktirmeden en geç ne zaman başlanmalı?” sorusudur. Bu kez hesap bitişten başlar ve geriye doğru yürür. Bitiş olayının en geç zamanı en erken zamanına eşit alınır: proje 18 günde bitebiliyorsa 18. günde bitmelidir. Öyleyse EnGecBas[8] = EnErkenBas[8] = 18'dir.

a_i = <k, m> aktivitesi en geç EnGecBas[m] − süre anında başlamalıdır; yoksa m olayına geç kalınır. a10 (v7 → v8, 4 gün) en geç 18 − 4 = 14. günde başlamalıdır. a9 (v6 → v8, 2 gün) en geç 18 − 2 = 16. günde başlamalıdır. Bu yüzden EnGecBas[7] = 14, EnGecBas[6] = 16'dır.

Bir olaydan birden çok aktivite çıkıyorsa olay, en erken başlaması gereken aktiviteye yetişmelidir. Bu yüzden en küçük değer alınır:

EnGecBas[k] = min { EnGecBas[m] − süre(<k, m>) : m ∈ S(k) }

S(k), k'nin yakın ardıllarıdır. v0 bunun iyi bir örneğidir. v0'dan üç aktivite çıkar. a0 için 6 − 6 = 0, a1 için 6 − 4 = 2, a2 için 8 − 5 = 3 bulunur. En küçüğü 0'dır ve EnGecBas[0] = 0 olur. Büyüğü, yani 3 seçilseydi a0 üç gün geç başlar, v1 9. güne, v4 10. güne, v6 19. güne kayar ve proje 21 güne uzardı. İleri çözümlemede en büyük, geri çözümlemede en küçük değer alınır; ikisini karıştırmak bu tür hesapların en sık hatasıdır.

Hesap için her olayın ardıllarına ihtiyaç vardır ve ardılların değerleri önce kesinleşmelidir. En kolay yol bütün okları ters çevirmektir. Ters çizgede ardıllar öncüle dönüşür ve aynı topolojik sıra yordamı kullanılabilir. Ters çizge, komşuluk listesinin tersi kurularak elde edilir:

int ters_kur(basoge baslik[], basoge ters[], int n)
{
    int i;
    oge_gost p;
    for (i = 0; i < n; i++) {
        ters[i].sayac = 0;
        ters[i].bag = NULL;
    }
    for (i = 0; i < n; i++)
        for (p = baslik[i].bag; p; p = p->bag)      /* <i, p->dugum> */
            if (!kenar_ekle(ters, p->dugum, i, p->sure))
                return 0;
    return 1;
}

Yordam her <i, j> kenarı için j'nin ters listesine i'yi, aynı süreyle ekler. kenar_ekle ters listedeki sayac alanını da artırır; bu sayaç ters çizgedeki giriş derecesi, yani asıl çizgedeki çıkış derecesidir. Yordam her kenara bir kez dokunur ve O(n + e)'de biter; liste sonuna eklemenin ek maliyeti de toplamda kenar sayısıyla sınırlıdır. Ters listeler, ileri çözümleme sayac alanlarını bozmadan önce ya da ondan bağımsız olarak, yalnız bag ve sure alanlarından kurulur.

Geri çözümlemenin döngüsü ileri çözümlemenin aynısıdır; yalnız gevşetme satırı değişir:

if (EnGecBas[k] > EnGecBas[j] - p->sure)
    EnGecBas[k] = EnGecBas[j] - p->sure;

Burada j ters listede yazılan olay, k de onun asıl çizgedeki bir öncülüdür. EnGecBas başta proje süresiyle, yani 18 ile doldurulur ve değerler yalnız küçülür. Tam yordam şöyledir:

void EnGecHesapla(basoge baslik[], int n, int proje)
{
    int i, j, k, ust = -1;
    oge_gost p;
    for (i = 0; i < n; i++)
        EnGecBas[i] = proje;
    for (i = 0; i < n; i++)
        if (!baslik[i].sayac) {
            baslik[i].sayac = ust;  ust = i; }
    for (i = 0; i < n; i++) {
        if (ust == -1) { printf("dongu"); break; }
        j = ust;  ust = baslik[ust].sayac;   /* ters liste */
        printf("%d ", j);
        for (p = baslik[j].bag; p; p = p->bag) {
            k = p->dugum;                        /* k: oncul */
            if (EnGecBas[k] > EnGecBas[j] - p->sure)
                EnGecBas[k] = EnGecBas[j] - p->sure;
            if (--baslik[k].sayac == 0) {
                baslik[k].sayac = ust;  ust = k;
            }
        }
    }
}

18.8.4Geri çözümlemenin izlenmesi

Ters çizgede öncülsüz tek düğüm v8'dir; hesap ondan başlar. Ters listeler asıl kenarlar i sırasıyla taranarak kurulduğu için v8'in ters listesi v6, v7; v7'ninki v4, v5; v4'ünki v1, v2 sırasındadır. Tablo 18.16 izlemeyi verir; değerler programla doğrulandı.

EnGecBas[0] üç kez değişmiştir: v3'ten 8 − 5 = 3, v2'den 6 − 4 = 2, v1'den 6 − 6 = 0. Her güncelleme daha sıkı bir zorunluluk getirir; sonuncusu, v0'ın gecikme payı olmadığını söyler. v6 işlenirken v4 için 16 − 9 = 7 bulunur; bu, v7 üzerinden bulunan değerle (14 − 7 = 7) aynıdır ve dizi değişmez. v4'ün iki ardılı da kritiktir.

Geri çözümlemenin sırası (8 7 5 3 6 4 2 1 0) ters çizgenin bir topolojik sırasıdır. İleri çözümlemenin sırasını (0 3 5 2 1 4 7 6 8) tersten okumak da aynı işi görür: bir topolojik sıranın tersi, ters çizgenin topolojik sırasıdır. Bir betik bu ikinci sırayla da aynı EnGecBas değerlerini buldu. Önemli olan, bir olay işlenirken bütün ardıllarının kesinleşmiş olmasıdır; rastgele bir sırada bu garanti yoktur.

18.8.5Bolluk ve kritik aktiviteler

Artık her aktivite için iki zaman bilinir. a_i = <k, m> için en erken başlama zamanı EnErkenBas[k], en geç başlama zamanı EnGecBas[m] − süre'dir. İkisi arasındaki fark, aktivitenin projeyi geciktirmeden kaydırılabileceği gün sayısıdır.

Kritik bir aktivite en erken zamanında başlamak zorundadır; bir günlük gecikmesi bütün projeyi bir gün geciktirir. Örnek ağın bütün aktiviteleri Tablo 18.17'dedir. Tablo programın çıktısıyla aynıdır.

Bir örnekle: a4'ün en erken başlama zamanı 4, en geç başlama zamanı 7 − 1 = 6'dır. a4 iki gün gecikebilir ve proje yine 18 günde biter. Kritik aktiviteler a0, a3, a6, a7, a9 ve a10'dur. Bunlar v0'dan v8'e iki yol oluşturur ve bu yollar kritik yollardır (Şekil 18.21). Proje yönetimi yazılımları bolluk dağılımını çubuk grafiklerle gösterir; yönetici kaynakları bolluğu olan işlerden kritik işlere aktarabilir.

Tablodaki bolluk toplam bolluktur (total float). Toplam bolluk aynı yoldaki aktiviteler arasında paylaşılır. a2, a5 ve a8 aynı yol üzerindedir ve üçünün de bolluğu 3'tür. Ama bu, üçünün de üçer gün gecikebileceği anlamına gelmez. a2 üç gün gecikirse a5 ve a8'in payı tükenir; ikisi de kritik olur. Bolluk yol boyunca bir kez harcanabilir.

Bunun için ikinci bir ölçü kullanılır. Serbest bolluk (free float), bir aktivitenin ardıllarının en erken zamanını geciktirmeden kullanabileceği bolluktur: EnErkenBas[m] − EnErkenBas[k] − süre. a2 için 5 − 0 − 5 = 0, a5 için 7 − 5 − 2 = 0, a8 için 14 − 7 − 4 = 3'tür. Yani a2 ve a5'in bollukları kendilerine ait değildir, yoldaki a8'den gelir. a8 ise üç gününü kimseyi etkilemeden kullanabilir. a4'ün serbest bolluğu da 7 − 4 − 1 = 2'dir.

18.8.6Kritik yolu programın bulması

İki dizi hesaplandıktan sonra her aktivitenin bolluğunu yazdırmak tek bir çift döngü ister. Asıl çizgenin listeleri gezilir; her öğe bir aktivitedir.

void Bolluklar(basoge baslik[], int n)
{
    int i;
    oge_gost p;
    /* EnErkenBas[] ve EnGecBas[] hesaplandiktan sonra */
    for (i = 0; i < n; i++)
        for (p = baslik[i].bag; p; p = p->bag) {
            int erken = EnErkenBas[i];
            int gec   = EnGecBas[p->dugum] - p->sure;
            printf("<%d,%d> erken=%d gec=%d bolluk=%d%s\n",
                   i, p->dugum, erken, gec, gec - erken,
                   gec == erken ? " KRITIK" : "");
        }
}

Çıktının ilk dört satırı şöyledir:

<0,1> erken=0 gec=0 bolluk=0 KRITIK
<0,2> erken=0 gec=2 bolluk=2
<0,3> erken=0 gec=3 bolluk=3
<1,4> erken=6 gec=6 bolluk=0 KRITIK

Kalan satırlar Tablo 18.17 ile birebir aynıdır. Yordam yalnız bolluğu 0 olan aktiviteleri tutarak kritik yolu da verir: kritik aktiviteler v0'dan v8'e uzanan bir ya da birkaç yol oluşturur. printf'teki ?: işleci koşullu bir dize seçer: bolluk 0 ise " KRITIK", değilse boş dize yazılır.

Bütün hesabın maliyeti parçaların toplamıdır. İleri çözümleme O(n + e), ters listenin kurulması O(n + e), geri çözümleme O(n + e), bolluk taraması da O(n + e)'dir. Toplam O(n + e)'dir; proje ne kadar büyük olursa olsun hesap doğrusal sürede biter. Notun testlerinde ileri ve ters listeler için 22 malloc ve 22 free sayıldı; sızıntı yoktur.

18.8.7Uygulama: bir sınav sorusu

Bu hesaplar sınavlarda sık sorulur ve kâğıt üzerinde adım adım işletilmeleri beklenir. Anlaşıldığı sanılan ama elle işletilirken çoğu zaman yanlış yapılan bir konudur. Aşağıdaki örnek bütün adımlarıyla çözülür.

İleri çözümleme. Sayaçlar v0…v5 için 0, 1, 1, 2, 1, 2'dir. Yalnız v0 yığındadır. v0 yazılınca v1 ve v2'nin değerleri 3 ve 2 olur; ikisi de yığına girer ve tepe v2'dir. v2 yazılınca v3 için 2 + 2 = 4, v4 için 2 + 3 = 5 bulunur. v3'ün sayacı 1'e iner; v4 yığına girer. v4 yazılınca v5 için 5 + 5 = 10 bulunur. Sonra v1 yazılır ve v3'ün değeri 3 + 4 = 7'ye çıkar; v3 yığına girer. v3 yazılınca v5 için 7 + 2 = 9 bulunur, ama 9 < 10 olduğu için değer değişmez. En son v5 yazılır. Topolojik sıra 0 2 4 1 3 5, sonuç EnErkenBas = [0, 3, 2, 7, 5, 10]'dur. Proje en erken 10 günde biter.

Geri çözümleme. EnGecBas 10'larla başlar. Ters çizgede v5'ten başlanır: v3 için 10 − 2 = 8, v4 için 10 − 5 = 5 bulunur. v4 işlenince v2 için 5 − 3 = 2 bulunur. v3 işlenince v1 için 8 − 4 = 4 bulunur; v2 için 8 − 2 = 6, ama 2 daha küçük olduğu için değer 2 kalır. v2 işlenince v0 için 2 − 2 = 0, v1 işlenince 4 − 3 = 1 bulunur ve 0 korunur. Sıra 5 4 3 2 1 0, sonuç EnGecBas = [0, 4, 2, 8, 5, 10]'dur.

Kritik aktiviteler a1, a4 ve a6'dır; kritik yol v0-v2-v4-v5'tir ve uzunluğu 2 + 3 + 5 = 10'dur. Bütün değerler aynı yordamlarla programda da hesaplandı ve elle bulunanlarla örtüştü. a3'ün bolluğu (4) en büyüktür: v2 2. günde gerçekleşir, v3 ise 8. güne kadar beklenebilir; 2 günlük a3'ün önünde 4 günlük bir boşluk vardır.

18.9Karmaşıklık özeti

Tablo 18.19 notta ele alınan bütün algoritmaları, kullandıkları veri yapılarını ve sürelerini bir arada verir. n düğüm, e kenar sayısıdır.

Ek bellek sütunu, girdinin kendisi dışında ayrılan yeri gösterir. Topolojik sıranın ek belleği sabittir, çünkü yığın başlık dizisinin içine gömülüdür. Zaman hesaplarında ise ters liste ve iki dizi gerekir. Tablodaki bütün sınırlar en kötü durum içindir. Temel Dijkstra ve Floyd-Warshall için sınır aynı zamanda en iyi durumdur: bu yordamlar girdiye bakmadan her zaman aynı sayıda tur döner.

18.10Sık yapılan hatalar

1. Negatif kenarlı çizgede Dijkstra kullanmak. Algoritma hata vermez, sessizce yanlış sonuç üretir. Negatif ağırlık varsa Bellman-Ford, döngüsüz çizgede ise topolojik sırada gevşetme kullanılmalıdır.
2. Sonsuz için INT_MAX seçmek. uzaklik[u] + maliyet[u][w] toplamı taşar; işaretli tamsayı taşması tanımsız davranıştır ve sonuç çoğu zaman negatif bir sayıdır. Gerçek yollardan büyük ama iki katı int'e sığan bir sabit seçilmelidir.
3. En erken zamanda en küçüğü, en geç zamanda en büyüğü almak. Doğrusu tersidir: en erken zaman giren aktivitelerin en büyüğünü bekler, en geç zaman çıkan aktivitelerin en küçüğüne yetişir.
4. En geç zamanı ardıllar kesinleşmeden hesaplamak. Geri çözümleme ters çizgenin topolojik sırasında ya da ileri sıranın tersinde yapılmalıdır. Rastgele bir sırada, ardılı henüz işlenmemiş bir olayın değeri kesin sanılır.
5. Topolojik sıraya rastgele bir düğümden başlamak. Öncülleri işlenmemiş bir düğümün en erken zamanı yalnız bir alt sınırdır. Bir değer, ancak düğüm yığından alınıp yazıldığında kesinleşir.
6. Yolu ileri doğru kurmaya çalışmak. Kaynaktan çıkarken hangi kenarın seçileceği belli değildir. Öncüller dizisi hedeften geriye okunur, özyineleme ya da yığınla ters çevrilerek yazılır.
7. Erişilemeyen düğüm için yol yazdırmak. uzaklik[h] >= SONSUZ ise onceki[h] anlamsızdır; önce bu koşul denetlenmelidir.
8. TopolojikSira'yı aynı yapı üzerinde ikinci kez çağırmak. Sayaç alanları yığın bağlarına dönüşmüştür; sayaçlar yeniden hesaplanmalıdır.

18.11Alıştırmalar ve çözümleri

18.11.1Başka bir kaynak

Soru. Altı düğümlü örnek çizgede kaynak 2 olsaydı EnKisaYolBul hangi uzaklıkları bulurdu?

Çözüm. Başlangıçta 2'nin satırı kopyalanır: 0 için 20, 3 için 15, ötekiler 1000. İlk turda 3 seçilir (15); 3 üzerinden 1'e 15 + 20 = 35, 4'e 15 + 35 = 50 bulunur. İkinci turda 0 seçilir (20); 0 üzerinden hiçbir değer kısalmaz (1'e 70, 4'e 65). Üçüncü turda 1 seçilir (35); 1 üzerinden 4'e 35 + 10 = 45 bulunur ve 50'nin yerini alır. Dördüncü turda 4 seçilir. Sonuç: d(2→0) = 20, d(2→3) = 15, d(2→1) = 35 (3 üzerinden), d(2→4) = 45 (3 ve 1 üzerinden); 5'e yol yoktur.

18.11.2Dış döngünün tur sayısı

Soru. EnKisaYolBul'un dış döngüsü neden n − 2 tur döner? n − 1 tur dönse ne olurdu?

Çözüm. Kaynak başta kesindir; n − 2 tur sonunda n − 1 düğüm işaretlenmiş olur. Kalan tek düğüm için öteki bütün düğümler S'dedir ve uzaklik değeri tanım gereği en kısa uzunluktur. Bir tur daha dönülseydi bu düğüm seçilip işaretlenirdi, ama gevşetilecek işaretsiz düğüm kalmadığı için hiçbir değer değişmezdi. Fazladan tur zararsızdır, ama gereksizdir.

18.11.3Kenar ağırlığı değişirse

Soru. Yedi düğümlü adım adım örnekte v3 → v6 kenarı 2 yerine 15 olsaydı S'ye katılma sırası ne olurdu?

Çözüm. İlk üç adım değişmez: v1 (10), v2 (20), sonra v3 ve v4 (ikisi de 30; eşitlikte küçük indis önce: v3, v4). v3 katılınca v6'nın değeri bu kez 30 + 15 = 45 olur. v4 katılınca v5 40'a iner. 40 < 45 olduğu için v5, v6'dan önce seçilir. v5'ten v6'ya kenar yoktur; v6 45'te kalır. Sıra v1, v2, v3, v4, v5, v6 olur. Program da aynı sırayı ve uzaklik = 0 10 20 30 30 40 45 sonucunu verdi.

18.11.4Yığın yerine kuyruk

Soru. Topolojik sıra yordamında yığın yerine kuyruk kullanılsaydı v0…v5 örneğinde çıktı ne olurdu?

Çözüm. 0 1 2 3 5 4. v0 alınınca v1, v2, v3 bu sırayla kuyruğa girer ve aynı sırayla çıkar. v1 alınınca v4'ün sayacı 2'ye, v2 alınınca 1'e iner; v5'in sayacı 1'e iner. v3 alınınca önce v5'in, sonra v4'ün sayacı 0'a düşer, çünkü v3'ün listesinde v5 v4'ten öncedir. Kuyruklu sürüm programda da bu çıktıyı verdi.

18.11.5Bir aktivitenin süresi uzarsa

Soru. AoE örneğinde a8'in süresi 4 yerine 8 olsaydı proje süresi ve kritik yol ne olurdu?

Çözüm. v7'ye v5 üzerinden 7 + 8 = 15'te varılır; bu, v4 üzerinden gelen 14'ten büyüktür. EnErkenBas[7] = 15, v8 için 15 + 4 = 19 olur ve proje 19 güne uzar. Kritik yol artık v0-v3-v5-v7-v8'dir (5 + 2 + 8 + 4 = 19). Eski kritik yollar 18 gün sürdüğü için kritik olmaktan çıkar; program a0, a3, a6, a7 ve a9 için 1 günlük bolluk buldu. a8'in bolluğu 3 gündü; bolluğundan fazla (4 gün) uzayan kritik olmayan bir aktivite kritik yolu değiştirir. Bu yüzden hesap her değişiklikte yeniden yapılmalıdır.

18.11.6Floyd-Warshall'da geç gelen değişiklik

Soru. Floyd-Warshall örneğinde A[1][0] neden k = 2 turunda değişti?

Çözüm. 1'den 0'a en kısa yol 1 → 2 → 0'dır: 2 + 3 = 5, doğrudan kenar ise 6'dır. Bu yol 2'yi ara düğüm olarak kullanır. A^k yalnız 0…k arasındaki ara düğümlere izin verdiği için 2'nin kullanılabilmesi ancak k = 2 turunda mümkündür.

18.12Özet

• En kısa yol problemi ağırlıklı yönlü çizgede kurulur; yolun uzunluğu kenar maliyetlerinin toplamıdır. Tek kaynaktan tek hedefe, tek kaynaktan bütün hedeflere ve tüm çiftler arası sürümleri vardır.
• Kaba kuvvet bütün basit yolları dener. Tam çizgede yol sayısı 1 + (n − 2) + ⋯ + (n − 2)!'dir; tek bir hedef için bile O(nⁿ) mertebesinde iş gerekir.
• Dijkstra açgözlüdür: S dışında en küçük uzaklıklı düğümü kesinleştirir, sonra onun üzerinden gevşetme yapar. w ≥ 0 ister. Matrisle O(n²), min-heap ve komşuluk listesiyle O((n + e) log n)'dir.
• Sonsuz için taşma yaratmayan bir sabit seçilir. minimumBul −1'i yalnız işaretsiz düğüm kalmadığında döndürür.
• Öncüller dizisi tek başına yeter: en kısa yollar bir ağaç oluşturur. Yol hedeften geriye okunur, özyineleme ya da yığınla doğru sırada yazılır.
• Negatif kenarda Dijkstra yanılır. Bellman-Ford bütün kenarları n − 1 tur gevşetir, n. turda negatif döngüyü yakalar: O(n · e). Floyd-Warshall ara düğümleri birer birer serbest bırakarak tüm çiftleri O(n³)'te bulur.
• Düğümde aktivite ağı öncül ilişkisini gösterir ve döngüsüz olmalıdır. Topolojik sıra öncülsüz düğümleri birer birer silerek bulunur. Sayaçlı başlıklar ve gömülü yığınla O(n + e)'dir; aynı yordam döngüyü de yakalar.
• Kenarda aktivite ağında kenarlar aktiviteler, düğümler olaylardır. Proje süresi başlangıçtan bitişe en uzun yoldur: kritik yol.
• En erken zamanlar topolojik sırada en büyük değerle (ileri çözümleme), en geç zamanlar ters çizgede en küçük değerle (geri çözümleme) bulunur. Bolluk, en geç ile en erken başlama zamanının farkıdır. Bolluğu 0 olan aktiviteler kritik yolu oluşturur.

18.13Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• ağırlıklı çizge weighted graph
• en kısa yol shortest path
• kaba kuvvet brute force
• tam çizge complete graph
• açgözlü yöntem greedy method
• Dijkstra algoritması Dijkstra's algorithm
• gevşetme relaxation
• öncül predecessor
• ardıl successor
• öncelikli kuyruk priority queue
• heap heap
• Fibonacci heap Fibonacci heap
• negatif döngü negative cycle
• Bellman-Ford algoritması Bellman-Ford algorithm
• tüm çiftler arası en kısa yollar all-pairs shortest paths
• Floyd-Warshall algoritması Floyd-Warshall algorithm
• aktivite ağı activity network
• düğümde aktivite ağı (AoV) activity on vertex network
• kenarda aktivite ağı (AoE) activity on edge network
• yönlü döngüsüz çizge directed acyclic graph
• topolojik sıra topological order
• giriş derecesi in-degree
• çıkış derecesi out-degree
• yapay aktivite dummy activity
• kritik yol critical path
• bolluk slack

18.14Kendini Dene

1. Altı düğümlü örnek çizgede kaynak 5 alınırsa Dijkstra düğümleri hangi sırayla kesinleştirir ve uzaklıklar ne olur?

   Cevap

   5'ten tek kenar 3'e gider (3). Sıra 3 (3), 1 (23), 4 (33), 2 (38)'dir; 0 son kalan düğümdür ve değeri 2 üzerinden 58'dir. Uzaklıklar 0'dan 4'e sırasıyla 58, 23, 38, 3, 33'tür. Floyd-Warshall'ın 5. satırı da aynı değerleri verir.

2. EnKisaYolBul bittiğinde onceki = {0, 3, 0, 2, 0, 0}'dır. yol_yaz(onceki, 0, 3) kaç özyinelemeli çağrı yapar ve ne yazar?

   Cevap

   İlk çağrı dahil üç çağrı yapılır: h = 3, 2, 0. Çıktı 0 -> 2 -> 3'tür; maliyet 10 + 15 = 25.

3. Sonsuz olarak INT_MAX kullanan bir Dijkstra kodunda, erişilemeyen bir u seçilip uzaklik[u] + maliyet[u][w] hesaplanırsa ne olabilir?

   Cevap

   Toplam int'e sığmaz; işaretli taşma tanımsız davranıştır. Pratikte sonuç çoğu zaman negatif bir sayıya döner, uzaklik[w]'den küçük görünür ve var olmayan bir “kısa yol” yazılır.

4. Bellman-Ford dört düğümlü negatif örnekte kaç tur döner ve toplam kaç gevşetme denemesi yapar? Hangi turdan sonra hiçbir değer değişmez?

   Cevap

   n − 1 = 3 tur ve her turda 4 kenar: 12 deneme; n. turda da 4 kenar denetlenir. Son değişiklik ikinci turda olur (d[3] 6'dan 4'e); üçüncü tur hiçbir şey değiştirmez.

5. Floyd-Warshall kodunda döngülerin sırası i, j, k (en içte k) olarak değiştirilirse ne olur?

   Cevap

   Algoritma doğruluğunu yitirir. A[i][j] hesaplanırken kullanılan A[i][k] ve A[k][j] değerleri henüz bütün ara düğümler hesaba katılmadan alınmış olabilir. A^k'nın tanımı, k en dışta olduğunda sağlanır.

6. v0…v5 topolojik sıra örneğinde v3'ün listesi v5, v4 yerine v4, v5 sırasında olsaydı TopolojikSira ne yazardı?

   Cevap

   0 3 2 5 1 4; çıktı değişmez. v3 işlenirken v4'ün sayacı 2'ye, v5'inki 1'e iner; ikisi de sıfıra düşmediği için yığına giriş sırası etkilenmez. Liste sırası ancak sayaçları aynı anda sıfıra düşen düğümlerin sırasını değiştirir.

7. AoE örneğinde a6'nın süresi 9 yerine 10 olsaydı proje süresi ve kritik yol ne olurdu?

   Cevap

   v6 en erken 7 + 10 = 17'de, v8 17 + 2 = 19'da gerçekleşir; proje 19 gün sürer. Kritik yol yalnız v0-v1-v4-v6-v8'dir. a7 ve a10'un bolluğu 1 olur, çünkü v7 üzerinden giden yol 18 gündür.

8. AoE örneğinde a4'ün toplam bolluğu ve serbest bolluğu nedir? İkisinin eşit olması ne anlama gelir?

   Cevap

   Toplam bolluk 6 − 4 = 2, serbest bolluk EnErkenBas[4] − EnErkenBas[2] − 1 = 7 − 4 − 1 = 2'dir. Eşit olmaları, a4'ün iki günlük payını hiçbir ardılın en erken zamanını etkilemeden kullanabileceğini gösterir; pay başka bir aktiviteyle paylaşılmaz.

18.15İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, kesim 6.4 ve 6.5. Bu notun örnek çizgeleri, Dijkstra'nın dizi sürümü, gömülü yığınlı topolojik sıra ve en erken/en geç zaman hesapları oradaki biçimiyle izlenmiştir.
• T. H. Cormen ve ark., Introduction to Algorithms, 4. baskı, bölüm 20.4, 22 ve 23. Topolojik sıranın DFS ile bulunması, Dijkstra ve Bellman-Ford'un doğruluk kanıtları ve Floyd-Warshall'ın dinamik programlama çözümlemesi ayrıntılı verilir.
• R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3. baskı, bölüm 21. En kısa yol algoritmaları C koduyla ve büyük çizgeler üzerindeki deneylerle birlikte ele alınır.

18.16Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. bs., Silicon Press, 2008. §6.4 Shortest Paths and Transitive Closure, §6.5 Activity Networks.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. bs., MIT Press, 2022. Bölüm 20.4 (Topological Sort), 22 (Single-Source Shortest Paths), 23 (All-Pairs Shortest Paths).
3. R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3. bs., Addison-Wesley, 2002. Bölüm 21 (Shortest Paths).

İlgili sayfalar: Bölüm 18 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.