DSA Interview Prep · Ders

Öncelik Kuyruğuyla Dijkstra Algoritması

Q: “Öncelik Kuyruğuyla Dijkstra Algoritması” dersi ücretsiz mi?

Evet — “Öncelik Kuyruğuyla Dijkstra Algoritması” 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 DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.

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

Önceden deneyim gerekmez. CoddyKit'te DSA 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.

Q: “Öncelik Kuyruğuyla Dijkstra Algoritması” 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 DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her DSA 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.

Dijkstra’yı heapq kullanarak uygulayın, ağırlıklı bir graf üzerinde gevşetme adımlarını izleyin ve k durak içindeki en ucuz uçuşlar problemini çözün.

Öncelik Kuyruğuyla Dijkstra Algoritması, CoddyKit'te ücretsiz bir DSA 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, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.

Ağırlıklı Graflarda En Kısa Yol

Dijkstra algoritması, negatif olmayan kenar ağırlıklarına sahip ağırlıklı bir grafta tek bir kaynak düğümden diğer tüm düğümlere olan en kısa yolları bulur. Algoritma, düğümleri o ana kadarki en iyi bilinen uzaklıklarına göre açgözlü biçimde işler; her zaman ziyaret edilmemiş en yakın düğümü genişletir. Temel veri yapısı, en küçük uzaklığa sahip düğümü verimli biçimde alan bir minimum yığın (öncelik kuyruğu) yapısıdır.

Algoritma Adımlarına Genel Bakış

Dijkstra algoritması: (1) dist[source] = 0 ve dist[all others] = inf değerlerini başlatın. (2) (0, source) çiftini minimum yığına ekleyin. (3) Uzaklığı en küçük olan u düğümünü çıkarın. Daha küçük bir uzaklıkla daha önce ziyaret edildiyse atlayın. (4) u düğümünün her komşusu v için: dist[u] + weight(u,v) < dist[v] ise dist[v] değerini güncelleyin ve (dist[v], v) çiftini yığına ekleyin. (5) Yığın boşalana kadar tekrarlayın.

Python'da Öncelik Kuyruğuyla Uygulama

Python'un heapq modülü bir minimum yığın uygular. Grafı komşuluk listesi olarak gösteririz: graph[u] = [(v, weight), ...]. Yığın, (distance, node) çiftlerini tutar. Daha iyi bir yol bulunmadan önce eklenmiş, artık geçerli olmayan yığın girdilerini atlamak için bir visited kümesi kullanırız.

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

Çözümlü Örnek

5 düğümlü ve şu kenarlara sahip bir graf düşünün: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). 0 düğümünden en kısa yollar: 1'e 0→2→1 üzerinden maliyet 3, 2'ye maliyet 1, 3'e 0→2→1→3 üzerinden maliyet 4 ve 4'e 0→2→1→3→4 üzerinden maliyet 7. Dijkstra bunların tümünü tek geçişte bulur; yalnızca tek bir hedefe giden yolu bulmakla kalmaz.

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

Dijkstra Negatif Ağırlıklarda Neden Başarısız Olur

Dijkstra'nın doğruluğu, bir düğüm minimum yığından çıkarıldığında uzaklığının kesinleştiği gerçeğine dayanır. Bu yalnızca kenar ağırlıkları negatif değilse geçerlidir. Ağırlığı -5 olan u→v negatif kenarı söz konusu olduğunda, v'yi ziyaret ettikten sonra u üzerinden daha kısa bir yol bulabiliriz; ancak v zaten ziyaret edildi olarak işaretlenmiştir. Tek bir negatif kenar, sonraki tüm uzaklık hesaplamalarını geçersiz kılabilir.

K Durak İçindeki En Ucuz Uçuşlar (LeetCode 787)

Bu problem bir kısıtlama daha ekler: en fazla k durak. Standart Dijkstra, adım sayılarını kendiliğinden ele almaz. Çözüm: durumu (cost, node, stops_remaining) biçiminde genişletin. Bu üçlüyle Dijkstra kullanın veya k+1 gevşetme turuyla Bellman-Ford kullanın. Değiştirilmiş Dijkstra, stops_remaining 0'a ulaştığında durarak başka sıçramalar yapılmasını önler.

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

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

Zaman Karmaşıklığı Analizi

İkili yığınla Dijkstra, O((V + E) log V) zamanda çalışır: her köşe bir kez çıkarılır (V çıkarma), her kenar bir ekleme işlemini tetikleyebilir (E ekleme) ve her yığın işlemi O(log V) maliyetindedir. Fibonacci yığınıyla sınır O(E + V log V) değerine iyileşir; ancak Python'un heapq modülü ikili yığın kullanır. Seyrek graflarda (E ≈ V) ikili yığın sürümü O(V log V) olur; yoğun graflarda (E ≈ V²) ise O(V² log V) olur.

En Kısa Yolun Yeniden Oluşturulması

Yalnızca uzaklıkları değil, gerçek yolu da elde etmek için bir prev dizisi tutun: dist[v] güncellenirken prev[v] = u atayın. Algoritma tamamlandıktan sonra, geriye doğru iz sürerek kaynaktan hedefe giden yolu yeniden oluşturun: dst ile başlayın, source konumuna ulaşana kadar prev işaretçilerini izleyin ve sonucu ters çevirin.

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    # Reconstruct
    path, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

Seyrek Graflarda Sözlük Kullanımı

Düğümler dizelerden veya ardışık olmayan tam sayılardan oluşuyorsa, komşuluk listesi için bir defaultdict(list), uzaklıklar için de normal bir dict kullanın. Bu, düğümlerin 1'den n'ye kadar etiketlendiği Network Delay Time gibi LeetCode problemlerinde yaygındır. dist = {node: inf for node in all_nodes} kullanmayı ve algoritmadan sonra ulaşılamayan düğümleri kontrol etmeyi unutmayın.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

Ağırlıksız Graflar için BFS ile Karşılaştırma

Ağırlıksız graflarda BFS, O(V + E) içinde en kısa yolları bulur; bu, Dijkstra'nın O((V+E) log V) karmaşıklığından daha hızlıdır. Dijkstra, normal bir FIFO kuyruğu yerine öncelik kuyruğu kullanarak BFS'yi ağırlıklı graflara geneller. Tüm kenar ağırlıkları eşit olduğunda Dijkstra, BFS'ye indirgenir. Ağırlıksız graflar için BFS'yi, negatif olmayan ağırlıklar için Dijkstra'yı, negatif ağırlıklar için Bellman-Ford'u seçin.

Azaltma Anahtarı Optimizasyonuyla Dijkstra

Ders kitaplarındaki Dijkstra, azaltma anahtarı kullanan bir öncelik kuyruğudur: bir düğümün uzaklığı iyileştiğinde önceliğini yerinde güncelleyin. Bu, O(E + V log V) için bir Fibonacci yığını gerektirir; ancak uygulaması zordur. Mülakatlarda kullanılan tembel silme yaklaşımı ise bunun yerine yeni bir girdi ekler ve güncelliğini yitirmiş çıkarma sonuçlarını atlar; yalnızca sabit katsayılı ek yükle daha basittir. Python'da heapq ile tembel silme, mülakatlarda kullanılan standart uygulamadır.

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: Dijkstra, düğümleri mevcut en iyi uzaklık sırasına göre açgözlü biçimde işlemek için minimum yığın kullanır, O((V+E) log V) zamanda çalışır ve negatif ağırlıklı kenarlarda başarısız olur ve güncelliğini yitirmiş yığın girdileri, çıkarma sırasında bir ziyaret edilmiş kümesi kontrol edilerek ele alınır. Sırada, negatif ağırlıkları n-1 gevşetme turuyla ele alan Bellman-Ford var.

Sıkça Sorulan Sorular