0Pricing
Coding Interview Prep · Ders

Bellman-Ford ve Negatif Kenarlar

Negatifleri işleyin ve döngüleri algılayın.

Bellman-Ford ve Negatif Kenarlar, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. 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.

Dijkstra Ne Zaman Başarısız Olur

Dijkstra, çıkarılan uzaklığın kesin olduğuna güvenir; ancak negatif bir kenar daha sonra bir yolu ucuzlatabilir. Bu yüzden bozulur.

Bellman-Ford ile Tanışın

Bellman-Ford, negatif kenar ağırlıklarını işler. Dijkstra'dan daha yavaştır, ancak açgözlü mantığa güvenilemeyen durumlarda sağlamdır.

Temel İşlem

Her kenarı tekrar tekrar gevşetir: dist[u] ile kenar ağırlığının toplamı dist[v] değerinden küçükse dist[v] değerini bu daha küçük değere günceller.

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

Kaç Tur Gerekir

En kısa yol en fazla V eksi 1 kenar kullanır; bu nedenle her kenarı gevşetmek için V-1 tur uygulamak tüm uzaklıkları kesinleştirmeye yeter.

for _ in range(n - 1):
    relax_all_edges()

Uzaklıkları Başlatın

Dijkstra'da yaptığınız gibi, kaynak düğümün uzaklığını sıfır ve diğer tüm uzaklıkları sonsuzluk olarak başlatın.

dist = [float('inf')] * n
dist[src] = 0

Tam Bir Geçiş

Her geçişte tüm kenar listesini bir kez dolaşır ve her kenarı gevşetirsiniz. İyileştirmeler her geçişte bir adım ilerleyerek dışarıya yayılır.

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

V-1'in Yeterli Olmasının Nedeni

k geçişten sonra, k kenar kullanan tüm en kısa yollar doğrudur. V-1 geçiş sonunda her basit en kısa yol tamamlanmış olur.

Ek Geçiş

Bir geçiş daha yapın. Herhangi bir uzaklık hâlâ azalırsa maliyetin düşmeye devam ettiği anlaşılır; bu da negatif bir döngü olduğunu gösterir.

Negatif Döngüleri Belirleme

Negatif döngü, sonlu bir en kısa yol bulunmadığı anlamına gelir; çünkü maliyeti sınırsız biçimde azaltmak için döngüde sonsuza kadar dolaşabilirsiniz.

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

Çalışma Süresi

V geçiş boyunca E kenarı gevşettiğiniz için Bellman-Ford O(V * E) sürede çalışır; bu süre küçük veya orta büyüklükteki graflar için uygundur.

Dijkstra mı, Bellman-Ford mu

Negatif olmayan ağırlıklar ve hız için Dijkstra'yı seçin. Negatif ağırlıklar varsa veya hatalı bir döngüyü yakalamanız gerekiyorsa Bellman-Ford'u seçin.

Hızlı Kontrol

V-1 geçişten sonra, bir geçiş daha yaptığınızda bir uzaklık hâlâ azalıyor. Bu ne anlama gelir?

Özet: Bellman-Ford

Tüm kenarları V-1 geçiş boyunca gevşetin, ardından negatif döngüleri yakalamak için bir geçiş daha yapın. O(V*E) sürede çalışır, ancak Dijkstra'nın çalışamadığı durumlarda işe yarar. ✅

Sıkça Sorulan Sorular

“Bellman-Ford ve Negatif Kenarlar” dersi ücretsiz mi?

Evet — “Bellman-Ford ve Negatif Kenarlar” 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.

“Bellman-Ford ve Negatif Kenarlar” dersinde ne öğreneceğim?

Negatifleri işleyin ve döngüleri algılayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

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 3. dersidir.

“Bellman-Ford ve Negatif Kenarlar” 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.

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.

Bu kursun tüm dersleri

  1. Yığınla Dijkstra
  2. Deque ile 0-1 BFS
  3. Bellman-Ford ve Negatif Kenarlar
  4. Tüm Çiftler için Floyd-Warshall
← Coding Interview Prep Sayfasına Dön