Dijkstra, 0–1 BFS ve A*

Dijkstra nonnegative kenarlarda en küçük geçici distance'ı kesinleştirir. Relaxation d[v]>d[u]+w ise iyileştirme yapar. Negatif kenar, kesinleşmiş düğümün daha sonra ucuzlamasına yol açabilir ve ispatı bozar. “Bütün cycle'+'’lar pozitif” varsayımı tek başına yeterli değildir.

Heap uygulamasında bir düğüme yeni distance yazınca yeni entry ekle; eski entry çekilince d!=dist[u] ise atla. İlk enqueue'da visited yapma; Dijkstra'da bir düğümün ilk görülen yolu en iyi olmayabilir. Hedefi erken durdurma ancak geçerli minimum entry extract edildiğinde uygundur.

0/1 ağırlıkta deque ile0–1 BFS O(V+E) çalışır. A* f=g+h kullanır; admissible heuristic hedef maliyetini aşmaz. Graph search'te consistency, kapatılmış düğümü yeniden açmadan optimalite için önemlidir; inconsistent heuristic uygun reopening ister. A*, Dijkstra'+'’nın h=0 özel durumunu geneller; gerçek navigasyon ürünleri çok daha fazla preprocessing ve trafik modeli kullanır.

Relaxation neden güvenilir?

s→a=4, s→b=1, b→a=2 olsun. Önce tentative a=4, b=1. Heap b'yi çıkarır ve a'yı 3'e indirir. Daha sonra a=3 finalize edilir. Heap'te kalan a=4 eski kayıttır; distance != best[node] kontrolüyle atlanır. Parent da başarılı relaxation'da güncellenir; distance tek başına path'i vermez.

Dijkstra'nın temel kanıtı nonnegative edge varsayımına bağlıdır. Minimum tentative node'u finalize ederken henüz seçilmemiş bir node üzerinden daha ucuz yol gelemez; çünkü o yolun prefix'i zaten en az bu tentative değere sahiptir ve kalan ağırlıklar negatif değildir. Negatif kenar bu çıkarımı bozar. Negatif edge var ama negative cycle yoksa Bellman-Ford veya uygun Johnson reweighting düşünülebilir.

A* priority f=g+h kullanır. Admissible heuristic kalan gerçek maliyeti aşmaz; consistent heuristic h(u)≤w(u,v)+h(v) koşulunu sağlar. Closed node'ları yeniden açmayan graph-search uygulamasında consistency önemli olabilir. h=0 Dijkstra'ya döner. Haritadaki düz çizgi mesafesi yalnız cost modeli uygunken lower bound'dur; zaman veya ücret metriğinde gelişigüzel kullanılamaz.

Temel: Yukarıdaki stale heap kaydını elle izle. Orta: Zero-weight ve unreachable testlerini ekle. İleri: Inconsistent ama admissible heuristic ile reopen ihtiyacını göster; expanded-node sayısını ve doğru distance'ı ayrı ölç.

import heapq

def dijkstra(g, start):
    if any(w < 0 for edges in g.values() for _,w in edges):
        raise ValueError("negative edge")
    dist = {u: float("inf") for u in g}; dist[start] = 0
    q = [(0,start)]
    while q:
        d,u = heapq.heappop(q)
        if d != dist[u]: continue
        for v,w in g[u]:
            if d+w < dist[v]:
                dist[v] = d+w; heapq.heappush(q,(dist[v],v))
    return dist
assert dijkstra({"A":[("B",10),("C",1)],"B":[],"C":[("B",2)]},"A")["B"] == 3