Home / Algoritmalar / Dijkstra Algoritması Nedir? Dijkstra Örnekli Anlatım & C Kodu

Dijkstra Algoritması Nedir? Dijkstra Örnekli Anlatım & C Kodu

Şimdi sıra en ünlü algoritmalardan bir tanesine geldi. Dijkstra Algoritması yazılım dünyasının ötesinde matematik dünyasında da sıkça adı geçen bir algoritmadır. En kısa yol bulmada kullanılan bu algoritmayı Algoritma Uzmanı farkıyla örnek üzerinde gösterimini gerçekleştirip daha sonra da yazılımını sizinle paylaşacağız.

Dijkstra algoritması adını kurucusundan alır. Algoritmanın temel amacı Graf üzerindeki en kısa yolu bulmaktır. Graf ismini ilk defa duyanların kafasını karıştırabilir. Bizler bilgisayar ortamında verileri tutarken belirli bir mantıkla tutmak zorundayız. En çok kullandığımız yöntemlerden birisi de verileri graf formatında tutmaktır. Graflar, üzerindeki düğümlerin birbirleri ile ilişkilerin gösterilmesi bakımından oldukça çok tercih edilmektedir. Türkiye haritasını graf, şehirleri ise graf üzerindeki düğümler olarak gösterebilirsiniz.

Dijkstra Algoritması Nasıl Çalışır?

Dijkstra algoritmasında bir tane başlangıç noktası seçilir. Geri kalan tüm düğümler sanki sonsuz uzaklıktaymış gibi düşünülmelidir. Biz düğümlere ulaştıkça uzaklıkları güncelleriz. Dijkstra’da her adımda bir düğümden çıkan komşulara bakılır ve daha kısa bir yol bulunmuşsa uzaklıklar güncellenir. Ve yine kendisine en yakın olan düğüme gidilir. Bu şekilde tüm graf üzerindeki düğümler dolaşılır ve en kısa yol bulunmuş olur. Tabii ki bir algoritma en güzel örnek üzerinde öğrenilir. Size Dikstra’nın En kısa Yol algoritmasını örnek üzerinde göstereceğiz.

Dijkstra Algoritması Örnek

Yukarıda örnek bir graf yapımız bulunmaktadır. Bu yapıdaki bağlantıların yönlü olduğuna dikkat edin. Yukarıdaki örnek yönlü graf örneğidir. Yönlü graflarda yalnızca okun yönüne hareket edebiliriz. Geriye dönüş olmaz, çift yönlü gidiş geliş için iki yönlü ok kullanılır. (Mersin-Niğde arası gibi mesela)

Dijkstra algoritmasını uygularken bir tane başlangıç noktası seçeriz. Bu başlangıç noktasının maliyeti sıfır (0) olur, diğer (keşfedilmemiş) tüm düğümlerin sonsuz maliyetli olduğu varsayılır.

Başlangıç noktası olarak Konya düğümünü seçiyorum. Aşağıdaki gibi bir tablo çizeriz.

1. Adım:

Başlangıç düğümü olarak Konya’yı seçtiğimize göre Konya’nın komşularının maliyetlerini güncelleriz.

Konya’nın komşuları Eskişehir, Mersin ve Antalya’dır. (okların yönüne dikkat edin) Bu düğümlere olan maliyetler güncellenmiştir. Diğer tüm düğümler hala sonsuz maliyettedir. Konya düğümü başlangıç düğümü olduğu için sıfır’dır, hep sıfır olarak kalacaktır.

Dikkat! Maliyetlerin altında yazan düğüm isimleri hangi düğümden geldiği bilgisini tutmak içindir. Kodlarken parent şeklinde kullanacağız.

 

2. Adım:

Bu adımda 1. satırdaki en az maliyetli düğümü seçeriz. Ancak şuna her zaman dikkat edeceğiz, seçeceğimiz düğüm asla ziyaret edilmiş düğüm OLMAMALI. En az maliyetli düğüm Eskişehir olduğu için Eskişehir’e gidiyoruz.

Eskişehir’den gidilebilecek tek bir düğüm var, o da Sivas (okların yönüne dikkat). Ancak Sivas’a maliyet 10’du neden 30 yazdık? Çünkü zaten Eskişehir’e gidişin maliyeti 20, Sivas’a gidiş de 10, toplam 30 olarak güncelleriz. (başlangıç noktamızın Konya olduğunu unutmayın, başlangıç noktası çok önemli)

 

3. Adım:

Yine en düşük maliyetli düğümü seçeceğiz, en az maliyetli düğümler Konya ve Eskişehir aslında ama biz bu iki düğümü de ziyaret ettik. (düğüm sütununda ismi varsa ziyaret etmişiz demektir) bu yüzden bu düğümlerin haricindeki en düşük maliyetli düğüme gideriz. O da Sivas.

Sivas’tan çıkan iki ok var, Bunlar Niğde ve Mersin. Niğde’ye Sivas’tan maliyet 10, ama Sivas’ın da 30 maliyeti var. Bu yüzden maliyeti 40 olarak güncelleriz. Mersin’e olan maliyet ise 40, Sivas’ın maliyetini de ekleyince 70 oluyor. Önceki maliyet ise 80’di, 70 sayısı 80’den küçük olduğu için Mersin’in maliyetini güncelleriz. İşte dijkstra algoritmasının esas olayını burada net olarak görüyoruz. Daha kısa bir yol bulmuş olduk.

 

4. Adım:

Bu adımda yine en düşük maliyetli, ziyaret edilmemiş düğümü seçiyoruz (3. satırdaki), o da Niğde (40).

Niğde düğümünün Sivas, Mersin ve Kayseri düğümlerine komşuluğu var. Sivas düğümüne gidiş, Sivas’ın maliyetini artırıyor (zaten oraya geldik) bu yüzden Sivas’ta güncelleme yapmıyoruz.

Eğer Negatif maliyetli kenarlar olsaydı iş burada değişirdi, ancak dijkstra algoritması negatif kenarları hesaplamaz. (Hata verir, loop’a girer)

Geriye Kayseri ve Mersin kalıyor. Niğde Kayseri arası 20, Niğde’nin maliyeti de 40, bu yüzden 60 olacak şekilde güncelliyoruz.

Mersin’e maliyet ise 10, Niğde’nin maliyeti ise 40, yani Mersin’in Maliyeti 50 oldu, önceki maliyet 70 olduğu için 50 şeklinde güncelliyoruz.

 

5. Adım:

Bu adımda en düşük maliyetli düğümü seçeceğiz, en düşük maliyetli düğüm Mersin. (Mersin ziyaret edilmedi çünkü)

Mersin’den bir tek Antalya’ya gidebiliyoruz. Mersin’e toplam maliyet 50, Mersin Antalya arası ise 20 maliyete sahip. Toplam 70 oluyor. Antalya’nın önceki maliyeti 90’dı bu yüzden 70 olarak güncelliyoruz.

 

6. Adım:

Yine bu adımda en düşük maliyetli, ziyaret edilmemiş düğümü seçeceğiz. 5. satıra (Mersinli satır) bakıp en düşük maliyetlinin Kayseri olduğunu görüyoruz.

En kolay adım bu oldu, zira Kayseri’nin hiç gidilebilecek komşusu yok, tüm maliyetleri aynı şekilde alta geçiriyoruz.

 

7. Adım:

Geriye kalan en küçük maliyetli düğüm Antalya oldu (Denizli’nin maliyeti sonsuz, diğer düğümler de ziyaret edilmiş durumda)

Antalya’dan bir tek Konya’ya yol var, ancak Konya’nın maliyeti zaten sıfır. (Çünkü oradan başladık) Bu yüzden güncelleme yapmıyoruz.

 

8. Adım:

Bu adımda en küçük maliyetli yol sonsuz değere sahip Denizli 🙂 Çünkü ziyaret edilmiş düğümleri baştan eliyoruz. Ama Denizlinin maliyeti sonsuz olduğu için herhangi bir güncelleme yapmanın olanağı yok. Neden Denizli’ye böyle oldu diye sorarsanız Graf yapısını tekrar inceleyin derim, çünkü Denizli’ye yol yok. Ulaşamadığımız Grafın değerini de güncelleyemeyiz. Yolu olmayan yere gidemeyiz. Bu yüzden Denizli +sonsuz olarak kalır. Yani biz Konya’dan diğer graflara olan en kısa yolları buldu.

 

Dijkstra Algoritması C Kodu


//Kodlar Geeks for Geeks'ten alınmıştır. Türkçe yorum satırları eklenmiştir.

#include <stdio.h>
#include <limits.h>
  
// Graftaki düğüm sayısını V global değişkeni ile ifade edeceğiz.
#define V 9

//En kısa yolu bulan yardımcı fonksiyon.
//Ziyaret edilmemiş düğümler içerisindeki en kısa maliyetli düğümü return ediyor.
int minDistance(int dist[], bool sptSet[])
{
   //İlk başta Sonsuz değer atıyoruz.
   int min = INT_MAX, min_index;
   //Aşağıdaki döngü ziyaret edilmemiş düğümler içerisinde min değerinden daha küçük
   //düğümleri tespit ediyor. En küçüğünü buluyor.
   for (int v = 0; v < V; v++)
     if (sptSet[v] == false && dist[v] <= min)
         min = dist[v], min_index = v;
  
   //En küçük düğümün indexini return ediyoruz.
   return min_index;
}
  
// Başlangıç noktasından diğer düğümlere olan maliyeti yazdıran fonksiyon.
int printSolution(int dist[], int n)
{
   printf("Dugumlerin ana kaynağa olan uzakligi");
   for (int i = 0; i < V; i++)
      printf("%d tt %dn", i, dist[i]);
}
  
// Dijkstra algoritmasının temel fonksiyonu
// Ağırlıklı graf yapımızı graph[V][V] dizisinde tutuyoruz
// int src ise başlangıç noktamız.
void dijkstra(int graph[V][V], int src)
{
     int dist[V];     //Başlangıç düğümünden bir başka düğüme olan uzaklığı burada tutacağız.
  
     bool sptSet[V];  //Düğüm ziyaret edildiğinde bu diziye aktarıyoruz. Böylece ziyaret edilmiş düğümleri kontrol edebileceğiz.

  
     //İlk başta Tüm düğümleri ziyaret edilmemiş olarak işaretliyoruz.
     for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
  
     //Başlangıç noktasının maliyeti her zaman sıfır olur.
     dist[src] = 0;
  
     // Tüm düğümlere olan uzaklığın (kaynaktan) bulunacağı döngüye giriş yapıyoruz.
     for (int count = 0; count < V-1; count++)
     {
       // Henüz ziyaret edilmemiş, en az maliyetli düğümü u değişkenine aktarıyoruz.
       int u = minDistance(dist, sptSet);
  
       // Bu düğümü (aslında indisini) ziyaret edildi olarak işaretliyoruz.
       sptSet[u] = true;
  
       // Mevcut düğümden diğer komşu düğümleri tarayan döngümüz
       for (int v = 0; v < V; v++)
  
         // !sptSet[v] => Eğer düğüm ziyaret edilmediyse VE 
         // graph[u][v] => Graf üzerinde bu nokta bulunuyorsa VE
         // dist[u] != INT_MAX ==> Maliyet Sonsuz değilse VE
         // ist[u]+graph[u][v] < dist[v] => Mevcut uzaklıktan küçükse
         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                       && dist[u]+graph[u][v] < dist[v])

            //Uzaklığı güncelliyoruz.
            dist[v] = dist[u] + graph[u][v];
     }
  
     // Kaynağa olan uzaklığı ekrana bastırıyoruz.
     printSolution(dist, V);
}
  
// driver program to test above function
int main()
{
   /* Ağırlıklı Graf Yapımızı  aşağıdaki gibi oluşturduk*/
   int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                      {4, 0, 8, 0, 0, 0, 0, 11, 0},
                      {0, 8, 0, 7, 0, 4, 0, 0, 2},
                      {0, 0, 7, 0, 9, 14, 0, 0, 0},
                      {0, 0, 0, 9, 0, 10, 0, 0, 0},
                      {0, 0, 4, 14, 10, 0, 2, 0, 0},
                      {0, 0, 0, 0, 0, 2, 0, 1, 6},
                      {8, 11, 0, 0, 0, 0, 1, 0, 7},
                      {0, 0, 2, 0, 0, 0, 6, 7, 0}
                     };
  
    //0 düğümünü başlangıç noktası olarak belirttik.
    dijkstra(graph, 0);
  
    return 0;
}

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir