Grokking Algorithms-3

Bölüm 6: Genişlik Öncelikli Arama (Breadth-First Search, BFS)

Genişlik öncelikli arama, iki şey arasında en kısa mesafeyi bulmaya yarar. En kısa mesafe, çok fazla anlam barındırabilir. Bahsedeceğimiz bu algoritma bir graf algoritmasıdır ve bu algoritmayı bilmek için önce grafları bilmek gerekiyor. Geniş öncelikli aramayı şuralarda kullanabilirsiniz,

• Dama Yapay Zekası yazarak, zafere giden en az hamleyi hesaplayabilirsiniz.
• Yazım denetimi yapabilirsiniz. (Örneğin: READED -> READER tek bir yazım hatası)
• Çevrendeki en yakın doktoru bulabilirsin.

Graf algoritmaları, en yararlı algoritmaların başında gelir.

Yazının ikinci bölümünü buradan okuyabilirsiniz.

Graflara Giriş

San Francisco’da olduğumuzu düşünelim. Twin Peaks’ten Golden Gate Köprüsü’ne(bridge) gitmek istiyoruz. Seçeneklerimiz şunlardır.

En az adımla gideceğimiz yolu bulacağımız algoritmamız ne olurdu?

Her seferinde tek bir adım gidersek, gidebileceğimiz tüm yerler şöyle olurdu.

Köprüye varamadık, demek ki ona tek bir adımda varamıyoruz. İki adımda varabilir miyiz?

Köprüye hâlâ varamadık. Köprüye iki adımda da varamıyoruz. Ya üç adımda?

Köprüye şimdi vardık. Demek ki, köprüye 3 adımda varıyormuşuz.

Köprüye götürecek başka rotalar da var ama onların adım sayısı daha fazla tutuyor(4 adım). Algoritma, köprüye en kısa rota olarak 3 adımlık uzunluğu buldu. Bu tip probleme, en kısa yol(shortest-path) problemi denir. Her zaman bir şeylerin en kısa halini bulmaya çalışırız. Arkaşımızın evine varabileceğimiz en kısa yol da olabilir. Satranç oyununda en az sayıda adımla Şah Mat yapma hamlesi de olabilir. En kısa yol problemlerini çözmeye çalışan algoritmaya, genişlik öncelikli arama(breadth-first search) denir.

Golden Gate Köprüsü’ne nasıl gideceğimizi bulmak için, atacağımız 2 adım var:

1. Problemi graf olarak modelle.
2. Genişlik öncelikli arama ile problemi çöz.

Graf Nedir?

Bir graf, bağlantıların kümesini modeller. Arkadaşlarımızla kağıt oyunu oynadığımızı düşünelim. Kimin kime borcu olduğunu modellemek istiyoruz.

Şöyle bir graf ile modelleyebiliriz.

Kimin kime borcunun olduğunu gösteren graf.

Her graf, düğümlerden ve kenarlardan oluşur.

Bir düğüm, direk olarak başka düğümlerle bağlı olabilir. Bu düğümlere, komşular deriz. Bu grafta, Alex ile Rama komşulardır.

Genişlik Öncelikli Arama(Breadth-First Search)

Genişlik öncelikli arama, daha önce gördüğümüz ikili arama algoritmasından daha farklı bir türde algoritmadır. Graflar üzerinde ilerleyebiliriz.

• Soru Tipi 1: A düğümünden B düğümüne gitmek için bir yol var mı?
• Soru Tipi 2: A düğümünden B düğümüne gitmek için en kısa yol nedir?

Şimdi, ilk soruyla başlayalım, herhangi bir yol var mı?

Mango çiftliği sahibi olduğumuzu düşünelim. Mangolarımızı satabileceğimiz bir mango satıcısı arıyoruz. Herhangi bir mango satıcısıyla Facebook’ta bağlantıda mıyız?

İlk arama, gayet basit. Önce, arkadaşlarımızın listesini yapalım.

Sonra, listedeki her bir insanı tara ve mango satıcısı mı diye kontrol et.

Hiçbir arkadaşımızın mango satıcı olmadığını düşünelim. Şimdi de, arkadaşlarımızın arkadaşlarını taramak zorunda kalırız.

Listeden birini araştırdığımız her seferinde, onun tüm arkadaşlarını da listeye ekleriz.

Bu şekilde, sadece arkadaşlarımızı değil arkadaşlarımızın arkadaşlarını da araştırmış oluruz. Bu algoritma ile, bir mango satıcısına denk gelene kadar tüm bağlantıları taramış oluruz. Bu algoritmaya, genişlik öncelikli arama denir.

En Kısa Yolu Bulma

Genişlik öncelikli aramadaki 2. soruya bakacak olursak,

• Soru Tipi 1: A düğümünden B düğümüne gitmek için bir yol var mı? (Ağınızda mango satıcısı var mı?)
• Soru Tipi 2: A düğümünden B düğümüne gitmek için en kısa yol nedir? (Mango satıcısına en yakın kim?)

Birinci soruyu cevaplamıştık, şimdi ikinci soruya bakalım. En yakın mango satıcısını bulabilir miyiz? Örneğin, kendi arkadaşlarımız 1.derece bağlantılar olsun, onların arkadaşları ise 2.derece olur.

İlk derece bağlantıyı, ikinci dereye bağlantıya tercih ederiz, ikinci derece bağlantıyı ise üçüncü derece bağlantıya tercih ederiz ve böyle devam eder. 1. derece bağlantılarda mango satıcısı olmadığına eminsen, o zaman 2. derece bağlantılara bakmalısın. Genişlik öncelikli arama, A’dan B’ye yol bulmakla kalmaz en kısa yolu da bulur.

Genişlik öncelikli aramanın işe yaraması için, listeye eklenmesine göre insanları aramak gerekir. Bu da başka bir veri yapısıdır ve buna kuyruk(queue) denir.

Kuyruklar

Kuyruk, gerçek hayatta neyi simgeliyorsa tam olarak aynı işi yapar.

Otobüs durağında arkadaşlarımızla beraber beklediğimizi düşünelim. Eğer kuyrukta ondan daha önceysen, otobüse de daha önce binersin. Kuyrukta bu şekilde çalışır. Kuyruklar, yığınlara(stack) benzerdir. Kuyruktaki elemanlara rastgele olarak erişemezsin. Bunun yerine, sadece 2 operasyon vardır: kuyruğa at(enqueue) ve kuyruktan al(dequeue).

Eğer kuyruğa yeni bir eleman ekleyeceksen, her zaman en sona eklersin. Kuyruktan bir eleman çıkaracaksan ise, her zaman en baştan çıkarırsın. Bu yüzden listeye ilk eklenen elemanlar, ilk araması yapılacak olanlardır.

Kuyruğa, FIFO(First In, First Out — İlk Giren İlk Çıkar) veri yapısı denir. Yığın ise LIFO(Last In, First Out — Son Giren İlk Çıkar) veri yapısıdır.

Kuyrukları bildiğimize göre, genişlik öncelikli aramaya geçebiliriz.

Grafı Gerçeklemek

İlk başta, grafı kod üzerinde gerçeklememiz gerekiyor. Bir graf, birkaç düğümden oluşur ve her düğüm, komşu düğümlerle bağlıdır. Böyle bir ilişkiyi nasıl tanımlarız: “siz -> bob”? Daha önce kullandığımız bir veri yapısını burada kullanabiliriz: hash tablosu. Bir hash tablosu, bir anahtardan bir değere adresleme yapar. Bu durumda, bir düğümden komşularına adresleme yaparız.

Bunu Python’da yazmak istersek,

graph = {}
graph[“you”] = [“alice”, “bob”, “claire”]

“you” anahtarını bir diziye adresledik. graph[“you”] diye çağırdığımızda, “you” anahtarının tüm komşularını dizi olarak almış olacağız.

Bir graf, düğümler ve kenarlar kümesidir. Grafları Python’da kodlamanız için bilmeniz gereken tek şey budur. Ya bunun gibi büyük bir graf olursa?

Python kodu şöyle olur:

Anahtar / Değer çiftini hangi sırada hash tablosuna eklediğimizin bir önemi yoktur.

Hash tablosunun bir sıralaması yoktur, yani hangi sırada anahtar/değer çiftini eklediğimizin bir önemi yoktur.

Anuj, Peggy, Thom ve Jonny’nin komşuları yoktur. Onları işaret eden bir ok vardır ama onlardan başka birilerini işaret eden bir ok yoktur. Buna, yönlü(directed) graf denir. Yönlü graflarda, düğümler arası ilişki tek yönlü olur. Yönsüz(undirected) graflarda ise, arada herhangi bir ok olmaz, her iki düğümde birbirinin komşusu olur. Örneğin, bu iki graf eşittir.

Algoritmayı Gerçeklemek

Algoritmanın uygulanması şöyle çalışır.

Öncelikle bir kuyruk başlat. Python’da çift-yönlü kuyruk olarak deque fonksiyonu kullanılabilir.

from collections import deque
search_queue = deque()       # Yeni bir kuyruk oluşturur
search_queue += graph[“you”] # Tüm komşularını kuyruğa atar

graph[“you”] diye çağırırsak, tüm komşularını dizi olarak alabiliriz. Bu komşular arama yapmak için kuyruğa eklenecek.

Kalanına bakalım.

Son bir şey: kişi mango satıcısı mı, person_is_seller, fonksiyonuna ihtiyacımız var.

def person_is_seller(name):
  return name[-1] == ‘m’

Bu fonksiyon, kişinin ismi “m” harfi ile bitiyor mu diye kontrol ediyor. Eğer bitiyorsa, o bir mango satıcısıdır. Örneği basitleştirmek için böyle bir yöntem kullandık. Şimdi de genişlik öncelikli aramayı detayına bakalım.

Ve algoritma şu durumlardan biri oluncaya kadar devam eder.

• Mango satıcısı bulunur ya da,
• Kuyrukta kontrol edilecek kimse kalmaz, ki bu durumda mango satıcısı yok demektir.

Alice ve Bob’un ortak bir arkadaşı var: Peggy. Bu yüzden Peggy kuyruğa iki kez eklenecek demektir.

Ama Peggy’i kuyruğa iki kez eklemek fazladan Peggy’i tekrardan kontrol etmek demektir. O yüzden bir insanı araştırdığımızda, onu araştırılmış diye işaretlememiz gerekir, ki tekrar araştırmayalım.

Eğer böyle yapmazsak, sonsuz döngüye girebiliriz. Mango satıcısı grafımızın şöyle olduğunu düşünelim.

Başlangıçta, tüm komşularımızı ararız.

Sonra, Peggy’i kontrol ederiz. O, mango satıcısı değildir. Bu yüzden, onun tüm komşularını kuyruğa atarız.

Sonra, kendimizi kontrol ederiz. Biz de mango satıcısı değiliz. Sonra komşumuz olduğu için tekrar Peggy’i ekleriz. Bu iş böylece sonsuz döngüye girmiş olur.

Her bir insanı kontrol etmeden önce, daha önce kontrol edilmediğinden emin olmamız gerekiyor. Bunu yapmak içinse, daha önce kontrol edilmiş mi diye bir liste tutarız.

Genişlik öncelikli arama için kodumuzun son hali şöyle olur.

Çalışma Zamanı

Mango satıcısı için tüm ağımızda arama yaptığımızda, her bir kenarı takip edeceğimiz anlamına gelir. Bu yüzden çalışma zamanı en azından O(kenar sayısı) olur.

Ayrıca, araştırılacak insanları kuyrukta tutmamız gerekiyor. Kuyruğa bir kişiyi eklemek O(1) zaman alır. Bunu her kişi için yapmak ise, O(kişi sayısı) kadar tutar. Genişlik öncelikli arama O(kişi sayısı + kenar sayısı) zamanlı çalışır. Genel ifadeyle, O(V+E) denilir. (V: Vertices — Köşeler, E: Edges — Kenarlar)

Bölüm 7: Dijkstra Algoritması

Son bölümde, A noktasından B noktasına nasıl gidileceğini görmüştük.

Bu yolun en hızlı olması ile ilgili bir şey demedik. En kısa yoldu, çünkü en az sayıda bölümden geçiyordu. Ya bu bölümlere seyahat zamanlarını da eklemiş olsaydık. Şimdi en hızlı yol hakkında konuşabilirdik.

Genişlik öncelikli arama en sayıdaki bölüm üzerinden yolu hesaplıyordu. En hızlı yolu hesaplamak istediğimizde, karşımıza Dijkstra Algoritması çıkar.

Dijkstra Algoritması İle Çalışma

Bu graf ile algoritmanın nasıl çalıştığına bakalım.

Her bölümün dakika cinsinden seyahat zamanı bulunur. Dijkstra Algoritması’nı kullanarak başlangıç noktasından bitiş noktasına en kısa zamanda gitmeyi bulacağız.

Genişlik öncelikli arama ile graf üzerinde arama yapsaydık, en kısa yolumuz şöyle olurdu.

En kısa yol, 7 dakika olurdu. Daha az zamanlı bir yol var mı diye kontrol edelim. Dijkstra Algoritması’nın 4 adımı vardır.

1. En ucuz düğümü bul. Bu, en az zamanlı düğümün bulunmasıdır.
2. Bu düğümün komşularının maliyetlerini güncelle. Bunu açıklayacağız.
3. Graftaki her düğümü tamamlayana kadar bu işleme devam et.
4. En son final yolunu hesapla.

Adım 1: En ucuz düğümü bul. Başlangıçta duruyoruz ve A düğümüne mi yoksa B düğümüne mi gideceğiz diye kendimize soruyoruz? Her bir düğüme varmak ne kadar sürerdi?

A düğümüne varmak 6 dakika, B düğümüne varmak ise 2 dakika. Geri kalan düğümleri henüz bilmiyoruz.

Tam olarak ne kadar süreceğini bilmediğimiz için, şimdilik bitişe sonsuz diyoruz. B düğümü daha yakındır.

Adım 2: B düğümünün tüm komşularının ne kadar süreceğini hesapla.

Artık, A düğümüne daha kısa bir yol bulduk. Önceden A düğümüne varmak 6 dakikaydı.

Eğer B düğümü üzerinden gitseydik, sadece 5 dakika sürerdi.

B düğümünün komşuları için daha kısa yollar bulursak, maliyetleri güncellememiz gerekiyor. Bu durumda, bulmuş olduk.

• A düğümüne daha kısa bir yol (6 dakikadan 5 dakikaya indi)
• Bitişe daha kısa bir yol (Sonsuzdan 7 dakikaya düştü)

Adım 3: Tekrarla!

Adım 1 Tekrar: Daha az zamanda gidebileceğimiz düğümü bul. B ile işimiz bitmişti, A’nın bir sonraki en küçük zamanını da bulmuş olduk.

Adım 2 Tekrar: A’nın komşularının maliyetlerini güncelle.

Şimdi Bitiş’e varmak 6 dakikaya düştü. Dijkstra Algoritması’nı her düğüm için çalıştırmış olduk. Bu noktada, şunları biliriz,

• B düğümüne varmak 2 dakika sürer
• A düğümüne varmak 5 dakika sürer
• Bitiş’e varmak ise 6 dakika sürer

Final yolumuz şöyle olur.

Genişlik öncelikli arama en kısa yol olarak bu yolu bulamazdı, çünkü 2 adımda Bitiş’e varmış olurdu.

Genişlik öncelikli aramada, en kısa yol en az sayıdaki bölüm demekti. Dijkstra Algoritması’nda ise, her bir bölüme bir ağırlık(numara) atarız. Sonra, Dijkstra en az ağırlıktaki yolu bize bulur.

Dijkstra Algoritması’nın 4 adımını tekrar gözden geçirirsek,

1. En ucuz düğümü bul. Bu, en az zamanlı ağırlıklı düğüm olur.
2. Bu düğümün komşularının daha ucuz bir yolu var mı, kontrol et. Eğer varsa, maliyeti güncelle.
3. Graftaki her düğüm için bunu yapana kadar tekrarla.
4. Final yolu hesapla.

Terminoloji

Şimdi, Dijkstra Algoritması’nın uygulamada olan daha fazla örneklerine bakalım. Öncesinde, bazı terminolojiyi açık hale getirelim.

Dijkstra Algoritması ile çalıştığımızda, graftaki her bir kenarın bir numarayla ilişkilendirilmiş bir ağırlığı olur.

Ağırlıkları olan grafa, ağırlıklı(weighted) graf denir. Ağırlıkları olmayana ise ağırlıksız graf denir.

Ağırlıksız grafta en kısa yolu hesaplamak için, genişlik öncelikli arama kullanırız. Ağırlıklı grafta en kısa yolu hesaplamak içinse, Dijkstra Algoritması kullanırız. Grafların içinde şunun gibi döngüler olabilir.

Şöyle bir grafta en kısa yolu bulmaya çalıştığımızı düşünelim.

Döngüyü takip etmek mantıklı mıdır? Döngüden kaçınacak şekilde bir yol kullanabiliriz.

Ya da döngü üzerinden bir yol takip edebiliriz.

A düğümü üzerinden daha fazla tur atabilirsiniz ama bu daha fazla ağırlık eklemekten başka bir işe yaramaz.

Daha önce de bahsettiğimiz gibi, yönlü graflarda iki düğüm birbirini işaret ediyorsa bu bir döngüye yol açar.

Yönsüz graflarda ise, her bir kenar başka bir tane döngü yaratır. Dijkstra’nın Algoritması sadece, yönlü ve döngü içermeyen graflarda işe yarar.

Piyano İçin Alışveriş

Bu, Rama. Rama, piyano kitabını gerçek bir piyano ile alışverişle takas etmenin bir yolunu arıyor.

Alex, “kitabına karşılık sana poster vereceğim” dedi. “Bu Destroyer adlı favori grubumun posteri. Ya da sana nadir olan LP ve Rick Astley veririm ve üzerine 5$ veririm.” Amy, “LP’nin çok iyi şarkıları olduğunu duydum. Gitarım veya davul setimi(drum set) poster veya LP ile takas edebilirim.” der.

Beethoven, “Piyanomu, Amy’nin herhangi bir araçlarıyla takas edebilirim” der.

Az bir parayla Rama, piyano kitabından gerçek bir piyanoya geçişin alışverişini yapabilir. Şimdi düşünmesi gereken şey, en az parayla bu transferi nasıl gerçekleştirebileceğiydi. Yapılan tekliflerin bir grafını çizelim.

Bu grafta, düğümler, Rama’nın alışverişini yapabileceği tüm ürünlerdir. Kenarlar üzerindeki ağırlıklar ise, alışveriş için fazladan ödeyeceği para tutarlarıdır. Gitar için posteri vermek isterse, üzerine 30$ vermek zorunda ya da gitar için LP’yi vermek isterse, o zamanda 15$ vermek zorunda. Rama, kitaptan piyanoya gidecek yolu en az masrafla nasıl bilebilir? Bu durumdan Dijkstra Algoritması kurtarabilir.

Başlamadan önce bazı ön ayarların yapılması gerekiyor. Her düğüm için bir maliyet tablosu yapmamız gerekiyor. Düğümün maliyeti, ne kadar pahalılıkla ürüne erişebileceğimiz olacaktır.

Algoritma çalışırken, bu tabloyu sürekli güncelleriz. Varış yolunu hesaplarken, tabloya bir ebeveyn sütünü gerekir.

Algoritmaya başlayalım.

Adım 1: En ucuz düğümü bul. Bu durumda, poster ile değiştirmenin maliyeti 0$. Poster ile daha ucuz alışverişin bir yolu var mıdır? Hayır, yok. Dijkstra Algoritması’nın anahtar fikri, her zaman graftaki en ucuz düğüme odaklanmamız.

Adım 2: Posterin komşularının maliyetlerini hesapla.

Gitar ve davul(drum) seti için artık fiyatlarımız var. Ata düğümleri olan Poster üzerinden değerleri set edildi.

Adım 1 Tekrar: LP bir sonraki en ucuz düğümümüz, sadece 5$.

Adım 2 Tekrar: LP düğümünün komşularının maliyetlerini güncelle.

Davul seti ve gitarın fiyatını güncelledik. Daha ucuz değişim maliyetlerini bulduk. Atalarını da “LP” olarak güncelledik.

Bas gitar bir sonraki en ucuz eleman. Onun da komşularını güncelleyelim.

Nihayet piyano için bir fiyata ulaşabildik, gitar üzerinden değiş tokuş yaparak. Gitar, piyanonun atası oldu. En sonunda, son düğüm davul setine göre de maliyetleri güncellersek, grafın son hali şöyle olur.

Rama, gitar üzerinden piyano almaktan daha ucuz bir yol buldu. O da, davul seti üzerinden piyano almak. Rama’nın yapacağı en ucuz alışveriş 35$ oldu.

Şimdi ise, son adıma kadar geldiğimiz güzergahı bulmak istiyoruz. Bunun için, piyanoların atasına bakalım.

Davul seti, piyanonun atası idi. Bu yüzden, bu kenarı takip edelim.

Davul setinin(drums) atası ise, LP idi. LP’nin atası ise, kitaptı. Böylece, tüm yolu bulmuş olduk.

Rama’nın yapacağı alışverişler şu şekilde olur.

Daha önce en kısa yol derken, iki konum arasındaki mesafeyi hesaplamaktan bahsetmiştik. Bu örnektenden de görüyoruz ki, en kısa yol her zaman fiziksel bir mesafe olmak zorunda değil. Genel olarak, bir şeyin değerini azaltmakla alakalı bir durum. Bu durumda, Rama, Dijkstra’nın sayesinde harcayacağı parayı minimize etmeye çalıştı.

Negatif Ağırlıklı Kenarlar: Gösterdiğimiz örnekte, kenar ağırlıkları hep pozitif idi. Eğer, negatif ağırlıklı kenarlarda en kısa yolu bulmak isteseydik, Bellman-Ford algoritmasını kullanabilirdik. Bu algoritmanın detaylarını şuradan inceleyebilirsiniz.

Algoritmanın Gerçeklenmesi

Dijkstra’nın kodda uygulanması nasıl olur bakalım. Örnek için kullanacağımız graf şudur.

Bu örneği kodlamak için, 3 tane hash tablosuna ihtiyaç duyarız.

Algoritma ilerlerken, maliyetler ve atalar hash tablolarını güncelleyeceğiz. İlk başta, graf tablosunu kodlamamız gerekir.

graph = {}

Son bölümde, bir düğümün tüm komşularını şu şekilde tuttuğumuzu görmüştük.

graph[“you”] = [“alice”, “bob”, “claire”]

Ama bu durumda, komşuları ve bu komşulara erişmek için maliyetleri tutmamız gerekir. Örneğin, A ve B adında 2 tane komşumuz var ise, şöyle gösterebiliriz.

Bu kenar ağırlıklarını başka bir hash tablosu ile gösterebiliriz.

graph[“start”] = {}
graph[“start”][“a”] = 6
graph[“start”][“b”] = 2

graph[“start”] bir hash tablosudur. Şu şekilde onun bütün komşularını öğrenebiliriz.

>>> print graph[“start”].keys()
[“a”, “b”]

Bu kenarların ağırlıklarını bulmak istersek de, şöyle olur.

>>> print graph[“start”][“a”]
2
>>> print graph[“start”][“b”]
6

Kalan düğümleri ve onların komşularını da grafa ekleyelim.

graph[“a”] = {}
graph[“a”][“fin”] = 1
graph[“b”] = {}
graph[“b”][“a”] = 3
graph[“b”][“fin”] = 5
graph[“fin”] = {}  # Bitiş düğümünün komşusu olmaz

Grafın tüm hash tablosu şu şekilde olur.

Her düğümün maliyetlerini tutabilmek için ayrıca bir hash tablosuna ihtiyaç duyarız.

Düğümün maliyeti, başlangıçtan o düğüme gelene kadar olan maliyeti kadardır. Başlangıçtan B düğümüne gelme maliyetinin 2 dakika olduğunu biliyoruz. A düğümün ise, 6 dakika olduğunu biliyoruz. Henüz bitişe varmanın ne kadar maliyeti olduğunu bilmediğimiz için sonsuz diye işaretliyoruz. Python’da bunu göstermeyi şöyle yapabiliriz.

infinity = float(“inf”) # sonsuzluk

Maliyet hash tablolarının kodları şöyle olur.

infinity = float(“inf”)
costs = {}
costs[“a”] = 6
costs[“b”] = 2
costs[“fin”] = infinity

Düğümlerin atasını tutmak için başka bir hash tablosuna ihtiyaç duyarız.

Bu hash tablosu için gereken koda bakalım.

parents = {}
parents[“a”] = “start”
parents[“b”] = “start”
parents[“fin”] = None

Son olarak, tekrar tekrar işlem yapmamak için üzerinden ilerlediğimiz düğümleri tutmak için bir dizi tutarız.

processed = [] # üzerinde işlem yapılmış düğümler

Tüm kurulumları yaptık, şimdi algoritmaya bakalım.

Önce kodu gösterelim sonra da adım adım üzerinden ilerleyelim.

Dijkstra’nın Python dilinde kodlanması bu şekilde olur. Algoritma içindeki find_lowest_cost_node fonksiyonuna bakalım

En düşük maliyetli düğümü bul.

Bu düğümün maliyetini ve komşularını bul.

Komşular üzerinde dön.

Her düğümün bir maliyeti vardır. Maliyet, başlangıçtan itibaren bu düğüme ne kadar sürede ulaşmanın maliyetidir. A düğümüne B düğümü üzerinden ulaşmak için, Başlangıç > Düğüm B > Düğüm A yolunu takip ederiz.

Maliyetleri karşılaştıralım.

A düğümüne ulaşacak daha kısa bir yol bulduğumuza göre, maliyetleri güncelleyebiliriz.

Yeni yol B üzerinden gittiği için, B düğümünü yeni ata olarak değiştiririz.

Döngünün tekrar başına döndük. Bir sonraki komşu Bitiş düğümü olur.

B düğümü üzerinden, Bitiş düğümüne varmak ne kadar sürer?

7 dakika sürer. Daha önceki değer sonsuz idi, şimdiki değer ise 7 dakika olur.

Yeni maliyeti ve yeni atayı, Bitiş düğümü için güncelleyelim.

B düğümün tüm komşularının maliyetlerini güncelleyelim. Üzerinde çalışılmış(işlenmiş) olarak güncelleyelim.

İşlenecek bir sonraki düğümü bulalım.

A düğümünün komşularını ve maliyetini bulalım.

A düğümünün bir komşusu var: Bitiş düğümü.

Şu anda, Bitiş düğümüne varmak 7 dakika sürüyor. A üzerinden gitmek istesek, ne kadar sürerdi?

A üzerinden Bitiş’e varmanın maliyeti daha düşük. Maliyeti ve ata düğümü güncelleyelim.

Tüm düğümleri işlediğimize göre, algoritma bitmiş olur. Adım adım açıklanması ile algoritmanın anlaşılması daha kolay olmuştur. En son, find_lowest_cost_node fonksiyonuna bakacak olursak, kodu şöyle olur.

Bölüm 8: Açgözlü(Greedy) Algoritmalar

…