Dijkstra algoritması nasıl çalışır? Ağırlıklı grafikte en kısa yolu bulun.

Dijkstra, negatif olmayan ağırlıklı bir grafikte bir kaynaktan tüm düğümlere en kısa mesafeyi bulur. Açgözlü (greedy) bir algoritmadır: her adımda kesinleşmemiş düğümler arasında mesafesi en küçük olanı seçer ve komşularını gevşetir (relax).

Adımlar

1. Kaynağın mesafesi 0, diğerleri sonsuz.
2. Min-heap'e (0, kaynak) eklenir.
3. Heap'ten en küçük mesafeli düğüm çıkarılır; eski (güncel olmayan) kayıtsa atlanır.
4. Her komşu için dist[u] + w < dist[v] ise dist[v] güncellenir ve heap'e eklenir.
5. Heap boşalana kadar devam edilir.

import heapq

def dijkstra(graph, src):
    # graph: {düğüm: [(komşu, ağırlık), ...]}
    dist = {node: float("inf") for node in graph}
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                 # eski kayıt
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

g = {"A": [("B", 4), ("C", 1)], "C": [("B", 2), ("D", 5)],
     "B": [("D", 1)], "D": []}
dijkstra(g, "A")  # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

Yolun kendisi isteniyorsa her düğüm için prev[v] = u tutulur ve hedeften geriye gidilir.

Karmaşıklık

• Binary heap ile `O((V + E) log V)`, bellek O(V + E).

Ne zaman başka algoritma?

Negatif kenarda Dijkstra yanlış sonuç verir, çünkü kesinleşmiş bir düğüme sonradan daha kısa yol bulunabilir.