Öncelikli kuyruk

Dijkstra'nın öncelikli kuyrukla verimli çalıştığını öğrenirsin.

Dijkstra, her adımda en küçük mesafeye sahip ziyaret edilmemiş düğümü seçer. Bu seçim, öncelikli kuyrukla hızlanır.

Basit uygulamada doğrusal arama da yeterlidir: tüm ziyaret edilmemiş düğüümü tarayıp en küçük dist'i buluruz.

Başlangıç durumu

Tüm düğümlerin mesafesi inf olarak başlatılır, yalnızca dist[src] = 0 olur. Ziyaret dizisi False ile dolar.

Bu başlangıç durumu, algoritmanın tek kaynaktan adım adım yayılmasını sağlar.

init_dist(n, src) yaz. float('inf') ile dolu dizi döndür, dist[src] = 0 yap. print(init_dist(4, 0)) ile yazdır.

Örnek çözümü göster

def init_dist(n, src):
    # Başlangıç mesafe dizisini döndür
    dist = [float('inf')] * n
    dist[src] = 0
    return dist
print(init_dist(4, 0))

Sıradaki ders: Gevşetme