Özet - Bellman-Ford
- Algoritmalar kursu
- İleri seviye
- Ders 36/56
- 4 dk
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.
Başlangıç kodu
def has_negative_cycle(edges, n, src):
# Negatif döngü var mı denetleÖrnek çözüm
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))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Bellman-Ford'un çıktısı ne zaman geçerlidir?
- Negatif kenar yoksa
- Graf yönsüzse
- Tüm kenarlar pozitifse
- Negatif döngü yoksa Doğru cevap
Açıklama: Negatif döngü yoksa çıktı geçerlidir.
2 negatif döngü koşulu
Soru
if dist[u] + w ____ dist[v]: return True
Cevap
if dist[u] + w < dist[v]: return TrueAçıklama: < doğru.
3 Özet - Bellman-Ford: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
init_edges |
Kenar |
relax |
Gevşetme |
bellman_ford |
Algoritma |
n-1 |
Geçiş |