0Pricing
Competitive Programming Academy · 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 Competitive Programming Academy 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, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy 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 Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy 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. Competitive Programming Academy 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.

Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, 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 Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Competitive Programming Academy 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
← Competitive Programming Academy Sayfasına Dön