Yığınla Dijkstra
Negatif olmayan kenarlarda açgözlü en kısa yolları bulun.
Yığınla Dijkstra, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. 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.
En Kısa Yol Problemi
Bir düğümden diğer tüm düğümlere giden en düşük maliyetli yolu bulmak istersiniz. Her kenarın ağırlığı sıfır veya pozitif olduğunda bu sorunu Dijkstra çözer.
Açgözlü Fikir
Dijkstra açgözlüdür: her zaman ziyaret edilmemiş düğümler arasından bilinen uzaklığı en küçük olanı genişletir ve bu uzaklığın kesin olduğuna güvenir.
Neden Minimum Yığın Kullanılır
En yakın düğümü hızlıca almak için bir minimum yığına ihtiyacınız vardır. Bu yapı, yavaş bir tarama yapmak yerine en küçük uzaklığı log n sürede verir.
import heapqUzaklıklarla Başlayın
Her uzaklığı sonsuzluk olarak ayarlayın, ardından kaynak düğümün uzaklığını sıfır yapın. Ulaşılamayan düğümler sonsuza kadar sonsuzluk değerinde kalır.
dist = [float('inf')] * n
dist[src] = 0Yığını Başlatın
Kaynak düğümü (uzaklık, düğüm) şeklinde bir demet olarak yığına ekleyin. Uzaklığı ilk sıraya koymak, yığının girdileri maliyete göre otomatik olarak sıralamasını sağlar.
pq = [(0, src)]En Yakın Düğümü Çıkarın
Her döngüde en küçük (d, u) değerini çıkarın. Bu d değeri u düğümüne olan en kısa uzaklıktır; dolayısıyla düğüm çıkarıldığında onunla ilgili iş bir kez tamamlanmış olur.
d, u = heapq.heappop(pq)Eski Girdileri Atlayın
Bir düğüm, yığında eski ve daha büyük bir uzaklıkla bulunabilir. d değeri saklanan uzaklıktan kötüyse bu girdiyi atlayın.
if d > dist[u]:
continueKomşuları Gevşetin
Gevşetme, bir komşunun uzaklığını iyileştirmeyi denemek demektir: u üzerinden gitmek daha ucuzsa uzaklığını güncelleyin ve onu yığına ekleyin.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))Tembel Silme Tekniği
Python yığınları bir anahtarı güncelleyemez; bu nedenle yinelenen girdileri eklersiniz ve eski olanları yok sayarsınız. Bu tembel yaklaşım kodu kısa ve hızlı tutar.
Çalışma Süresi
İkili yığınla Dijkstra O((V + E) log V) sürede çalışır. Bu, yüz binlerce kenarı olan grafları kolayca işler.
Kenar Ağırlıklarına Dikkat Edin
Dijkstra, negatif kenarlarda bozulur; çünkü çıkarılan bir uzaklık kesin olmayabilir. Bu durumda Bellman-Ford kullanın.
Hızlı Kontrol
(d, u) değerini çıkarıyorsunuz, ancak d değeri dist[u] değerinden büyük. Ne yapmalısınız?
Özet: Yığınlı Dijkstra
Uzaklıkları başlatır, (dist, node) değerini eklersiniz, en yakını çıkarır, eski çıkarma sonuçlarını atlarsınız ve komşuları gevşetirsiniz. O((V+E) log V) süresindeki Dijkstra tam olarak budur. 🚀
Sıkça Sorulan Sorular
“Yığınla Dijkstra” dersi ücretsiz mi?
Evet — “Yığınla Dijkstra” 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.
“Yığınla Dijkstra” dersinde ne öğreneceğim?
Negatif olmayan kenarlarda açgözlü en kısa yolları bulun. 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 1. dersidir.
“Yığınla Dijkstra” 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.