Özet - Floyd-Warshall
- Algoritmalar kursu
- İleri seviye
- Ders 28/56
- 4 dk
Küçük bir graph'ta Floyd-Warshall uygulayan mini görev yaparsın.
Özet - Floyd-Warshall
Bu grupta tüm çiftler için en kısa yolu bulan Floyd-Warshall algoritmasını öğrendin. Komşuluk matrisi, üçlü döngü ve gevşetme formülü birleşince çözüm oluşur.
Şimdi tüm parçaları bir araya getiren bir sorgu fonksiyonu yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.
Uygulama shortest_distance fonksiyonu
shortest_distance(graph, src, dst) yaz. Floyd-Warshall çalıştır, dist[src][dst]'yi döndür. print(shortest_distance(init_graph(), 0, 3)) ile 6 yazdır.
Başlangıç kodu
def shortest_distance(graph, src, dst):
# Tüm çiftleri çöz ve src→dst döndürÖrnek çözüm
def shortest_distance(graph, src, dst):
# Tüm çiftleri çöz ve src→dst döndür
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[src][dst]
print(shortest_distance(init_graph(), 0, 3))Beklenen çıktı
6
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Floyd-Warshall'ın çıktısı nedir?
- Tek bir mesafe
- Kenar ağırlıkları
- Bir yol listesi
- Tüm çiftler mesafe matrisi Doğru cevap
Açıklama: Çıktı tüm çiftler için mesafe matrisidir.
2 matris kopyalama
Soru
dist = [row[:] for row in ____]
Cevap
dist = [row[:] for row in graph]Açıklama: graph doğru.
3 Özet - Floyd-Warshall: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
init_graph |
Graf |
relax_edge |
Gevşetme |
floyd_warshall |
Üçlü döngü |
dist |
Mesafe |