Dijkstra Algoritması Python & C++ (Misal)

En kısa yol veya en kısa mesafe nedir?

Kaynak düğümden hedef düğüme en düşük maliyetli yol, en kısa yol veya en kısa mesafe olarak adlandırılır. Grafik teorisinde, bir kaynaktan bir hedefe birden fazla yol olabilir. Bu yollar arasında, en düşük maliyetli yol varsa, buna en kısa yol denir.

Burada "maliyet", rotadaki düğüm sayısını veya her kenardaki maliyetlerin toplamını ifade eder. Bir yolun bir veya birden fazla kenarı olabilir. İki köşe arasındaki bağlantıya "kenar" denir. Dijkstra algoritması ve Bellman-Ford algoritması gibi çeşitli en kısa yol algoritmaları vardır.

Burada Dijkstra algoritmasını ele alacağız. Aşağıdaki ağırlıklı grafiğe bakalım:

Yönlendirilmemiş Ağırlıklı Grafik

• "Ağırlıklı" terimi, bir düğümden diğerine geçmenin maliyetini ifade eder. Örneğin, 1. düğümden 2. düğüme geçmenin maliyeti veya ağırlığı 1'dir.
• 1. düğüm ile 2. düğüm arasındaki yola kenar denir.
• "Yönlendirilmemiş" demek, bir düğümden diğerine ve tekrar önceki düğüme gidebileceğiniz anlamına gelir. Dolayısıyla, 1. düğümden 7. düğüme giden tüm rotaları bulmaya çalışırsak, bunlar şöyle olacaktır:

Bu dört rota arasında, ilk rotanın maliyetinin 7 olduğunu görüyoruz. Dolayısıyla, maliyet açısından en kısa yol budur.

En kısa yol

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

Dijkstra algoritması, hem yönlü hem de yönsüz ağırlıklı grafiklerde en kısa mesafeyi bulabilir. Bu algoritma açgözlüdür çünkü her zaman orijinden en kısa veya en yakın düğümü seçer. "Açgözlü" terimi, bir sonuç veya çıktı kümesi arasından algoritmanın en iyisini seçeceği anlamına gelir.

Burada, diğer tüm rotalar arasında en kısa yolu bulmaya çalışıyoruz. Dolayısıyla, Dijkstra algoritması tek bir kaynak düğümden tüm en kısa yolları bulur. Sonuç olarak, şu şekilde davranır: Açgözlü algoritma.

Aşağıdaki "örnek" bölümünde adım adım yaklaşımı göreceksiniz. İşlem şu şekilde gerçekleşir:

) 1 Adım Başlangıç ​​düğümünü 0 maliyetle, diğer düğümleri ise sonsuz maliyetle başlatın.
) 2 Adım Bir dizi veya listeyi muhafaza edin. tracZiyaret edilen düğümlerin k tanesi.
) 3 Adım Düğüm maliyetini minimum maliyetle güncelleyin. Bu işlem, mevcut maliyeti yol maliyetiyle karşılaştırarak yapılabilir (örnek bölümünde gösterilmiştir).
) 4 Adım Tüm düğümler ziyaret edilene kadar 3. adıma devam edin.

Tüm bu adımları tamamladıktan sonra kaynaktan hedefe kadar maliyeti minimum olan yolu bulacağız.

Dijkstra ve BFS, DFS Arasındaki Fark

Dijkstra ve BFS-DFS arasındaki temel fark, Dijkstra'nın en kısa yolu bulma algoritması olması, BFS ve DFS'nin ise genel yol bulma algoritmaları olmasıdır. Genel durumlarda, BFS ve DFS yol bulurken kenar maliyetini dikkate almaz. Bu nedenle, bu algoritmalar en kısa yolu garanti edemez.

BFS'nin Nasıl Çalıştığını Gösteren 2 Boyutlu Izgara Gösterimi

Algosketch, BFS gösterimini gösteriyor

Bu gösteri BFS'nin yalnızca yolu bulduğunu gösterir. Ancak yolun ağırlığı umrunda değil. BFS'ler (Kapsamlı Arama), bir düğümden diğer düğüme seyahat etmenin yalnızca 1 dolara mal olacağını varsayar.

Şimdi bir örnek grafiğe bakalım:

Burada, BFS 2. seviyede bir yol buluyor. BFS, grafı seviye sırasına göre tarar. Dolayısıyla, şu şekilde ilerler:

) 1 Adım “1” numaralı düğümden başlayarak bitişik tüm düğümleri (2, 3, 4) ziyaret edin.

) 2 Adım 2, 3 ve 4 numaralı düğümleri 1. seviye olarak işaretleyin ve bitişik düğümleri ziyaret edin. Hedef düğüme ulaşana kadar tüm bitişik düğümleri keşfetmeye devam edecektir.

DFS açısından 1'den 7'ye kadar olan yolu aşağıdaki gibi kat edecektir:

• 1→2→3→7 (Orijinal Maliyet 10, DFS maliyeti 3)
• 1→2→6→7 (Orijinal Maliyet 7, DFS maliyeti 3)
• 1→3→7 (Orijinal Maliyet 8, DFS maliyeti 2)
• 1→4→5→7 (Orijinal Maliyet 13, DFS maliyeti 3)

Gördüğümüz gibi, DFS yol maliyetini kenar sayısıyla hesaplar. DFS aşağıdaki işlemleri yapar:

• DFS, kaynaktan (başlangıç ​​tepe noktasından) hedefe kadar bir yol bulabilir.
• Kaynak düğümden hedefe giden yolun en kısa yol olup olmadığını garanti edemez.

Ancak Dijkstra algoritması, kenarları maliyetlerine göre seçer. Açgözlü bir algoritma olarak, en düşük maliyetli yolları seçecektir.

Dijkstra Algoritması Örneği

Dijkstra Algoritması, yolun toplam maliyetini hesaplamak için maliyet veya ağırlığı kullanır.

Dijkstra Algoritmasının hedefi bu toplam maliyeti veya ağırlığı en aza indirmektir. Yukarıda gösterilen örnekte, düğüm 1'den düğüm 7'ye en iyi yolları buluyoruz ve ardından tüm maliyetleri hesaplıyoruz.

Dijkstra algoritması, ağırlıkları hesaplayarak en kısa yolları bulur. Tüm olası yolları aramaz. Dijkstra algoritmasını bir örnekle açıklayalım. Örneğin, 1 numaralı düğümden 7 numaralı düğüme en kısa yolu bulmanız isteniyor.

Bu işlem için aşağıda adımlar verilmiştir:

) 1 Adım Başlangıç ​​düğüm maliyetini 0 olarak başlatın. Atayın. “Bilgi” Diğer düğümlere. Bu, kaynak ile düğüm arasında bir yolun bulunmadığı veya yolun henüz ziyaret edilmediği anlamına gelir.

) 2 Adım 1 numaralı düğümü seçtiğinizde, ziyaret edilmiş olarak işaretlenecektir. Ardından, 1 numaralı düğümün tüm komşu düğümlerini güncelleyin. 2, 3, 4, 1 numaralı düğümün komşu düğümleridir.

Bir maliyeti güncellerken aşağıdaki prosedürü izlememiz gerekir:

Yukarıdaki formülü kullanarak her düğümün maliyetini güncelleyebiliriz. Örneğin, 1 numaralı düğümdeydik ve bitişik düğümler olan 2, 3, 4'ün maliyetini güncellememiz gerekiyordu. Güncelleme sonrasında maliyetler şöyle görünecektir:

) 3 Adım “2” numaralı düğümün komşuları 6 ve 3'tür. “6” numaralı düğümün maliyetini, sonsuz (mevcut değer) ile 2 numaralı düğümün maliyeti + 2'den 6'ya giden yolun maliyetini karşılaştırarak güncelliyoruz. Basitçe söylemek gerekirse, “6” numaralı düğümün maliyeti 1+3 veya 4 olacaktır.

Düğüm 3, düğüm 2'nin komşusudur. Ancak önceki adımda maliyetini 7 olarak hesaplamıştık. Şimdi yolumuz 1-2-3 ise düğüm 3'ün maliyeti 10 olacaktır. Yol 1-2- 3'ün fiyatı 10, 1'den 3'e kadar olanların maliyeti ise 7'dir.

) 4 Adım 3 numaralı düğüm için komşu düğüm 7'dir. Dolayısıyla, 7 numaralı düğümün mevcut değerini yol maliyeti (7+1) veya 8 ile karşılaştırarak, 7 numaralı düğümün maliyetini güncelleyeceğiz. Bu da 8'dir. Bu nedenle, 1 numaralı düğümden 7 numaralı düğüme giden bir yol buluyoruz ve bu yol 1→3→7'dir. Maliyet 8'dir.

) 5 Adım 4 numaralı düğüm için, bitişik düğümün maliyetini buna göre güncelleyeceğiz. Dolayısıyla, "5" numaralı düğümün güncellenmiş maliyeti 8 olacaktır. 4. ve 5. adımlardan sonra, şöyle görünecektir:

Şimdi, 1-3-7 yolunun maliyeti 8'di (önceden). "7" düğümü ziyaret edilmiş olarak işaretlenmedi çünkü "6" düğümünden "7" düğümüne ulaşabiliyoruz. "1-2-6" yolunun maliyeti 4'tü. Dolayısıyla 1-2-6-7 yolunun maliyeti 7 olacaktır.

7 < 8 olduğundan, kaynak düğüm "1"den hedef düğüm "7"ye en kısa yol 1-2-6-7 olacak ve maliyeti 7 olacaktır. Daha önce 1-3-7 idi ve maliyeti 8 idi. Dolayısıyla, son grafik şu şekilde görünecektir:

Siyah çizgiyle işaretlenen kenar 1'den 7'ye en kısa yolumuzdur ve bize 7'ye mal olur.

Sözde Code Dijkstra Algoritması

İşte Dijkstra algoritmasının sözde kodu:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Dijkstra Algoritmasının Uygulanması

Dijkstra'nın algoritmasını kullanarak uygulamak için C++İşte kod:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] && distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] && graph[U][j] &&
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

Çıktı:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python Dijkstra Algoritmasının Uygulanması

Dijkstra'nın algoritmasını kullanarak uygulamak için Pythonİşte kod:

num_of_vertex = 7
def minimumDistance(distance, visited):
    _min = 1e11
    min_index = 1e11
    for i in range(num_of_vertex):
        if not visited[i] and distance[i] <= _min:
            _min = distance[i]
            min_index = i
    return min_index

def printParentNode(parent, i):
    if parent[i] == -1:
        return
    printParentNode(parent, parent[i])
    print("{} ".format(i + 1), end="")

def dijkstra(graph, src):
    distance = list()
    visited = list()
    parent = list()
    for i in range(num_of_vertex):
        parent.append(-1)
        distance.append(1e11)
        visited.append(False)
    distance[src] = 0
    for i in range(num_of_vertex - 1):
        U = minimumDistance(distance, visited)
        visited[U] = True
        for j in range(num_of_vertex):
            curr_distance = distance[U] + graph[U][j]
            if not visited[j] and graph[U][j] and curr_distance < distance[j]:
                parent[j] = U
                distance[j] = curr_distance
    print("Vertex\t\tDistance\tPath")
    for i in range(num_of_vertex):
        print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="")
        printParentNode(parent, i)
        print("")

graph = [
    [0, 1, 7, 6, 0, 0, 0],
    [1, 0, 9, 0, 0, 3, 0],
    [7, 9, 0, 0, 0, 0, 1],
    [6, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

Çıktı:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

Algoritmanın kaynak düğümden en kısa mesafeyi hesapladığını görebiliriz.

Dijkstra Algoritmasının Uygulanması

Dijkstra algoritmasının çok çeşitli kullanım alanları vardır. Bunlar arasında ağ iletişimi alanında yaygın olarak kullanılır. İşte Dijkstra algoritmasının gerçek hayattaki bazı kullanım alanları:

Dijkstra'da Google Haritalar: Yukarıdaki kod parçacığı çıktısından da görülebileceği gibi, bu algoritma en kısa yolları bulmanın temelini oluşturmaktadır.

Google Basit Dijkstra algoritmasını kullanmaz. Bunun yerine, değiştirilmiş bir sürümünü kullanır. Bir hedef seçtiğinizde, size birden fazla yol gösterir. Google Haritalar. Bu yollar arasından bazıları kullanıcı için sıralanmıştır. Bu yollar "zaman"a göre seçilir. Dolayısıyla, "zaman" en kısa yol için bir kenar maliyetidir.

IP Yönlendirmesinde Dijkstra: IP yönlendirme IP yönlendirme, ağ iletişimi terminolojisinde kullanılan bir terimdir. Veri paketinizin farklı yollar üzerinden alıcıya nasıl gönderildiğini açıklar. Bu yollar yönlendiricilerden, sunuculardan ve diğer ekipmanlardan oluşur. IP yönlendirmede farklı protokol türleri vardır.

Bu protokoller, yönlendiricinin verileri göndermek için en kısa yolları bulmasına yardımcı olur. Protokol isimlerinden biri "OSPF (Open Shortest Path First)"'dir. OSPF, Dijkstra algoritmasını kullanır. Yönlendirici, rotaların bir tablosunu tutar. Her yönlendirici, tablosunu komşu yönlendiricilerle paylaşır. Güncellenmiş tabloyu aldıktan sonra, tüm yolları tekrar hesaplamaları gerekir. Bu sırada yönlendirici, Dijkstra algoritmasını kullanır.

Dijkstra Algoritmasının Sınırlaması

Dijkstra algoritması, negatif kenarlara sahip bir grafikte en kısa yolu garanti edemez. Dijkstra algoritması şu prensiplere uyar:

• Bir düğümden diğerine en kısa yol izlenecektir.
• İki düğüm arasındaki en kısa yol seçildikten sonra tekrar hesaplanmayacaktır.

Burada negatif kenarları olan iki örneğe dikkat edin.

Soldaki grafikte, Üç köşe noktası vardır. Dijkstra algoritması grafikte aşağıdaki gibi çalışacaktır:

) 1 Adım Başlangıç ​​köşesi “1” sıfır olarak başlatılacaktır. Diğer düğümler sonsuzluğa sahip olacaktır.

) 2 Adım “1” numaralı düğümü ziyaret edilmiş olarak işaretleyin ve en kısa yola dahil edin.

) 3 Adım Kaynak düğüm 1'in "2" ve "3" düğümlerine olan mesafesi sonsuz olarak ayarlanmıştır, çünkü en kısa yol henüz hesaplanmamıştır. Bu nedenle, sonsuzdan daha az maliyetli herhangi bir yol, en kısa yola eklenecektir (açgözlü yaklaşım).

) 4 Adım Kaynak düğüm "1"den "2"ye olan mesafeyi güncelliyoruz. Mevcut ağırlık 5 olacak (5 < sonsuzluk). Benzer şekilde, düğüm "1"den "3"e olan mesafeyi 3 ağırlığıyla güncelliyoruz.

) 5 Adım Şimdi "1" düğümünden en kısa mesafeleri kontrol edersek, 1→2 kenarı için en kısa mesafenin 5 olduğunu görürüz. Bu nedenle, "2" düğümü ziyaret edilmiş olarak işaretlenecektir. Benzer şekilde, en kısa mesafe 3 olduğu için "3" düğümü de ziyaret edilmiş olarak işaretlenecektir.

Ancak, gözlemlediğimizde, maliyeti sadece 2 olan 1-3-2 yolunun olduğunu görüyoruz. Fakat Dijkstra algoritması, "1" düğümünden "2" düğümüne en kısa mesafenin 5 olduğunu gösteriyor. Dolayısıyla, Dijkstra en kısa mesafeyi doğru hesaplayamadı. Bunun nedeni, Dijkstra'nın açgözlü bir algoritma olmasıdır. Bu nedenle, bir düğüm ziyaret edildi olarak işaretlendiğinde, daha kısa bir yol mevcut olsa bile yeniden dikkate alınmaz. Bu sorun yalnızca kenarların negatif maliyetli veya negatif ağırlıklı kenarlar olması durumunda ortaya çıkar.

Dijkstra algoritması bu senaryoda iki düğüm arasındaki en kısa yolu hesaplayamıyor. Sonuç olarak, bu algoritmanın bazı dezavantajları var. Bu negatif kenar sorununu çözmek için "Bellman-Ford Algoritması" adı verilen başka bir algoritma kullanılıyor. Bu algoritma negatif kenarlarla da çalışabiliyor.

Dijkstra Algoritmasının Karmaşıklığı

Yukarıdaki uygulama iki "for" döngüsü kullandı. Bu döngüler köşe sayısı kadar çalışır. Yani, zaman karmaşıklığı O(V²)Burada "O" terimi, Dijkstra algoritması için bir varsayımı ifade eden bir gösterimdir.

Grafı bir "öncelik kuyruğu" kullanarak saklayabiliriz. Öncelik kuyruğu, ikili yığın veri yapısıdır. 2 boyutlu bir matristen daha verimli olacaktır. Minimum maliyetli kenar yüksek önceliğe sahip olacaktır. O zaman zaman karmaşıklığı şu şekilde olacaktır: O(E log V). Burada E kenar sayısı, V ise köşe sayısıdır.

Uzay karmaşıklığı O(V²), bir bitişiklik matrisi kullandığımız için (2 boyutlu dizi). Uzay karmaşıklığı, bitişiklik listesi veya kuyruk veri yapısı kullanılarak optimize edilebilir.

SSS