Tablo güncelleme
- Algoritmalar kursu
- İleri seviye
- Ders 27/56
- 4 dk
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.
Başlangıç kodu
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Örnek çözüm
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()))Beklenen çıktı
[[0, 3, 4, 6], [999, 0, 1, 3], [999, 6, 0, 2], [999, 4, 5, 0]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Tablo güncelleme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dist[i][j] |
Mevcut |
dist[i][k] |
i→k |
dist[k][j] |
k→j |
min |
En küçük |
2 0'dan 3'e en kısa mesafe nedir?
- 7
- 4
- 6 Doğru cevap
- 999
Açıklama: 0→1→2→3 yolu 3+1+2=6 verir.
3 iç güncelleme
dist[i][j] = ____(dist[i][j], dist[i][k] + dist[k][j])dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Açıklama: min doğru.