Özet - Floyd-Warshall

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.

Örnek çözümü göster

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))

Kendini test et

Floyd-Warshall'ın çıktısı nedir?
- Tek bir mesafe
- Kenar ağırlıkları
- Bir yol listesi
- Tüm çiftler mesafe matrisi
Cevabı göster

Tüm çiftler mesafe matrisi — Çıktı tüm çiftler için mesafe matrisidir.

matris kopyalama

dist = [row[:] for row in ____]

Cevabı göster

dist = [row[:] for row in graph]

Özet - Floyd-Warshall: kavramları eşleştir

init_graph

Graf
relax_edge

Gevşetme
floyd_warshall

Üçlü döngü
dist

Mesafe

Sıradaki ders: Tek kaynak

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler