Özet - Bellman-Ford

Bellman-Ford uygulayıp mesafeleri yazdıran mini görev yaparsın.

Özet - Bellman-Ford

Bu grupta negatif ağırlıkları destekleyen Bellman-Ford algoritmasını öğrendin. Kenar listesi, kenar döngüsü ve negatif döngü denetimi birleşince çözüm oluşur.

Şimdi tüm parçaları bir araya getiren bir denetim fonksiyonu yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.

Uygulama has_negative_cycle fonksiyonu

has_negative_cycle(edges, n, src) yaz. Bellman-Ford çalıştır, bir ek geçişte hala gevşeyen kenar varsa True döndür. print(has_negative_cycle([(0, 1, 1), (1, 2, -1), (2, 0, -1)], 3, 0)) ile True yazdır.

Örnek çözümü göster

def has_negative_cycle(edges, n, src):
    # Negatif döngü var mı denetle
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True
    return False
print(has_negative_cycle([(0, 1, 1), (1, 2, -1), (2, 0, -1)], 3, 0))

Kendini test et

Bellman-Ford'un çıktısı ne zaman geçerlidir?
- Negatif kenar yoksa
- Graf yönsüzse
- Tüm kenarlar pozitifse
- Negatif döngü yoksa
Cevabı göster

Negatif döngü yoksa — Negatif döngü yoksa çıktı geçerlidir.

negatif döngü koşulu

if dist[u] + w ____ dist[v]: return True

Cevabı göster

if dist[u] + w < dist[v]: return True

Özet - Bellman-Ford: kavramları eşleştir

init_edges

Kenar
relax

Gevşetme
bellman_ford

Algoritma
n-1

Geçiş

Sıradaki ders: Minimum çevreli ağaç

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler