Tüm çiftler

Tüm düğüm çiftleri arasındaki en kısa yolu bulan algoritmayı öğrenirsin.

Tüm çiftler

Floyd-Warshall algoritması, bir graftaki tüm düğüm çiftleri arasındaki en kısa yolları tek seferde bulur. Çıktı, bir mesafe matrisidir.

Tek kaynak değil, tüm çiftler için sonuç verir. Bu özellik, yoğun graf sorunlarında faydalıdır.

Mesafe matrisi

Graf, bir n×n komşuluk matrisi olarak temsil edilir. graph[i][j], i'den j'ye doğrudan kenar ağırlığıdır; kenar yoksa 999 (sonsuz) yazılır.

Köşegen sıfırdır: graph[i][i] = 0. Matris üzerinde üçlü döngü çalıştırılarak en kısa yollar hesaplanır.

Uygulama init_graph fonksiyonu

init_graph() yaz. 4×4 komşuluk matrisini döndür. print(init_graph()) ile 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]]
print(init_graph())

Kendini test et

Floyd-Warshall kaç düğüm çiftini çözer?
- Tüm çiftler
- Tek kaynak
- Yalnız bir çift
- Yalnız komşular
Cevabı göster

Tüm çiftler — Floyd-Warshall tüm çiftleri çözer.

sonsuz değer

graph[i][j] = ____ (kenar yoksa)

Cevabı göster

graph[i][j] = 999 (kenar yoksa)

Tüm çiftler: kavramları eşleştir

graph[i][i]

0
graph[i][j]

Kenar
999

Sonsuz
n×n

Boyut

Sıradaki ders: Üçlü döngü

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler