Negatif döngü

Negatif döngü tespitini öğrenirsin.

Negatif döngü

n-1 geçişten sonra bir geçiş daha yapılır. Hala gevşeyebilen bir kenar varsa grafın negatif döngüsü vardır ve en kısa yol tanımsızdır.

Bu denetim, algoritmanın güvenli kullanımını sağlar. Negatif döngü varsa kullanıcı uyarılır.

Çözümün son hali

n-1 geçişten sonra dist dizisi tek kaynak en kısa mesafeleri içerir. Negatif döngü yoksa bu değerler kesindir.

Çıktı, Dijkstra'nın çıktısıyla aynı biçimdedir: bir mesafe dizisi. Fark, negatif kenarları da içermesidir.

Uygulama bellman_ford fonksiyonu

bellman_ford(edges, n, src) yaz. n-1 kez tüm kenarları gevşet. print(bellman_ford(init_edges(), 4, 0)) ile [0, 3, 1, 4] yazdır.

Örnek çözümü göster

def init_edges():
    # Kenar listesini döndür
    return [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
def bellman_ford(edges, n, src):
    # Tek kaynak en kısa yolları bul
    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
    return dist
print(bellman_ford(init_edges(), 4, 0))

Kendini test et

Negatif döngü: kavramları eşleştir

n-1

Geçiş
1

Kontrol geçişi
negatif döngü

Tanımsız
gevşeme

Güncelleme
0'dan 3'e en kısa mesafe nedir?
- 3
- 5
- 4
- 1
Cevabı göster

4 — 0→2→1→3 yolu 1+2+1=4 verir.

döngü değişkeni

for u, v, w in ____:

Cevabı göster

for u, v, w in edges:

Sıradaki ders: Özet - Bellman-Ford

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler