Üçlü döngü

k, i, j iç içe döngüleriyle tabloyu güncellemeyi öğrenirsin.

Üçlü döngü

Algoritma üç iç içe döngü çalıştırır: dış döngü k ara düğümü, içteki iki döngü i ve j'yi dolaşır. Karmaşıklık O(n³)'tir.

Her k için tüm (i, j) çiftleri denenecek şekilde matris güncellenir. Bu yapı, tüm çiftlerin gevşetilmesini sağlar.

Ara düğüm

k, i'den j'ye giderken ara durak olarak kullanılan düğümdür. i → k → j yolu, doğrudan i → j yolundan daha kısaysa mesafe güncellenir.

Bu, tüm olası ara düğümleri deneyerek en kısa yolu bulur. Algoritma, her k için tabloyu bir kez günceller.

Uygulama relax_edge fonksiyonu

relax_edge(dist, i, j, k) yaz. min(dist[i][j], dist[i][k] + dist[k][j]) döndür. print(relax_edge(init_graph(), 0, 2, 1)) ile 4 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]]
def relax_edge(dist, i, j, k):
    # Tek bir gevşetme yap
    return min(dist[i][j], dist[i][k] + dist[k][j])
print(relax_edge(init_graph(), 0, 2, 1))

Kendini test et

dış döngü değişkeni
```
for ____ in range(n):
```
Cevabı göster
```
for k in range(n):
```
Üçlü döngünün karmaşıklığı nedir?
- O(n²)
- O(n³)
- O(n log n)
- O(n)
Cevabı göster

O(n³) — Üç iç içe döngü O(n³) verir.
Üçlü döngü: kavramları eşleştir

k

Ara düğüm
i

Başlangıç
j

Bitiş
n

Düğüm sayısı

Sıradaki ders: Tablo güncelleme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler