Dijkstra algoritması, negatif olmayan ağırlıklı bir grafikte başlangıç düğümünden diğer tüm düğümlere olan en kısa yolları bulur. Başlangıç düğümünden başlarsın, geçici uzaklığı en küçük olan düğümü seçersin ve komşularının uzaklıklarını güncellersin. Bunu tüm düğümler kesinleşene kadar sürdürürsün. Bu yazıda tek bir örnek grafiği tur tur elle çözerek en kısa yol mantığını göreceksin.
Dijkstra algoritması her turda ne yapar?
Dijkstra her turda en küçük geçici uzaklığa sahip düğümü kesinleştirir ve bu düğümün komşularını yeni bir yol üzerinden yeniden değerlendirir. Algoritmanın bütün işi bu iki hamlenin tekrarıdır: önce en umut verici düğümü seç, sonra onun üzerinden daha kısa bir yol çıkıp çıkmadığına bak.
Makale boyunca tek bir grafik kullanacağız: yönsüz, ağırlıklı, 5 düğümlü ve 7 kenarlı. Düğümler A, B, C, D ve E. Kenarlar ve ağırlıkları şöyle:
- A-B: 4
- A-C: 2
- B-C: 1
- B-D: 5
- C-D: 8
- C-E: 10
- D-E: 2
Başlangıç düğümümüz A. Amacımız A'dan her düğüme giden en kısa yolun toplam ağırlığını bulmak. Kavramları bu örnek üzerinden tanımlayalım:
- Düğüm: Grafikteki noktalar. Örneğimizde A, B, C, D ve E.
- Kenar ve ağırlık: İki düğümü bağlayan çizgi ve üzerindeki maliyet. A-C kenarının ağırlığı 2'dir.
- Başlangıç uzaklığı: Başlangıç düğümünün kendisine uzaklığı sıfırdır, yani A için 0.
- Geçici uzaklık: Bir düğüme şimdiye kadar bulunmuş en kısa yolun uzunluğu. Başta A dışındaki tüm düğümler için sonsuzdur, çünkü henüz hiçbirine yol bulmadık.
- Seçilmiş (kesinleşmiş) düğüm: Uzaklığı artık değişmeyecek olan düğüm. Her tur tam bir düğüm bu duruma geçer.
- Önceki düğüm: Bir düğüme şimdiki en iyi yolla hangi düğümden gelindiği. Yolu sonradan geriye doğru kurmak için bu bilgiyi saklarız.
Kısacası her düğümün iki bilgisi vardır: geçici uzaklığı ve önceki düğümü. Algoritma ilerledikçe bu iki bilgi güncellenir, düğümler tek tek kesinleşir.
Beş düğümlü grafikte Dijkstra'yı elle çözmek
Aşağıdaki tabloda her satır bir turu gösteriyor. Hücrelerde geçici uzaklık ve parantez içinde önceki düğüm yer alır; kesinleşen düğümün değeri kalın yazılmıştır.
| Tur | Seçilen düğüm | A | B | C | D | E |
|---|---|---|---|---|---|---|
| Başlangıç | - | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A | 0 | 4 (A) | 2 (A) | ∞ | ∞ |
| 2 | C | 0 | 3 (C) | 2 (A) | 10 (C) | 12 (C) |
| 3 | B | 0 | 3 (C) | 2 (A) | 8 (B) | 12 (C) |
| 4 | D | 0 | 3 (C) | 2 (A) | 8 (B) | 10 (D) |
| 5 | E | 0 | 3 (C) | 2 (A) | 8 (B) | 10 (D) |
Final uzaklıklar: A=0, B=3, C=2, D=8, E=10.
Gevşetme adımı: B'nin değeri neden düştü?
Tablodaki asıl hareket 2. turda gerçekleşir. A-B kenarı doğrudan 4 ağırlığındaydı. Ancak C kesinleştiğinde A→C→B yolunun toplamı 2 + 1 = 3 çıkar ve bu, 4'ten küçüktür. B'nin değeri 3'e iner, önceki düğümü C olur. Bu güncellemeye gevşetme denir. Mantığı tek cümledir: seçilen düğümün uzaklığı + kenar ağırlığı, komşunun mevcut değerinden küçükse komşuyu güncelle. Aynı kural 3. turda D'yi 10'dan 8'e (3 + 5), 4. turda E'yi 12'den 10'a (8 + 2) indirir.
Bir düğüm seçildiği anda değerinin bir daha değişmemesinin nedeni şudur: seçilmemiş diğer tüm düğümlerin geçici uzaklığı seçilenden küçük olamaz. Ağırlıkların hiçbiri negatif olmadığı için, o düğümlerden birinin üzerinden geçen bir yol seçilen düğüme daha kısa bir rota sunamaz. Bu varsayım Dijkstra'nın doğruluğunun temelidir.
Sınavda tablo kurarken tek bir ipucu işini kolaylaştırır: her turda yalnızca seçilen düğümün komşularına bak. Kesinleşmiş düğümlere geri dönmen gerekmez. Elle çözümü kendi çizdiğin grafiklerde tekrarladıktan sonra, dilden bağımsız algoritmik düşünme becerini Algoritmik Düşünme Testi ile ölçebilirsin.
En kısa yolu önceki düğümlerden sondan başa kurmak
Mesafe tablosu yalnızca uzunluğu verir, yolun kendisini vermez. Yolu kurmak için her düğümün en kısa uzaklığına hangi düğümden gelindiğini de kaydedersin. Bu kayda önceki düğüm denir; bir düğümün uzaklığı her güncellendiğinde önceki düğümü de güncellenir.
Örnek grafikte E'nin önceki düğümü D, D'nin B, B'nin C, C'nin de A'dır. Hedeften başlayıp geriye doğru okursan E←D←B←C←A dizisini bulursun. Bunu ters çevirince yol A → C → B → D → E olur. Kenar ağırlıkları 2+1+5+2 = 10 eder ve bu, tablodaki E değeriyle aynıdır. Doğrudan A-C-E yolu 2+10 = 12 tuttuğu için daha uzundur.
Kısa bir kontrol önerisi: Kurduğun yoldaki kenar ağırlıklarını topla. Toplam tablodaki uzaklığa eşit çıkmıyorsa önceki düğüm kayıtlarında ya da güncelleme adımında bir hata var demektir.
Sözde kod ve heapq ile Python uygulaması
Önce algoritmanın iskeleti. Kuyruk, (uzaklık, düğüm) çiftlerini küçükten büyüğe sıralı tutan bir öncelik kuyruğudur.
tüm düğümlerin uzaklığını sonsuz yap
başlangıcın uzaklığını 0 yap
kuyruğa (0, başlangıç) ekle
kuyruk boşalana kadar:
(d, u) = kuyruktan en küçük çifti çek
eğer d > uzaklık[u] ise: atla
u'nun her komşusu v için (ağırlık w):
yeni = d + w
eğer yeni < uzaklık[v] ise:
uzaklık[v] = yeni
önceki[v] = u
kuyruğa (yeni, v) ekleAynı grafiği Python'da heapq modülüyle çözelim. Grafik, ders tablosundakiyle birebir aynıdır; her kenar iki yönlü eklenmiştir.
import heapq
graph = {
"A": {"B": 4, "C": 2},
"B": {"A": 4, "C": 1, "D": 5},
"C": {"A": 2, "B": 1, "D": 8, "E": 10},
"D": {"B": 5, "C": 8, "E": 2},
"E": {"C": 10, "D": 2},
}
def dijkstra(graph, start):
dist = {node: float("inf") for node in graph}
prev = {node: None for node in graph}
dist[start] = 0
queue = [(0, start)]
while queue:
d, u = heapq.heappop(queue)
if d > dist[u]:
continue
for v, w in graph[u].items():
yeni = d + w
if yeni < dist[v]:
dist[v] = yeni
prev[v] = u
heapq.heappush(queue, (yeni, v))
return dist, prev
dist, prev = dijkstra(graph, "A")
yol = []
node = "E"
while node is not None:
yol.append(node)
node = prev[node]
yol.reverse()
print("Uzaklıklar:", dist)
print("En kısa yol:", " -> ".join(yol))
print("Toplam:", dist["E"])Beklenen çıktı:
Uzaklıklar: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}
En kısa yol: A -> C -> B -> D -> E
Toplam: 10Değerler elle çözümdeki tabloyla, yol da önceki düğümlerden kurduğumuz diziyle aynıdır.
if d > dist[u]: continue satırı kuyruktaki eski kayıtları eler. Örnekte B önce 4 ile kuyruğa girer, sonra C üzerinden 3'e düşer ve kuyruğa ikinci kez eklenir. Kuyruktan önce (3, B) çıkar; sonradan gelen (4, B) kaydı güncel uzaklıktan büyük olduğu için atlanır. Bu satır olmasa sonuç yine doğru çıkardı ama gereksiz tekrar işlem yapılırdı.
Kodu kendi başına yeniden yazıp değiştirdikten sonra düzeyini görmek istersen ücretsiz bilgi testleri merkezindeki Python ve Java seviye testlerini deneyebilirsin.
Dijkstra negatif kenarlarda neden güvenilir değildir?
Dijkstra'nın doğruluğu tek bir varsayıma dayanır: bir düğüm kesinleştirildiğinde, geri kalan düğümlerden geçen hiçbir yol ona daha kısa bir rota sunamaz. Ağırlıklar negatif değilse bu doğrudur, çünkü bir yola kenar eklemek toplam uzaklığı asla azaltmaz. Negatif bir kenar bu varsayımı bozar. Daha sonra keşfedilen bir yol, yolun sonunda uzaklığı düşürebilir. Oysa algoritma o düğümü çoktan kesinleştirmiştir ve geri dönüp bakmaz.
Küçük bir yönlü graf üzerinde görelim. Kenarlar şunlar:
- A → B, ağırlık 2
- A → C, ağırlık 3
- C → B, ağırlık -2
Başlangıç düğümü A olsun. İlk turda geçici uzaklıklar B = 2 ve C = 3 olur. En küçük geçici uzaklık B'dedir, dolayısıyla Dijkstra B'yi 2 olarak kesinleştirir. Sonra C'ye geçer ve C → B kenarına bakar, ama B artık kapanmıştır. Oysa A → C → B yolunun uzunluğu 3 + (-2) = 1'dir. Gerçek en kısa uzaklık 1'dir, algoritma ise 2 döndürür.
Örnekteki kenarın yönlü olması önemlidir. Yönsüz bir kenar her iki yönde de geçilebildiği için negatif ağırlıklı yönsüz bir kenar, ileri geri gidip gelerek toplamı sürekli düşüren bir negatif döngü yaratır ve en kısa yol kavramı anlamını yitirir.
Grafında negatif ağırlıklı kenar varsa Dijkstra'yı hiç kullanma. Bu tür durumlar için Bellman-Ford adıyla anılan farklı bir algoritma ailesi vardır.
Dijkstra ne zaman kullanılır, ne zaman kullanılmaz? Karmaşıklık ve karar çerçevesi
Bir problemde Dijkstra'ya uzanmadan önce şu soruları sırayla yanıtla:
- Tüm ağırlıklar negatif olmayan mı? Sıfır ve pozitif değerler sorun çıkarmaz. Tek bir negatif kenar varsa Dijkstra güvenilmezdir.
- Tek bir başlangıçtan tüm düğümlere en kısa yol mu aranıyor? Dijkstra tam olarak bu problemi çözer. Her düğüm çiftinin birbirine uzaklığı gerekiyorsa algoritmayı her başlangıç için ayrı çalıştırman gerekir.
- Ağırlıklar eşit mi, yoksa yalnızca kenar sayısı mı önemli? Bu durumda ağırlıkları hesaba katmayan, düzey düzey ilerleyen daha basit bir gezinme (BFS) aynı sonucu daha sade bir kodla verebilir.
- Graf yoğun mu, seyrek mi? Uygulama seçimi buna bağlıdır; aşağıda ayrıntısı var.
- Yolun kendisi de gerekli mi? Yalnızca uzaklık yetmiyorsa her güncellemede önceki düğüm kaydını da tut ve yolu sondan başa kur.
Karmaşıklık, uygulamanın en küçük geçici uzaklığı nasıl bulduğuna göre değişir. Düğüm dizisi tutup her turda en küçük değeri doğrusal aramayla bulursan toplam iş yaklaşık O(V²) olur. Komşuluk listesi ve ikili yığın tabanlı bir öncelik kuyruğu (Python'da heapq) kullanırsan O((V+E) log V) mertebesine inersin. Seyrek grafta kenar sayısı düğüm sayısına yakın kalır ve yığın tabanlı sürüm genellikle avantajlıdır. Kenar sayısı V² değerine yaklaşan yoğun grafta ise dizi tabanlı sürüm de rekabetçi kalabilir. Bu yüzden mutlak bir "en hızlı" yoktur; seçimi grafın yapısı belirler.
Öğrenmeyi pekiştirmek için kâğıda 6-7 düğümlü, ağırlıkları negatif olmayan yeni bir graf çiz. Beş düğümlü örnekteki gibi bir tablo hazırla ve her turda kesinleşen düğümü, güncellenen komşuları ve önceki düğüm kaydını kendi başına doldur. Sonra aynı grafı heapq kodunda çalıştırıp çıktıyı tablonla karşılaştır. Aradaki fark çoğu zaman bir gevşetme adımını atlamandan çıkar. Bu çalışmayı bitirdiğinde blogdaki diğer algoritma ve veri yapıları yazılarına göz atarak bir sonraki konuya geçebilirsin.
Sık Sorulan Sorular
Dijkstra algoritması sıfır ağırlıklı kenarlarda çalışır mı?
Evet. Algoritmanın şartı ağırlıkların negatif olmamasıdır; sıfır bu şarta uyar. Sıfır ağırlıklı bir kenar toplam uzaklığı azaltmaz, yalnızca artırmaz, bu yüzden kesinleştirme mantığı bozulmaz.
Dijkstra algoritması yönlü grafikte de kullanılabilir mi?
Evet. Gevşetme adımında yalnızca düğümden çıkan kenarlara bakılır, dolayısıyla kenar yönleri doğal olarak hesaba katılır. Yönlü grafta da ağırlıkların negatif olmaması gerekir.
Dijkstra ile BFS arasındaki fark nedir?
BFS yolu kenar sayısıyla ölçer, Dijkstra ise kenar ağırlıklarının toplamıyla. Tüm kenarlar aynı ağırlıktaysa ikisi aynı sonucu verir ve BFS daha basittir. Ağırlıklar farklıysa BFS'nin bulduğu en az kenarlı yol, en düşük toplam ağırlıklı yol olmayabilir.
Dijkstra algoritması yalnızca iki düğüm arasındaki yolu mu bulur?
Hayır. Standart hâliyle başlangıç düğümünden tüm düğümlere en kısa uzaklıkları hesaplar. Yalnızca belirli bir hedef düğümle ilgileniyorsan, hedef kesinleştirildiği anda algoritmayı durdurabilirsin.
Dijkstra'yı iyi anlamanın en kısa yolu, küçük bir grafı elle çözüp ardından kodla doğrulamaktır; tablodaki her satırın kodda neye karşılık geldiğini gördüğünde algoritma ezber olmaktan çıkar.
