En Kısa Yollar Ağacı

Minimum kapsama ağacı çözümüyle asfaltlanacak yol uzunluğunu 98,5 kmye indiren kaymakamımız ilçe sakinlerini favori piknik yeri olan 3 nolu köye olabilecek en uzak yoldan gitmeye zorlayacağı için şikayetlere maruz kalmış. Prim ya da Kruskal'ı boşvermiş, artık ilçe merkezini her bir köye olabilecek en kısa yoldan bağlayacak bir çözüm arıyor.

Djikstra Algoritması

Bu kez problem ağ üzerinde belli bir nodu merkez alan "en kısa yollar" (shortest paths) problemidir. Bunun bir çözüm yolu Djikstra algoritmasıdır. Bu algoritma aslında seçilen iki nod arasındaki en kısa yolu bulmak içindir, ama bir parça uğraşarak, belli bir noddan diğer her noda erişen en kısa yolu bulacak şekilde uygulayabiliriz.

Hatırlarsanız, genişlik öncelikli kapsama ağacı merkez seçtiğimiz nodu diğer her noda olabilecek en az kademeyle bağlıyordu. İlçe merkezini her köye olabilecek en az durakla bağlayan o yöntem kaymakamımız için en mantıklı yöntem olacaktır.

O yöntemdeki gibi ilçe merkezine doğrudan bağlı köylerin yolları muhtemel güzergahlar olarak listelenir, ama bu kez her köyün ilçe merkezinden uzaklığı da belirlenip not edilir. Aşağıdaki resimde köy uzaklıklarını nod kutularının köşelerindeki etiketlere yazdırdık:

Bundan sonra doğrudan ulaşılan bu köylerden komşu köylere giden yollar dikkate alınır, ama hepsi dikkate alınır. Halka oluşturmamak koşulu gözardı edilecektir, çünkü hedef köy için toplam yol daha kısa olacaksa fazladan bir iki durak yapan bir güzergah tercih edilebilir. Örneğin, 0-5 bağlantısı var diye 1-5 bağlantısı bir kenara atılmaz. Buradaki gibi 13 km değil de, 4,5 km'den daha kısa bir yol olsaydı, 0-5 doğrudan bağlantısı yerine 0-1-5 yolu asfaltlanacak güzergah olarak seçilirdi.

13 nolu köy yolu bunun bir örneğidir. Şu an 0-4-13 güzergahıyla uzaklığı 31 km gözüken bu köye 0-5-7-14-13 güzergahından gitmek uzaklığı 13,5 km yapacaktır. Bu güzergahı 11 nolu köye kadar uzatmak belki 2 durak değil 4 durak yapar, ama o köyün uzaklığını 1 km daha azaltır.

Bu algoritmayla oluşturulan en kısa yollar ağacının toplam uzunluğu 117,5 km'dir. Asfaltlanacak yol uzunluğu 9 km artmıştır, ama ileride yakıt ve zaman maliyetlerini düşürecek olması nedeniyle, sanırız kaymakamımız artık hakettiği takdirleri alacaktır.