Merhaba dostlarım, bu makalemde sizlere yazılım dünyasında en çok kullanılan algoritmaların başında gelen
"Dijkstra Algoritması"
hakkında bilgi vereceğim.
Makalede "Dijkstra Algoritması"nı yakından tanıyacak, neden bu kadar popüler olduğunu kavramış olacaksınız.
Ayrıca yine makalede bu algoritmanın "Python3" kodu ile nasıl yapıldığının örneğini vereceğim.
Foruma katkısı ve bu alanda çalışacak arkadaşlara faydalı olması dileğiyle diyerek başlamak istiyorum.
İyi okumalar.
|
|
v
Dijkstra Algoritması
Algoritmaya geçmeden önce “Graph (Grafik)” kavramına değinmek istiyorum.
Basit olarak anlatmak gerekirse grafikler; genelde eş zamanlı nesneler, varlıklar, şahıslar ile düğümler arasında bulunan kenar bağlantılar ve düğüm (tepe) öğeleri arasındaki bağlantıları göstermek için oluşturulan veri yapılarıdır. Aynı zamanda, herhangi iki düğüm sadece aralarında bir kenar bulunuyor ise bağlanabilir.
Grafikler için, “Kenarlar ile birbirine bağlanan düğümlerin aralarındaki ilişkilerdir.” Cümlesini kullanabiliriz.
Gerçek hayat ile uygun grafikleri iki bölümde inceleyebiliriz;
Undirected Graphs (Yönsüz grafikler); İlişkisi bulunan her çift düğüm için, bir düğümden diğerine çift yönlü hareket edilebilen grafiklerdir.
Directed Graphs (Yönlendirilmiş grafikler); İlişkisi bulunan her çift düğüm için, belirli bir doğrultuda bir düğümden diğerine tek yönlü hareket edilebilen grafiklerdir.
Peki, bir diğer kavram olan “Weighted Graphs (Ağırlık grafikleri)” nedir?
Ağırlık grafikleri; birazdan anlatacağım “Dijkstra Algoritmaları” için oldukça önemlilerdir. Grafiğin kenarlarının belirli bir ağırlığa veya maliyete sahip olduğu, bu değerlerin mesafe, para, zaman gibi düğümler arasındaki ilişkilerini yansıtabilen grafiklere “Ağırlık Grafiği” denir.
Dijkstra algoritası nedir?
Dijkstra Algoritması, 1956 yılında bilgisayar bilimci “Edsger W. Dijkstra” tarafından tasarlandı. Algoritma aslında, bir grafikteki belirli bir düğümden diğer tüm düğümlere giden en kısa yolu bulan yinelemeli bir algoritmik süreçtir.
Dijkstra’nın bulduğu bu algoritma, kaynak düğümden diğer tüm düğümlere giden toplam mesafeyi (ağırlık) en aza indirecek olan yolu bulmak için grafik kenarlarının ağırlıklarını kullanır.
Algoritma aynı zamanda “Tek kaynaklı en kısa yol algoritması” tanımında da kullanılır ve bilinir.
Burada dikkat etmemiz gereken bir husus var. Algoritma yalnızca tüm ağırlılar pozitif değerlerde iken doğru çalışmaktadır. Bunun nedeni, en kısa yol bulunurken kenarların ağırlıklarının eklenmesidir. Yani bir grafikte kenarlardan herhangi biri negatif tanımlanırsa algoritma istenilen sonucu bulamayacaktır. Yinede bazı algoritmalar (Bellman-Ford gibi) ile bu problem aşılabilir.
Dijkstra Algoritması genel olarak, amaçlanan en kısa mesafeye varana kadar doğru mesafenin yaklaşık olarak hesaplanan değerinin daha uygun değerler ile yer değiştirmesi olayını kullanır. Bu olaya “Gevşeme ilkesi” denir.
Öte yandan, düğümlere olan tahmini mesafe her zaman doğru mesafenin oldukça üstünde bir değerdir ve yakın zamanda belirlenen mesafe ile bir önceki değerin en küçük olanı değiştirilir.
Algoritma temelleri ve uygulama adımları
Temel olarak Dijkstra algoritması, seçilen (kaynak) düğümden başlayarak diğer tüm düğümler ile olan aradaki mesafeyi ölçmek ve en kısa yolu bulmak için grafiği analiz eder.
Algoritma, o an bilinen en kısa mesafeli düğümden yol alır ve daha kısa mesafeli bir düğüme rastladığında yolu değiştirir.
Kaynak düğüm ile bir diğer düğüm arasında bulunan en kısa yola denk gelinirse, algoritma bu düğümü “Visited (Ziyaret edildi)” olarak işaretler ve yoluna ekler.
Bu işlem, grafik üzerinde bulunan tüm düğümler yola eklenene kadar devam eder. Böylece diğer tüm düğümlere ulaşmak için mevcut olan en kısa yollar keşfedilmiş olur.
Peki bu algoritmanın iyi çalışması için neler gerkli?
Bahsettiğim gibi, bu algoritmanındüzgün çalışabilmesi için grafiğin kenarlarının pozitif değerlerde olması gerekir. Negatif bir değer işleri zora sokacaktır.
Uygulama adımları:
İlk adımda algoritma, grafikte bulunan ttüm düğümleri “ziyaret edilmemiş” olarak işaretler.
Seçilen (kaynak) düğümün geçerli mesafesini “0” olarak, geride kalan düğümlerin ise “oo” olarak işaretler.
Ardından seçilen düğümü mevcut düğüm olarak düzenler.
Mevcut düğüm için, henüz ziyaret edilmeyen tüm komşuları analiz eder. Mevcut düğümün mesafesini, komşu düğümler ile aralarındaki kenarların ağırlığına ekleyerek mesafe ölçümü yapar.
Bu mesafeyi komşu düğüme atanan mevcut mesafe ile karşılaştırır ve bu değeri komşu düğümün yeni mesafesi olarak düzenler.
Diğer tüm ziyaret edilmeyen komşu düğümlere bakılır ve mevcut düğümü “ziyaret edildi” olarak işaretler.
Eğer gelinen noktada hedef düğüm ziyaret edildi olarak işaretlenmiş ise algoritma işlemi sonlandırır. Aksi durumda ise, en az mesafe ile işaretlenmiş düğüme gider ve 4. Basamaktan tekrar devam eder.
Görsel anlatım
Makalenin bu başlığı altında, sizlere hazırlamış olduğum görseller ile konunun daha pekiştirilmesi adına bir anlatım yapacağım.
Aşağıdaki gibi bir grafiğe sahip olduğumuzu varsayalım. Bu grafikte 7 adet düğüm noktası bulunuyor. Bunlar "A,E,C,B,D,F,G" düğümleri.
Bu düğmler arasında bulunan ve ok ile gösterilen bağlar ise kenarlarımızdır.
Biz, "A" düğümünü başlangıç, "G" düğümünü ise varış noktası olarak almak istiyoruz. Algoritma burada bizlere "A'dan G'ye en kısa mesafede nasıl giderim?" sorusunun cevabını vermeli.
1. Aşama:
A düğümünü başlangıç düğümü olarak ele alalım ve “0” ile simgeleyelim. Başlangıç pozisyonunda diğer düğümlerin herhangi bir erişim imkanı olmadığı için “sonsuz işareti” ile simgeleyelim.
2. Aşama:
Başlangıç düğümünden (A) başlayarak komşu düğümlerin uzaklık değerlerini tablomuza yazalım. Burada, komşulardan en az mesafeye sahip olan düğümü seçerek ilerleyeceğiz.
“A” düğümünün 3 adet komşusu var. Bunlar “B,C,E” düğümleri. Mesafe değerlerine baktığımızda ise “A > E = 1, A > C = 6, A > B = 5” değerlerini görüyoruz. Burada en düşük değere sahip olan yolu seçeceğimizden “E” düğümü ile devam ediyoruz.
3. Aşama:
“E” düğümünün ise tek komşusu var. “C” düğümü ile devam edeceğiz. Burada “A > E = 1, E > C = 2” yolunu izlediğimiz için “C” düğümünün yeni değeri “1+2 = 3” oldu. “A > C veya A > B” yolları gördüğünüz gibi daha masraflı olduğundan “C” düğümünden devam ediyoruz.
4. Aşama:
“C” düğümü iki adet komşuya sahip. Bunlar “B,D” düğümleri. “D” düğümünün maliyeti (mesafe) “C+4= 7” ve “B” düğümünün maliyeti “C+1= 4” olduğunu görebiliyoruz. Burada maliyeti daha düşük olan “B” düğümü ile devam edeceğiz. Burada “B” düğümünün değerini güncellemeyi unutmayın.
5. Aşama:
“B” düğümünün tek komşusu var. “F” düğümü burada izleyeceğimiz yol olacak. Değerini ise “B+1= 5” olarak güncelleyelim.
6. Aşama:
“F” düğümünün 2 adet komşusu var. Bunlar “D,H” düğümleri. “D” düğümünün maliyetinin “F+3= 8” ve “G” düğümünün maliyetinin “F+2= 7” olduğunu görebiliyoruz. En az maliyet ile yol alacağımız için “G” düğümü ile devam edip işlemi bitiriyoruz.
Doğru yol:
Başlangıç düğümünden başlayarak tüm düğümleri gezdik.”A” düğümünden “G” düğümüne giden en kısa yol ise şu şekildedir;
A > E > C > B > F > G
1+2+1+1+2=7
Python3 kodu
Kodları yanlarında yorum satırı olarak açıkladım dostlar.
Python:
# by w1sd0m
# Gerekli kütüphanenin içeri alınması
import heapq
# Graph oluşturma fonksiyonu
def distance_calculation(graph, starting_node):
distances = {node: float('infinity') for node in graph}
distances[starting_node] = 0
# Diğer düğümlerin başlangıç düğümüne olan mesafeleri
hq = [(0, starting_node)]
while len(hq) > 0:
current_distance, current_node = heapq.heappop(hq)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(hq, (distance, neighbor))
return distances
# Kendi graph'inizi buraya yazabilirsiniz.
my_graph = {
"A": {"B":5,"E":1,"C":6},
"B":{"A":5,"F":1,"C":1},
"C":{"A":6,"E":2,"B":1,"D":3},
"F":{"B":1,"D":3,"G":2},
"E":{"A":1,"C":2,"E":5},
"D":{"C":4,"F":3,"G":5},
"G":{"D":5,"F":2,},
}
print(distance_calculation(my_graph, 'A'))Biz manuel olarak sonucu "7" bulmuştuk. Bakalım Python3 ile aynı sonucu bulabilecek miyiz?
Kodu çalıştırdığımızda aldığımız çıktı şu şekildedir;
Görüldüğü üzere kodumuz düzgün çalışıyor ve bize doğru cevabı gösterebiliyor.
Sizlerde, kendi grafiklerinizi koda yerleştirerek farklı denemeler yapabilirsiniz. Tavsiyemdir.
Avantaj / Dezavantaj
Algoritmanın bazı avantajlarına şunları diyebiliriz;
Anlaşılması ve uygulaması basittir.
Hedeflenen düğüm için belirlediği en kısa mesafeye ulaştığında işlemi durdurur.
Tek düğümden diğer tüm düğümlere mesafe analizi yapar ve bunu oldukça hızlı yapar.
Sadece yönlendirilmiş, ağırlıklı grafiklerde düzgün çalışır. Ayrıca negatif kenar değerine sahip olmaması gerekir.
Negatif kenar olsa dahi bunu birkaç algoritma ile çözmeye imkan verir.
Algoritmanın bazı dezavantajlarına şunları diyebiliriz;
İşleme aşamasında gereğinden fazla vakit harcar ve belirsiz bir keşif yapar.
Grafikte negaif kenar olmamalıdır. Çünkü bunları işleyemez.
Döngüsel olmayan grafiğe yöneldiğinde, en kısa yolu elde edemeyebilir.
Ziyaret edilen kenarların takip edilmesi gerekir.
Uzun lafın kısası
Grafikler; şahıslar, nesneler, varlıklar arasındaki bağlantıyı modeller. Bunları iki ana bölümde inceleriz: Düğüm ve Kenar. Düğümler varlıkları, şahısları, nesneleri temsil ederken kenarlar ise bunlar arasındaki bağlantıyı temsil eder.
Dijkstra algoritması, seçilen (kaynak) bir düğüm ile diğer düğümler arasındaki mesafeleri ölçerek en kısa mesafeyi bulur.
Algoritma, seçilen düğüm ile diğer tüm düğümler arasındaki mesafeyi en aza indirmek için kenar ağırlıklarını kullanır.
Genellikle bu algoritma, “Gevşeme” ilkesine bağlıdır.
^
|
|
|
|
Değerli dostlarım, güzel kardeşlerim;
Bu makalemde kısaca "Dijkstra Algoritması nedir?" sorusuna cevap bulduk.
Ardından "Adım adım" algoritmanın işleyişini ele aldık ve "Python3" koduna döktük.
Kaynak niteliğinde bu forumda kalması temennisi ile diyerek sözlerimi bitiriyorum.
Sağlıcakla kalın.
