Negatif ağırlık

Bellman-Ford'un negatif ağırlıklarla çalıştığını öğrenirsin.

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.

init_edges() yaz. Kenar listesini döndür. print(init_edges()) ile 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)]
print(init_edges())

kenar tanımı

edges = [(0, 1, ____)]

Cevabı göster

edges = [(0, 1, 4)]