Kenar döngüsü
- Algoritmalar kursu
- İleri seviye
- Ders 34/56
- 4 dk
Tüm kenarları V-1 kez gevşetmeyi öğrenirsin.
Kenar döngüsü
Bellman-Ford, tüm kenarları n-1 kez dolaşır. Her geçişte her kenar bir kez gevşetilir. Toplam (n-1)·m gevşetme yapılır.
Her geçiş, en az bir kenar uzunluğundaki yolları kapsar. n-1 geçiş, en uzun olası yolu garanti eder.
Gevşetme adımı
Her kenar için: if dist[u] + w < dist[v]: dist[v] = dist[u] + w. Eğer u üzerinden v'ye daha kısa yol varsa güncellenir.
Bu basit denetim, tüm algoritmanın özüdür. Kenar sayısı kadar tekrar edilir.
Uygulama relax fonksiyonu
relax(dist, u, v, w) yaz. dist[u] + w < dist[v] ise dist[v]'yi güncelle. print(dist[1]) ile 4 yazdır.
Başlangıç kodu
dist = [0, float('inf'), float('inf'), float('inf')]
def relax(dist, u, v, w):
# Tek kenarı gevşetÖrnek çözüm
dist = [0, float('inf'), float('inf'), float('inf')]
def relax(dist, u, v, w):
# Tek kenarı gevşet
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
relax(dist, 0, 1, 4)
print(dist[1])Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 dış döngü sayısı
Soru
for _ in range(n - ____):
Cevap
for _ in range(n - 1):Açıklama: 1 doğru.
2 n=4 için dış döngü kaç kez döner?
- 4
- 3 Doğru cevap
- 5
- 1
Açıklama: n-1 = 4-1 = 3 kez döner.
3 Kenar döngüsü: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
n-1 |
Geçiş sayısı |
m |
Kenar sayısı |
dist[u] |
Kaynak |
dist[v] |
Hedef |