Tablo güncelleme

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) formülünü öğrenirsin.

Tablo güncelleme

Her k adımında tüm (i, j) çiftleri gezilir ve dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) formülü uygulanır.

Bu işlem, k'yı ara durak olarak kullanan daha kısa yollar bulunursa mesafeyi günceller. Tüm k değerleri bitince matris tamamlanır.

Algoritma sonu

Tüm k değerleri işlendiğinde dist matrisi tüm çiftlerin en kısa mesafelerini içerir. Daha fazla güncelleme olmaz.

Sonuç matrisi, orijinal grafın tüm çiftler için çözülmüş halidir. Tek bir sorgu için bile tüm matris hesaplanır.

Uygulama floyd_warshall fonksiyonu

floyd_warshall(graph) yaz. Üçlü döngü ile dist matrisini güncelle, döndür. print(floyd_warshall(init_graph())) ile son matrisi yazdır.

Örnek çözümü göster

def init_graph():
    # Komşuluk matrisini döndür
    return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
def floyd_warshall(graph):
    # Tüm çiftlerin en kısa yolunu bul
    n = len(graph)
    dist = [row[:] for row in graph]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
print(floyd_warshall(init_graph()))

Kendini test et

Tablo güncelleme: kavramları eşleştir

dist[i][j]

Mevcut
dist[i][k]

i→k
dist[k][j]

k→j
min

En küçük
0'dan 3'e en kısa mesafe nedir?
- 7
- 4
- 6
- 999
Cevabı göster

6 — 0→1→2→3 yolu 3+1+2=6 verir.

iç güncelleme

dist[i][j] = ____(dist[i][j], dist[i][k] + dist[k][j])

Cevabı göster

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Sıradaki ders: Özet - Floyd-Warshall

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler