Negatif döngü
- Algoritmalar kursu
- İleri seviye
- Ders 35/56
- 4 dk
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.
Başlangıç kodu
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Örnek çözüm
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))Beklenen çıktı
[0, 3, 1, 4]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Negatif döngü: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
n-1 |
Geçiş |
1 |
Kontrol geçişi |
negatif döngü |
Tanımsız |
gevşeme |
Güncelleme |
2 0'dan 3'e en kısa mesafe nedir?
- 3
- 5
- 4 Doğru cevap
- 1
Açıklama: 0→2→1→3 yolu 1+2+1=4 verir.
3 döngü değişkeni
for u, v, w in ____:for u, v, w in edges:Açıklama: edges doğru.