Coding Interview Prep · Ders

Bellman-Ford ve Negatif Çevrimler

Q: “Bellman-Ford ve Negatif Çevrimler” dersi ücretsiz mi?

Evet — “Bellman-Ford ve Negatif Çevrimler” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Q: Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.

Q: “Bellman-Ford ve Negatif Çevrimler” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Tüm kenarlar üzerinde n-1 gevşetme geçişi yapın, son bir geçişle negatif çevrimleri belirleyin ve negatif ağırlıklı kenarlarda Dijkstra’nın neden başarısız olduğunu açıklayın.

Bellman-Ford ve Negatif Çevrimler, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Bellman-Ford Neden Gerekli

Bellman-Ford, Dijkstra gibi tek kaynaklı en kısa yol problemini çözer; ancak negatif kenar ağırlıklarını da ele alır. Ayrıca negatif çevrimleri algılar: toplam ağırlığı negatif olan bu çevrimler, içlerinden geçen sonlu bir en kısa yol tanımlamayı imkânsız kılar. Dijkstra'dan daha yavaş olsa da graf negatif ağırlıklı kenarlar içerebiliyorsa doğru seçim Bellman-Ford'dur.

Gevşetme: Temel İşlem

Bellman-Ford tek bir işleme dayanır: gevşetme. (u, v, w) kenarını gevşetmek şu anlama gelir: dist[u] + w < dist[v] ise dist[v] = dist[u] + w değerini atayın. Tüm kenarları tekrar tekrar gevşetiriz. Temel fikir şudur: negatif çevrim içermeyen bir grafta her en kısa yol en fazla V-1 kenara sahiptir. Bu nedenle, tüm kenarlar üzerinde V-1 gevşetme turu yapmak bütün en kısa yolları bulmak için yeterlidir.

Bellman-Ford Uygulaması

Grafı bir kenar listesi olarak [(u, v, weight)] gösterin. dist[source] = 0 değerini başlatın ve diğer tüm değerleri inf yapın. V-1 tur çalıştırıp her turda tüm kenarları gevşetin. V. turda hâlâ gerçekleşen herhangi bir güncelleme, negatif bir çevrime işaret eder.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

V-1 Tur Neden Yeterlidir

Negatif çevrim içermeyen bir graftaki en kısa yol her düğümü en fazla bir kez ziyaret eder; dolayısıyla en fazla V-1 kenara sahiptir. 1. turdan sonra en kısa 1 atlamalı yollar en iyi duruma gelir. 2. turdan sonra en kısa 2 atlamalı yollar en iyi duruma gelir. V-1 turdan sonra, en fazla V-1 atlama kullanan tüm en kısa yollar bulunmuş olur. V. tur hâlâ bir uzaklığı güncelliyorsa graf, kaynaktan erişilebilen bir negatif çevrim içerir.

Negatif Çevrim Algılama

V-1 turdan sonra tüm kenarlar üzerinde bir ek tur çalıştırın. (u, v, w) kenarlarından herhangi biri dist[u] + w < dist[v] koşulunu sağlıyorsa negatif bir çevrim vardır ve bazı düğümlere giden en kısa yol -infinity değerindedir. Gerçek dünya uygulamaları arasında döviz değişiminde arbitraj fırsatlarını algılama (log ağırlıklı graflardaki negatif çevrimler) ve kısıt sistemlerindeki tutarsızlıkları algılama bulunur.

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

Dijkstra ve Bellman-Ford Karşılaştırması

Dijkstra: O((V+E) log V), negatif olmayan ağırlıklar gerektirir, açgözlü yaklaşım kullanır. Bellman-Ford: O(V × E), negatif ağırlıkları ele alır ve negatif çevrimleri algılar. Negatif olmayan ağırlıklara sahip çoğu mülakat probleminde Dijkstra tercih edilir. Negatif ağırlıklar ortaya çıktığında (örneğin "negatif maliyetli kenarlarla en kısa yolu bulma" veya "arbitrajı algılama"), yanıt Bellman-Ford'dur. Yoğun graflarda Bellman-Ford'un en kötü durumdaki O(V³) karmaşıklığı, Floyd-Warshall ile karşılaştırılabilir.

Uygulama: Bellman-Ford ile En Ucuz Uçuşlar

K Durak İçindeki En Ucuz Uçuşlar (LeetCode 787), değiştirilmiş bir Bellman-Ford ile çözülebilir: tam olarak k+1 gevşetme turu çalıştırın (k durak, k+1 kenar anlamına gelir). Tek bir turda izin verilenden fazla atlama kullanmadığımızdan emin olmak için önceki turdaki uzaklıkların bir kopyasını kullanın; aksi takdirde tek bir turda birden fazla atlama zincirlenebilir.

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA: Kuyruk Tabanlı Optimizasyon

Shortest Path Faster Algorithm (SPFA), yalnızca uzaklığı az önce güncellenen düğümlerden çıkan kenarları bir kuyruk kullanarak yeniden gevşeten, Bellman-Ford'un optimize edilmiş hâlidir. Ortalama durum karmaşıklığı O(E) olsa da en kötü durum karmaşıklığı yine O(V × E) olur. Mülakatlarda SPFA'ya nadiren ihtiyaç duyulur; ancak Bellman-Ford seyrek graflarda çok yavaş kaldığında bunu bir optimizasyon olarak belirtebilirsiniz. Python'da yerleşik bir SPFA yoktur; ancak collections.deque ile uygulamak kolaydır.

Döviz Arbitrajı Algılama

Bellman-Ford'un klasik bir uygulaması şudur: döviz kurları verildiğinde arbitrajın mümkün olup olmadığını algılayın (dövizleri dönüştürdükten sonra başladığınızdan daha fazlasını elde ettiğiniz bir çevrim). Döviz kurlarının negatif logaritmasını alarak dönüşüm yapın. Arbitraj = negatif toplam log ağırlığına sahip bir çevrim = Bellman-Ford ile algılanabilen negatif çevrim. Bu, gerçek dünyadaki finans problemlerini standart algoritmaya dönüştürür.

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 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  # arbitrage!
    return False

Erken Sonlandırma Optimizasyonu

Tüm kenarlar üzerinde yapılan tam bir turda hiçbir uzaklık güncellenmezse sonraki turlar da hiçbir şeyi güncellemeyecektir; bu nedenle erken sonlandırın. Bu optimizasyon, graf birkaç turdan sonra zaten en iyi durumdaysa en iyi durum karmaşıklığını O(E) değerine düşürür. Her turun başında updated = False bayrağını ekleyin; turdan sonra False olarak kalırsa hemen çıkın.

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

Komşuluk Listeli Graflarda Bellman-Ford

Graf, kenar listesi yerine komşuluk listesi olarak verildiğinde önce bir kenar listesine dönüştürün veya tüm komşuluk listesi girdilerini kenarlar olarak dolaşın. V=1000 ve E=5000 için, her biri 5000 kenarı tarayan V-1=999 tur toplam 4.995.000 işlem yapar; bu, süre sınırlarının rahatlıkla içindedir. Çok yoğun graflarda (E ≈ V²) O(V³) en kötü durum karmaşıklığı Floyd-Warshall ile aynı olur; bu nedenle seçim bağlama bağlıdır.

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Hızlı Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı test edin.

Ders Özeti

Bu derste şunları öğrendiniz: Bellman-Ford, negatif ağırlıklı kenarları ele almak için tüm kenarları V-1 kez gevşetir, iyileştirmeler bulmaya devam eden V. gevşetme turu negatif bir çevrime işaret eder ve algoritmanın karmaşıklığı, Dijkstra'nın O((V+E) log V) değerine karşılık O(V × E)'dir. Sırada, tek bir O(V³) hesaplamayla tüm düğüm çiftleri arasındaki en kısa yolları bulan Floyd-Warshall var.

Sıkça Sorulan Sorular