Tüm çiftler
- Algoritmalar kursu
- İleri seviye
- Ders 25/56
- 4 dk
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.
Başlangıç kodu
def init_graph():
# Komşuluk matrisini döndürÖ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]]
print(init_graph())Beklenen çıktı
[[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Floyd-Warshall kaç düğüm çiftini çözer?
- Tüm çiftler Doğru cevap
- Tek kaynak
- Yalnız bir çift
- Yalnız komşular
Açıklama: Floyd-Warshall tüm çiftleri çözer.
2 sonsuz değer
graph[i][j] = ____ (kenar yoksa)graph[i][j] = 999 (kenar yoksa)Açıklama: 999 doğru.
3 Tüm çiftler: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
graph[i][i] |
0 |
graph[i][j] |
Kenar |
999 |
Sonsuz |
n×n |
Boyut |