Dijkstra Algoritması

#Nasıl çalışır?

Dijkstra algoritması (Edsger Dijkstra, 1956), kenarları negatif olmayan ağırlıklara sahip bir grafta, bir başlangıç düğümünden diğer tüm düğümlere en kısa (en ucuz) yolları bulur.

BFS kenar sayısını en aza indirir; ama kenarların uzunlukları, süreleri ya da maliyetleri farklıysa en az kenarlı yol en ucuz yol olmayabilir. Örnek grafta BFS'in bulduğu 1 → 2 → 4 → 7 yolu 12'ye, Dijkstra'nın bulduğu 1 → 3 → 6 → 7 yolu 6'ya mal oluyor.

Algoritma açgözlüdür (greedy): her adımda henüz kesinleşmemiş düğümler içinde mesafesi en küçük olanı seçer ve kesinleştirir. Ağırlıklar negatif olmadığı için o düğüme daha sonra daha kısa bir yoldan ulaşmak imkânsızdır.

Kesinleşen düğümün komşuları "gevşetilir" (relaxation): dist[u] + w, dist[v]'den küçükse dist[v] güncellenir ve prev[v] = u yazılır. En küçük mesafeli düğümü hızlıca bulmak için öncelik kuyruğu (min-heap) kullanılır.

#Kendin dene

#Adım adım

1. 01dist[başlangıç] = 0, diğer tüm mesafeler ∞; başlangıcı öncelik kuyruğuna koy.
2. 02Kuyruktan mesafesi en küçük düğümü (u) al ve kesinleştir.
3. 03u'nun kesinleşmemiş her komşusu v için: dist[u] + w(u, v) < dist[v] ise dist[v]'yi güncelle, prev[v] = u yaz ve v'yi kuyruğa ekle.
4. 04Kuyruk boşalana (ya da hedef kesinleşene) kadar tekrarla; yolu prev[] zincirini hedeften geriye izleyerek çıkar.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

import heapq

# Undirected weighted graph: graph[u] = [(v, weight), ...]
EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
graph = {v: [] for v in range(1, 8)}
for a, b, w in EDGES:
    graph[a].append((b, w))
    graph[b].append((a, w))


def dijkstra(start: int):
    dist = {v: float("inf") for v in graph}
    prev = {}
    dist[start] = 0
    heap = [(0, start)]  # (distance, node), smallest first
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # an outdated entry: u was already settled with a smaller distance
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev


dist, prev = dijkstra(1)
print(" ".join(str(dist[v]) for v in range(1, 8)))  # distance from 1 to nodes 1..7

path = [7]
while path[-1] != 1:
    path.append(prev[path[-1]])
print(" ".join(map(str, reversed(path))))  # cheapest path, not the fewest edges (1 2 4 7)
print(dist[7])

#Karmaşıklık

Her kenar en fazla bir kez gevşetilir ve her gevşetme heap'e O(log V) maliyetle bir ekleme yapabilir. Yoğun graflarda (E ≈ V²) basit dizi sürümü daha hızlı olabilir. Negatif ağırlıklı kenar varsa Dijkstra yanlış sonuç verir; o zaman Bellman-Ford kullanılır.

#Ne zaman kullanılır?

Harita ve navigasyon uygulamalarında rota bulma, ağ yönlendirme protokolleri (OSPF), oyunlarda yol bulma (A* algoritması Dijkstra'nın sezgisel bir uzantısıdır), uçuş ve toplu taşıma planlaması gibi tüm "en ucuz/en hızlı rota" problemleri Dijkstra ile çözülür.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Bellman-Ford Algoritması
• Floyd-Warshall Algoritması
• Prim Algoritması