Kenar döngüsü

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.

Örnek çözümü göster

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

Kendini test et

dış döngü sayısı

for _ in range(n - ____):

Cevabı göster

for _ in range(n - 1):

n=4 için dış döngü kaç kez döner?
- 4
- 3
- 5
- 1
Cevabı göster

3 — n-1 = 4-1 = 3 kez döner.
Kenar döngüsü: kavramları eşleştir

n-1

Geçiş sayısı
m

Kenar sayısı
dist[u]

Kaynak
dist[v]

Hedef

Sıradaki ders: Negatif döngü

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler