Dijsktra'nın Algoritması: C++, Python Kod Örneği
Sarah Chen
En kısa yol veya en kısa mesafe nedir?
Kaynak tepe noktasından hedef tepe noktasına minimum maliyetle ulaşan yol, en kısa yol veya en kısa mesafedir. Graf teorisinde, bir kaynaktan hedefe kadar birden fazla rotanın olması mümkündür. Bu rotalar arasında minimum maliyetli bir rota varsa buna en kısa yol algoritması diyebiliriz.
Burada “Maliyet”, rotadaki düğüm sayısı veya her yol üzerindeki maliyetlerin toplamı anlamına gelir. Bir yolun bir veya daha fazla kenarı olabilir. İki köşe arasındaki bağlantıya “kenar” denir. Dijkstra Algoritması, Bellman-Ford algoritması vb. gibi çeşitli en kısa yol algoritmaları vardır.
Burada Dijkstra Algoritmasını tartışıyoruz
Aşağıdaki ağırlıklı grafiğe bakalım:
- “Ağırlıklı” terimi, maliyetlerin bir düğümden diğerine taşınması anlamına gelir. Örneğin, düğüm 1'den düğüm 2'ye geçerken maliyet veya ağırlık 1'dir.
- Düğüm 1'den düğüm 2'ye kadar olan yola kenar denir.
- "Yönlendirilmemiş", bir düğümü diğerine taşıyabileceğiniz ve önceki düğüme geri dönebileceğiniz anlamına gelir. Yani, düğüm 1'den düğüm 7'ye kadar tüm rotaları bulmaya çalışırsak, o zaman şöyle olacaktır:
| Rota veya Yol | Ücret |
|---|---|
| 1-2-6-7 | (1+3+3) = 7 |
| 1-2-3-7 | (1+9+1) = 11 |
| 1-3-7 | (7+1) = 8 |
| 1-4-5-7 | (6+2+5) = 13 |
Bu dört rotadan ilkinin bize 7 dolara mal olacağını görüyoruz. Yani maliyet açısından en kısa yol.
Dijkstra Algoritması Nasıl Çalışır?
Dijkstra algoritması hem yönlendirilmiş hem de yönlendirilmemiş 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, Algoritmanın bir dizi sonuç veya sonuç arasından en iyisini seçeceği anlamına gelir.
Burada diğer tüm rotalar arasında en kısa yolları bulmaya çalışıyoruz. Yani Dijkstra Algoritması tek bir hedef düğümden gelen en kısa yolların tümünü bulur. Sonuç olarak şöyle davranır: Açgözlü algoritma.
Aşağıdaki “örnek” bölümünde adım adım yaklaşımı göreceksiniz. Aşağıdaki gibi çalışır:
) 1 Adım Başlangıç düğümünü 0 maliyetle ve düğümün geri kalanını Sonsuz Maliyet olarak başlatın.
) 2 Adım Ziyaret edilen düğümleri takip etmek için bir dizi veya liste tutun
) 3 Adım Düğüm maliyetini minimum maliyetle güncelleyin. Mevcut maliyet ile yol maliyeti karşılaştırılarak yapılabilir. (Örnek bölümde gösterimi gösterilmektedir)
) 4 Adım Tüm düğüm 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 yol bulma algoritması olması ve BFS, DFS'nin yol bulma algoritması olmasıdır. Genel olarak BFS ve DFS yolu bulurken maliyeti dikkate almazlar. Dolayısıyla bu algoritmalar en kısa yolu garanti edemez.
BFS'nin nasıl çalıştığını gösteren 2 boyutlu ızgara gösterimi
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.
Ama örnek bir grafik görelim:
Burada 2. seviyede bir yol bulur. BFS Grafiği seviye sırasına göre geçer. Yani şöyle seyahat ediyor:
) 1 Adım “1” düğümünden başlayın ve tüm bitişik düğümler 2,3,4'ü ziyaret edin
) 2 Adım 2,3,4 düğümünü seviye 1 olarak işaretleyin ve bitişik düğümlerini 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örüldüğü gibi DFS yol maliyetini derinlik sayısı veya kenar sayısı ile hesaplamaktadır.
DFS aşağıdakileri 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ı açısından kenarları maliyetlerine göre seçecektir. Açgözlü bir algoritma olarak en iyi veya minimum 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ı'nda ağırlıkları hesaplayarak en kısa yolları bulacaktır. Olası tüm yolları aramayacaktır. Dijkstra Algoritmasını bir örnekle gösterelim. Örneğin, düğüm 1'den 7'ye en kısa yolu bulmanız istendi.
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.
Düğümün geri kalanı, atayın “Enf”. Bu, başlangıç noktası (kaynak) ile düğüm arasında herhangi bir yol bulunmadığı veya yolun henüz ziyaret edilmediği anlamına gelir.
) 2 Adım Düğüm 1'i seçtiğinizde ziyaret edildi olarak işaretlenecektir. Daha sonra düğüm 1'in tüm bitişik komşularını güncelleyin. 2,3,4, düğüm 1'in 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. düğümdeydik ve onun bitişiğindeki 2,3,4 düğümünün maliyetini güncellememiz gerekiyordu.
Güncellemeden sonra maliyet veya ağırlık şu şekilde görünecektir:
Adım 3) “2” düğümü için, komşular 6 ve 3'tür. Sonsuzluğu (mevcut değer) karşılaştırarak maliyeti “6” olarak güncelliyoruz. Düğüm 2 + yol maliyeti 2'den 6'ya çıktı. Basitçe söylemek gerekirse "6" düğümünün maliyeti 1+3 veya 4 olacak.
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.
Adım 4) Düğüm 3 için, komşu düğüm 7'dir. Yani 7. düğümün mevcut değerini yol maliyeti (7+1) veya 8 ile karşılaştırarak 7. düğümün maliyetini güncelleyeceğiz. Yani 8.
Yani, 1. düğümden 7. düğüme giden bir yol buluyoruz ve bu 1 → 3 → 7'dir. Maliyet 8'dir.
Adım 5) Düğüm 4 için, bitişik düğüm maliyetini buna göre güncelleyeceğiz. Yani “5” düğümünün güncellenmiş maliyeti 8 olacaktır. 4,5 adımından sonra şöyle görünecektir:
Artık 1-3-7 yolunun maliyeti 8'di (önceden). "7" düğümü ziyaret edildi olarak işaretlenmedi çünkü "7" düğümünden "6" düğümüne ulaşabiliyoruz. “1-2-6” yolunun maliyeti 4 oldu. Yani 1-2-6-7 yolunun maliyeti 7 olacak.
7 < 8 olduğundan kaynak köşesi “1”den hedef köşesi “7”ye giden en kısa yol 1-2-6-7 olacak ve maliyeti 7 olacaktır. Daha önce 1-3-7 idi ve maliyeti 8'di.
Yani son Grafik şöyle görünecek:
Siyah çizgiyle işaretlenen kenar 1'den 7'ye en kısa yolumuzdur ve bize 7'ye mal olur.
Sözde Kod Dijkstra Algoritması
İşte Dijkstra Algoritmasının sözde kodu
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ Dijkstra Algoritmasının uygulanması
Dijkstra'nın algoritmasını kullanarak uygulamak için C++, iş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] & amp; & 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] & amp; & graph[U][j] & amp; &
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 piton, iş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] & lt; = _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 & lt;
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üğüme olan en kısa mesafeyi hesapladığını görebiliriz.
Dijkstra Algoritmasının Uygulanması
Dijkstra Algo'nun geniş bir kullanım alanı vardır. Bunlar arasında ağ alanında yaygın olarak kullanılmaktadır. Dijkstra Algoritmasının gerçek hayattaki bazı kullanımları:
Google haritasında Dijkstra: Temel olarak bu Algoritma en kısa yolları bulmanın omurgasıdır. Yukarıdaki kod parçacığının çıktısından görebileceğimiz gibi.
Google basit Dijkstra algoritmasını kullanmaz. Bunun yerine değiştirilmiş bir sürümünü kullanır. Bir varış noktası seçtiğinizde size Google Haritasında birden fazla yol gösterilir. Bu yollar arasında kullanıcı için bazı yollar sıralanmıştır. Seçilen bu yollar “zamana” dayanmaktadır. Yani “zaman” en kısa yol için bir uç maliyettir.
IP yönlendirmede Dijkstra: IP yönlendirme bir ağ terminolojisidir. Bu, veri paketinizin alıcıya farklı yollardan nasıl gönderildiği anlamına gelir. Bu yollar yönlendiricilerden, sunuculardan vb. oluşur. IP yönlendirmede farklı türde protokoller vardır.
Bu protokoller yönlendiricinin veriyi göndermek için en kısa yolları bulmasına yardımcı olur. Protokol adlarından biri “OSPF (Open Shortest Path First)”dür. OSPF, dijkstra algoritmasını kullanır. Yönlendirici bir rota tablosu tutar. Her yönlendirici tablosunu komşu yönlendiricilerle paylaşır. Güncellenen tabloyu aldıktan sonra, tüm yolları tekrar hesaplamaları gerekir. O sırada yönlendirici Dijkstra Algoritmasını kullanır.
Dijkstra Algoritmasının Sınırlaması
Dijkstra algoritması negatif kenar grafiğinde en kısa yolu garanti edemez. Dijkstra algoritması şu metodolojileri takip eder:
- 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ı var. Dijkstra, Graph üzerinde 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 Düğüm “1”i ziyaret edildi olarak işaretleyin ve onu en kısa yola ekleyin.
) 3 Adım Kaynak düğüm 1'in "2" ve "3" düğümlerine olan mesafesi, en kısa yol henüz hesaplanmadığından sonsuza ayarlanmıştır. Yani sonsuzdan daha az maliyetli olan herhangi bir yol en kısa yola eklenecektir (açgözlü yaklaşım).
) 4 Adım Kaynak köşesine veya kaynak düğümüne olan mesafe "1"den "2"ye güncelleniyor. Mevcut ağırlık 5 (5) olacaktır
) 5 Adım Şimdi, “1” düğümünden en kısa mesafeleri kontrol edersek, 5->1 kenarı için en kısa mesafenin 2 olduğunu buluruz. Yani, “2” düğümü ziyaret edilmiş olarak işaretlenecektir.
Benzer şekilde “3” düğümü de en kısa mesafe 3 olduğundan ziyaret edilmiş olarak işaretlenecektir.
Ancak gözlemlersek, maliyeti sadece 1 olan 3-2-2 yolu var. Ancak Dijkstra, “1” düğümünden “2” düğümüne en kısa mesafenin 5 olduğunu gösteriyor. Yani Dijkstra en kısa yolu hesaplayamadı. mesafeyi doğru şekilde ayarlayın. Bunun olmasının 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 bulunsa da yeniden değerlendirilmeyecektir. Bu sorun yalnızca kenarların negatif maliyetleri veya negatif ağırlık kenarları olduğunda ortaya çıkar
Dijkstra bu senaryoda iki düğüm arasındaki en kısa yolu hesaplamada başarısız oluyor. Sonuç olarak bu algoritmanın bazı dezavantajları bulunmaktadır. Bu negatif kenar problemini çözmek için “Bellman-Ford Algoritması” adı verilen başka bir algoritma kullanılmaktadır. Bu Algoritma negatif kenarlarla çalışabilir.
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ığı Ç(V2). Burada “0” terimi Dijkstra algoritması için varsayım veren bir gösterim anlamına gelmektedir.
Grafiği “Öncelik Kuyruğu” kullanarak saklayabiliriz. Öncelik kuyruğu, ikili bir yığın veri yapısıdır. 2D matristen daha verimli olacaktır. Minimum maliyete sahip olan 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ığı Ç(V2), 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.
