Python'da Dijkstra Algoritmasını Uygulama: Adım Adım Eğitim

Neden Dijkstra Algoritmasını Öğrenmelisiniz?

Dijkstra, bir ağda iki nokta arasındaki en kısa yolu bulmak için başvurulan algoritmadır ve pek çok uygulaması vardır. Bilgisayar bilimi ve grafik teorisinin temel taşlarındandır. Onu anlamak ve uygulamayı öğrenmek, daha ileri seviye grafik algoritmalarına ve uygulamalara kapı açar.

Ayrıca, her adımda mevcut bilgiye göre en iyi seçimi yapmayı içeren açgözlü (greedy) yaklaşımıyla değerli bir problem çözme yöntemini öğretir.

Bu beceri diğer optimizasyon algoritmalarına da aktarılabilir. Dijkstra algoritması her senaryoda en verimli yöntem olmasa da “en kısa mesafe” problemlerini çözerken iyi bir başlangıç noktası olabilir.

Örnekler şunları içerir:

• GPS navigasyon sistemlerinin en hızlı rotayı bulması
• Bilgisayar ağlarında veri paketlerinin yönlendirilmesi
• Teslimat hizmetlerinin verimlilik için rotaları optimize etmesi
• Sosyal ağlar (bağlantı önerileri)
• Finans (optimal yatırım yollarının bulunması)
• Proje yönetimi (en verimli iş akışının belirlenmesi)

Bu konuların hiçbirine ilgi duymasanız bile, Dijkstra algoritmasını Python'da uygulamak size şu önemli kavramları pratik etme imkânı verir:

• Python sınıfları
• Sözlük (dictionary) kapsamaları
• Liste kapsamaları
• Öncelik kuyrukları

Grafiklerle İlgili Temel Kavramlar

Dijkstra algoritmasını Python'da uygulamak için grafik teorisinden bazı temel kavramları tazeleyelim. Öncelikle, grafiklerin kendisi:

Grafikler, düğümler (köşeler) ve bu düğümleri bağlayan kenarlardan oluşur. Düğümler bir ağdaki varlıkları ya da noktaları temsil ederken, kenarlar aralarındaki bağlantıları veya ilişkileri temsil eder.

Grafikler ağırlıklı veya ağırlıksız olabilir. Ağırlıksız grafiklerde tüm kenarlar aynı ağırlığa sahiptir (genellikle 1). Ağırlıklı grafiklerde ise (tahmin edeceğiniz üzere) her kenarla ilişkili bir ağırlık bulunur; bu ağırlık genellikle maliyet, mesafe veya zamanı temsil eder.

Bu eğitimde Dijkstra algoritması için gerekli olduklarından ağırlıklı grafikler kullanacağız.

Bir grafikte yol, belirli düğümlerde başlayıp biten ve kenarlarla birbirine bağlanan düğüm dizisini ifade eder. Bu eğitimde odaklandığımız en kısa yol ise toplam ağırlığı (mesafe, maliyet vb.) en az olan yoldur.

Dijkstra Algoritmasının Görsel Açıklaması

Eğitimin geri kalanında, en son gördüğümüz grafiği kullanacağız:

Dijkstra algoritmasını kullanarak B ve F noktaları arasındaki en kısa yolu, en az yedi olası yol arasından bulmayı deneyelim. İlk aşamada bunu görsel olarak yapacağız, kodu daha sonra yazacağız.

Öncelikle algoritmayı şu şekilde başlatırız:

1. B’yi kök (kaynak) düğüm olarak belirleriz.
2. B ile diğer tüm düğümler arasındaki mesafeleri ilk, geçici değerleri olarak sonsuz yaparız. B’nin değerini ise kendisine olan mesafe olduğundan 0 olarak ayarlarız:

Ardından, aşağıdaki adımları yinelemeli olarak uygularız:

1. En küçük değere sahip düğümü “geçerli düğüm” olarak seçip tüm komşularını ziyaret ederiz. Her komşuyu ziyaret ederken, geçici değerlerini sonsuzdan, kaynak düğümden başlayan kenar ağırlıklarına güncelleriz.
2. Geçerli düğümün tüm komşuları ziyaret edildikten sonra geçerli düğümü “ziyaret edildi” olarak işaretleriz. Bir düğüm “ziyaret edildi” olarak işaretlendiğinde, değeri zaten hedeften olan en kısa yolu ifade eder.
3. Algoritma 1. adıma geri döner ve en küçük değere sahip düğümü seçer.

Grafiğimizde B’nin üç komşusu vardır — A, D ve E. Kök düğümden başlayarak her birini ziyaret edelim ve değerlerini (yineleme 1) kenar ağırlıklarına göre güncelleyelim:

2. yinelemede, en küçük değere sahip düğümü tekrar seçeriz — bu kez E. Komşuları C, D ve G’dir. B daha önce ziyaret edildiğinden hariç tutulur. E’nin komşularının değerlerini güncelleyelim:

C’nin değerini 5,6 olarak ayarlarız; çünkü değeri B’den C’ye kadar olan ağırlıkların kümülatif toplamıdır. G için de aynı durum geçerlidir. Ancak fark edeceğiniz üzere, D’nin değeri 3,5 olarak kalır; oysa diğer düğümlerde olduğu gibi 3,5 + 2,8 = 6,3 olmalıydı.

Kural şudur: Yeni kümülatif toplam düğümün mevcut değerinden büyükse, güncellemeyiz; çünkü düğüm zaten köke olan en kısa mesafeyi gösteriyordur. Bu durumda, D’nin mevcut 3,5 değeri, B ile komşu oldukları için B’ye olan en kısa mesafeyi zaten belirtmektedir.

Tüm düğümler ziyaret edilene kadar bu şekilde devam ederiz. Bu nihayet gerçekleştiğinde, B’den her düğüme olan en kısa mesafeyi elde etmiş oluruz ve B’den F’ye olan değeri doğrudan okuyabiliriz.

Özetle adımlar şunlardır:

1. Grafiği başlatın: kaynak düğümün değeri 0, diğer tüm düğümlerin değeri sonsuz olsun. “Geçerli düğüm” olarak kaynakla başlayın.
2. Geçerli düğümün tüm komşularını ziyaret edin ve değerlerini kaynaktan olan ağırlıkların (mesafelerin) kümülatif toplamına güncelleyin. Bir komşunun mevcut değeri kümülatif toplamdan küçükse aynı kalır. “Geçerli düğüm”ü tamamlandı olarak işaretleyin.
3. Tamamlanmamış düğümler arasında en küçük değere sahip olanı “geçerli düğüm” olarak işaretleyin.
4. Tüm düğümler tamamlanana kadar 2 ve 3. adımları tekrarlayın.

Python'da Dijkstra Algoritmasının Adım Adım Uygulanması

Şimdi, Dijkstra algoritmasını pekiştirmek için onu Python’da adım adım nasıl uygulayacağımızı öğreneceğiz.

Sözlükler olarak grafikleri anlamak

Öncelikle, grafikleri Python’da temsil etmenin bir yoluna ihtiyacımız var — en popüler seçenek sözlük (dictionary) kullanmaktır. Eğer grafiğimiz buysa:

Onu şu sözlükle temsil edebiliriz:

graph = {
   "A": {"B": 3, "C": 3},
   "B": {"A": 3, "D": 3.5, "E": 2.8},
   "C": {"A": 3, "E": 2.8, "F": 3.5},
   "D": {"B": 3.5, "E": 3.1, "G": 10},
   "E": {"B": 2.8, "C": 2.8, "D": 3.1, "G": 7},
   "F": {"G": 2.5, "C": 3.5},
   "G": {"F": 2.5, "E": 7, "D": 10},
}
Altyapı:

Sözlüğün her bir anahtarı bir düğümü, her bir değeri ise o anahtarın komşularını ve onlara olan mesafeleri içeren bir sözlüğü temsil eder. Grafiğimizde yedi düğüm vardır; bu da sözlüğün yedi anahtarı olması gerektiği anlamına gelir.

Diğer kaynaklar yukarıdaki sözlüğü sıklıkla komşuluk listesi sözlüğü olarak adlandırır. Biz de bundan sonra bu terimi kullanacağız.

1. Bir Graph sınıfı oluşturma

Kodumuzu daha modüler ve takip etmesi kolay hale getirmek için grafikleri temsil etmek üzere basit bir Graph sınıfı uygulayacağız. Alt yapıda bir komşuluk listesi sözlüğü kullanacak. Ayrıca iki düğüm arasında kolayca bağlantı eklemek için bir yöntemi olacak:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph  # A dictionary for the adjacency list

   def add_edge(self, node1, node2, weight):
       if node1 not in self.graph:  # Check if the node is already added
           self.graph[node1] = {}  # If not, create the node
       self.graph[node1][node2] = weight  # Else, add a connection to its neighbor
Altyapı:

Bu sınıfı kullanarak grafiğimizi sıfırdan yinelemeli olarak şu şekilde kurabiliriz:

G = Graph()

# Add A and its neighbors
G.add_edge("A", "B", 3)
G.add_edge("A", "C", 3)

# Add B and its neighbors
G.add_edge("B", "A", 3)
G.add_edge("B", "D", 3.5)
G.add_edge("B", "E", 2.8)

...
Altyapı:

Ya da doğrudan bir komşuluk listesi sözlüğü geçebiliriz ki bu daha hızlı bir yöntemdir:

# Use the dictionary we defined earlier
G = Graph(graph=graph)

G.graph
Altyapı:

{'A': {'B': 3, 'C': 3},
'B': {'A': 3, 'D': 3.5, 'E': 2.8},
'C': {'A': 3, 'E': 2.8, 'F': 3.5},
'D': {'B': 3.5, 'E': 3.1, 'G': 10},
'E': {'B': 2.8, 'C': 2.8, 'D': 3.1, 'G': 7},
'F': {'G': 2.5, 'C': 3.5},
'G': {'F': 2.5, 'E': 7, 'D': 10}}
Altyapı:

2. Kaynaktan olan mesafeleri depolamak için sözlük kullanma

Algoritmanın kendisi için — shortest_distances — bir sınıf yöntemi daha oluşturuyoruz:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   # The add_edge method omitted for space

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       ...
Altyapı:

Yöntemin içinde yaptığımız ilk şey, düğüm-değer çiftlerini içeren bir sözlük tanımlamaktır. Bu sözlük, her düğümü ve komşularını ziyaret ettiğimizde güncellenir. Algoritmanın görsel açıklamasında belirttiğimiz gibi, tüm düğümlerin başlangıç değerleri sonsuz, kaynağın değeri ise 0’dır.

Yöntemi yazmayı bitirdiğimizde, bu sözlük döndürülecek ve kaynaktan tüm düğümlere olan en kısa mesafeleri içerecek. B’den F’ye olan mesafeyi şöyle bulabileceğiz:

# Sneak-peek - find the shortest paths from B
distances = G.shortest_distances("B")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Altyapı:

3. Düğümler üzerinde yinelemek için öncelik kuyruğu kullanma

Şimdi, Dijkstra algoritmasının kurallarına göre grafik düğümleri üzerinde döngü kurmanın bir yoluna ihtiyacımız var. Hatırlarsanız, her yinelemede en küçük değere sahip düğümü seçip komşularını ziyaret etmemiz gerekiyor.

Basitçe sözlüğün anahtarları üzerinde dönebiliriz diyebilirsiniz:

for node in graph.keys():
   ...
Altyapı:

Bu yöntem işe yaramaz; çünkü düğümleri değerlerine göre sıralamamıza imkân tanımaz. Dolayısıyla, basit diziler yeterli olmayacaktır. Bu sorunu çözmek için öncelik kuyruğu denilen yapıyı kullanacağız.

Öncelik kuyruğu, normal bir listeye (diziye) benzer; ancak her öğesinin önceliğini temsil eden ekstra bir değeri vardır. İşte örnek bir öncelik kuyruğu:

pq = [(3, "A"), (1, "C"), (7, "D")]Altyapı:

Bu kuyrukta üç öğe vardır — A, C ve D — ve her biri, kuyruk üzerinde işlemlerin nasıl yapılacağını belirleyen bir öncelik değerine sahiptir. Python, öncelik kuyruklarıyla çalışmak için yerleşik heapq kütüphanesini sağlar:

from heapq import heapify, heappop, heappushAltyapı:

Bu kütüphanede bizim için önemli üç işlev vardır:

• heapify: Öncelik-değer çiftlerinden oluşan bir listeyi öncelik kuyruğuna dönüştürür.
• heappush: Kuyruğa, ilişkili önceliğiyle bir öğe ekler.
• heappop: En yüksek önceliğe sahip öğeyi (en küçük değere sahip öğe) kaldırır ve döndürür.

pq = [(3, "A"), (1, "C"), (7, "D")]

# Convert into a queue object
heapify(pq)

# Return the highest priority value
heappop(pq)
Altyapı:

(1, 'C')Altyapı:

Gördüğünüz gibi, pq’yu heapify ile bir kuyruğa dönüştürdükten sonra C’yi önceliğine göre çıkarabildik. Bir değer eklemeyi deneyelim:

heappush(pq, (0, "B"))

heappop(pq)
Altyapı:

(0, 'B')Altyapı:

Kuyruk, yeni öğenin önceliğine göre doğru şekilde güncellendi; çünkü heappop önceliği 0 olan yeni öğeyi döndürdü.

Bir öğeyi çıkardıktan sonra, artık kuyruğun parçası olmayacağını unutmayın.

Şimdi algoritmamıza geri dönersek, distances’ı başlattıktan sonra, başlangıçta yalnızca kaynak düğümü tutan yeni bir öncelik kuyruğu oluşturuyoruz:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()
Altyapı:

pq içindeki her öğenin önceliği, o öğenin mevcut değeri olacaktır. Ayrıca, ziyaret edilen düğümleri kaydetmek için boş bir küme başlatıyoruz.

4. while döngüsü olarak Dijkstra algoritması

Şimdi, tüm ziyaret edilmemiş düğümler üzerinde bir while döngüsü kullanarak yinelemeye başlıyoruz:

class Graph:
   def __init__(self, graph: dict = {}):
       self.graph = graph

   def shortest_distances(self, source: str):
       # Initialize the values of all nodes with infinity
       distances = {node: float("inf") for node in self.graph}
       distances[source] = 0  # Set the source value to 0

       # Initialize a priority queue
       pq = [(0, source)]
       heapify(pq)

       # Create a set to hold visited nodes
       visited = set()

       while pq:  # While the priority queue isn't empty
           current_distance, current_node = heappop(
               pq
           )  # Get the node with the min distance

           if current_node in visited:
               continue  # Skip already visited nodes
           visited.add(current_node)  # Else, add the node to visited set
Altyapı:

Öncelik kuyruğu boş olmadığı sürece, en yüksek önceliğe sahip (en küçük değere sahip) düğümü çıkarıp değerini ve adını current_distance ve current_node olarak alırız. current_node visited içinde ise atlarız. Aksi halde, onu ziyaret edildi olarak işaretler ve komşularını ziyaret etmeye geçeriz:

while pq:  # While the priority queue isn't empty
   current_distance, current_node = heappop(pq)

   if current_node in visited:
       continue 
   visited.add(current_node)

   for neighbor, weight in self.graph[current_node].items():
       # Calculate the distance from current_node to the neighbor
       tentative_distance = current_distance + weight
       if tentative_distance < distances[neighbor]:
           distances[neighbor] = tentative_distance
           heappush(pq, (tentative_distance, neighbor))

return distances
Altyapı:

Her komşu için, komşunun mevcut değerine bağlandığı kenarın ağırlığını ekleyerek geçici mesafeyi hesaplarız. Ardından, bu mesafenin distances içindeki komşunun mesafesinden küçük olup olmadığını kontrol ederiz. Küçükse, distances sözlüğünü günceller ve komşuyu geçici mesafesiyle öncelik kuyruğuna ekleriz.

İşte bu kadar! Dijkstra algoritmasını uyguladık. Hadi test edelim:

G = Graph(graph)

distances = G.shortest_distances("B")
print(distances, "\n")

to_F = distances["F"]
print(f"The shortest distance from B to F is {to_F}")
Altyapı:

{'A': 3, 'B': 0, 'C': 5.6, 'D': 3.5, 'E': 2.8, 'F': 9.1, 'G': 9.8}

The shortest distance from B to F is 9.1
Altyapı:

Yani, B’den F’ye olan mesafe 9,1. Ama durun: Hangi yol?

5. En kısa yolu oluşturma

Şu anda yalnızca en kısa mesafeler var, yollar yok; bu da grafiğimizi şu hale getiriyor:

Hesaplanan en kısa mesafeden en kısa yolu oluşturmak için hedeften geriye doğru iz sürebiliriz. F’ye bağlı her kenar için ağırlığını çıkarırız:

1. 9,1–3,5 = 5,6
2. 9,1–2,5 = 6,5

Sonra, sonuçlardan herhangi birinin F’nin komşularının değeriyle eşleşip eşleşmediğine bakarız. Yalnızca 5,6, C’nin değeriyle eşleşir; bu da C’nin en kısa yolun parçası olduğu anlamına gelir.

Bu işlemi C’nin komşuları A ve E için tekrarlarız:

1. 5,6–3 = 2,6
2. 5,6–2,8 = 2,8

2,8 E’nin değeriyle eşleştiğinden, E en kısa yolun parçasıdır. E aynı zamanda B’nin komşusudur; bu da B ile F arasındaki en kısa yolun — BECF — olduğunu gösterir.

Bu sürecin uygulamasını sınıfımıza ekleyelim. Kodun kendisi yukarıdaki açıklamadan biraz farklı; çünkü yalnızca F için değil, B ile tüm diğer düğümler arasındaki en kısa yolları buluyor.

Ayrıca, bunu ters yönde yapıyor; fakat fikir aynı.

Eski return ifadesini silerek aşağıdaki kod satırlarını shortest_distances yönteminin sonuna ekleyin:

predecessors = {node: None for node in self.graph}

for node, distance in distances.items():
   for neighbor, weight in self.graph[node].items():
       if distances[neighbor] == distance + weight:
           predecessors[neighbor] = node

return distances, predecessors
Altyapı:

Kod çalıştığında, predecessors sözlüğü, kaynağa giden en kısa yolda yer alan her düğümün bir önceki ebeveynini içerir. Deneyelim:

G = Graph(graph)

distances, predecessors = G.shortest_distances("B")

print(predecessors)
Altyapı:

{'A': 'B', 'B': None, 'C': 'E', 'D': 'B', 'E': 'B', 'F': 'C', 'G': 'E'}Altyapı:

Önce, predecessors sözlüğünü kullanarak F’den geriye iz sürüp en kısa yolu elle bulalım:

# Check the predecessor of F
predecessors["F"]
Altyapı:

'C'  # It is CAltyapı:

# Check the predecessor of C
predecessors["C"]
Altyapı:

'E'  # It is EAltyapı:

# Check the predecessor of E
predecessors["E"]
Altyapı:

'B'  # It is BAltyapı:

İşte bu! Sözlük, B ile F arasındaki en kısa yolun BECF olduğunu doğru şekilde söylüyor.

Fakat yöntemi yarı manuel bulduk. Herhangi bir kaynaktan herhangi bir hedefe, predecessors sözlüğünden oluşturulan en kısa yolu otomatik olarak döndüren bir yönteme ihtiyacımız var. Bu yöntemi shortest_path olarak tanımlıyoruz (sınıfın sonuna ekleyin):

def shortest_path(self, source: str, target: str):
   # Generate the predecessors dict
   _, predecessors = self.shortest_distances(source)

   path = []
   current_node = target

   # Backtrack from the target node using predecessors
   while current_node:
       path.append(current_node)
       current_node = predecessors[current_node]

   # Reverse the path and return it
   path.reverse()

   return path
Altyapı:

shortest_distances işlevini kullanarak predecessors sözlüğünü oluşturuyoruz. Ardından, her yinelemede geçerli düğümden bir önceki düğüme giderek kaynak düğüme ulaşana kadar devam eden bir while döngüsü başlatıyoruz. Sonra, kaynaktan hedefe olan yolu içeren listeyi ters çevirip döndürüyoruz.

Hadi test edelim:

G = Graph(graph)

G.shortest_path("B", "F")
Altyapı:

['B', 'E', 'C', 'F']Altyapı:

Çalışıyor! Bir tane daha deneyelim:

G.shortest_path("A", "G")Altyapı:

['A', 'C', 'F', 'G']Altyapı:

Tıkır tıkır.

Sonuç

Bu eğitimde grafik teorisinin en temel algoritmalarından birini — Dijkstra’yı — öğrendik. Grafik benzeri yapılarda iki nokta arasındaki en kısa yolu bulmak için sıklıkla başvurulan algoritmadır. Basitliği sayesinde şu gibi birçok sektörde uygulamaları vardır:

• Lojistik ve taşımacılık
• Ağ ve telekomünikasyon
• Üretim ve robotik
• Finans ve yatırım
• Kentsel planlama

Dijkstra algoritmasını Python’da uygulamanın, grafik algoritmalarının harika dünyasına ilginizi artırdığını umuyorum. Daha fazlasını öğrenmek isterseniz, aşağıdaki kaynakları şiddetle öneririm:

• Python ile Ağ Analizine Giriş Kursu
• Python'da Veri Yapıları ve Algoritmalar Kursu