Floyd-Warshall Algoritması

#Nasıl çalışır?

Floyd-Warshall algoritması tek bir başlangıçtan değil, tüm düğüm çiftleri arasındaki en kısa yolları hesaplar. Sonuç V × V boyutlu bir mesafe matrisidir: dist[i][j], i'den j'ye en kısa yolun maliyetidir.

Fikir dinamik programlamadır: düğümleri sırayla "ara durak" olarak izin verir. k. turda, i'den j'ye yalnızca ilk k düğümü ara durak olarak kullanan en iyi yol bilinir; yeni soru şudur: k üzerinden gitmek, yani dist[i][k] + dist[k][j], mevcut dist[i][j]'den kısa mı?

Kodu üç iç içe döngüden ibarettir ve negatif kenarlarla da çalışır (negatif döngü yoksa). Köşegende negatif bir değer belirirse grafta negatif döngü vardır.

#Kendin dene

#Adım adım

1. 01Matrisi doğrudan kenar ağırlıklarıyla doldur: köşegen 0, kenar olmayan çiftler ∞.
2. 02Her k düğümü için (en dıştaki döngü):
3. 03 her i, j çifti için dist[i][k] + dist[k][j] < dist[i][j] ise dist[i][j]'yi güncelle.
4. 04Yolları geri kurmak için next[i][j] (ilk durak) tablosu tutulabilir.

#Örnek kod

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

INF = float("inf")

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)]
N = 7

# dist[i][j] starts as the direct edge weight: 0 on the diagonal, INF where there is no edge.
dist = [[0 if i == j else INF for j in range(N)] for i in range(N)]
for a, b, w in EDGES:
    dist[a - 1][b - 1] = dist[b - 1][a - 1] = w  # undirected

for k in range(N):  # k must be the outermost loop
    for i in range(N):
        for j in range(N):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

for row in dist:
    print(" ".join(map(str, row)))

#Karmaşıklık

Kenar sayısından bağımsız olarak V³ adım sürer. Yoğun ve küçük graflarda (birkaç yüz düğüm) çok pratiktir. Seyrek ve büyük graflarda her düğümden Dijkstra çalıştırmak (O(V · E log V)) daha hızlıdır. k döngüsünün en dışta olması şarttır; sıralama değişirse sonuç yanlış olur.

#Ne zaman kullanılır?

Tüm çiftler arasındaki mesafelerin gerektiği durumlar: şehirler arası mesafe tabloları, ağdaki her cihaz çifti için gecikme, bir grafın geçişli kapanışı (kim kime ulaşabilir) ve oyun haritalarında önceden hesaplanmış yol tabloları.

#Alıştırma

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