Negatif ağırlık
- Algoritmalar kursu
- İleri seviye
- Ders 33/56
- 4 dk
Bellman-Ford'un negatif ağırlıklarla çalıştığını öğrenirsin.
Negatif ağırlık
Bellman-Ford algoritması, negatif ağırlıklı kenarları destekleyen tek kaynak en kısa yol algoritmasıdır. Dijkstra'nın yapamadığını yapar.
Algoritma tüm kenarları n-1 kez gevşetir. Bu, en uzun yolun n-1 kenardan fazla olamayacağı gerçeğine dayanır.
Kenar listesi
Bellman-Ford graftan ziyade kenar listesiyle çalışır. Her kenar (u, v, w) üçlüsüdür: u'dan v'ye, w ağırlığıyla.
Bu gösterim, algoritmanın tüm kenarları tek tek dolaşmasını sağlar. Karmaşıklık O(n·m)'dir; m kenar sayısıdır.
Uygulama init_edges fonksiyonu
init_edges() yaz. Kenar listesini döndür. print(init_edges()) ile yazdır.
Başlangıç kodu
def init_edges():
# Kenar listesini döndürÖ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)]
print(init_edges())Beklenen çıktı
[(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Bellman-Ford'un Dijkstra'ya üstünlüğü nedir?
- Negatif ağırlıkları destekler Doğru cevap
- Daha az bellek kullanır
- Daha hızlı çalışır
- Tüm çiftleri çözer
Açıklama: Bellman-Ford negatif ağırlıkları destekler.
2 kenar tanımı
edges = [(0, 1, ____)]edges = [(0, 1, 4)]Açıklama: 4 doğru.
3 Negatif ağırlık: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
(0,1,4) |
0→1 |
(0,2,1) |
0→2 |
(2,1,2) |
2→1 |
(1,3,1) |
1→3 |