Google Haritalar'da veya Yandex Navigasyon'da gitmek istediğiniz bir adresi seçtiğinizde, sistem saniyeler içinde trafik yoğunluğunu, sokak mesafelerini ve dönüşleri hesaba katarak size "En Hızlı Rota"yı sunar. Benzer şekilde, fabrika zemininde dolaşan otonom bir robot (AGV) veya Mars keşif aracı Curiosity, önündeki kraterlerin ve engellerin etrafından dolanarak hedefine en kısa yoldan ulaşmak zorundadır. İşte modern ulaşım ağlarının, internet veri paketlerinin ve robotik navigasyon sistemlerinin arkasında yatan mucizevi formül, 1956 yılında Hollandalı bilgisayar bilimci Edsger W. Dijkstra tarafından bir kahve molasında 20 dakikada tasarlanan **Dijkstra En Kısa Yol Algoritması (Dijkstra's Shortest Path Algorithm)**'dır.
---
1. Graf Teorisi Nedir? Düğümler ve Kenarlar
Dijkstra algoritmasını anlamak için öncelikle bilgisayar bilimlerinde haritaların nasıl temsil edildiğini bilmemiz gerekir. Bir harita matematiksel olarak bir **Çizge (Graf - Graph)** yapısıdır:
Dijkstra algoritmasının temel amacı şudur:
> "Belirli bir başlangıç düğümünden (Kaynak / Source) çıkan ve negatif olmayan kenar ağırlıklarına sahip bir grafta, diğer TÜM düğümlere giden en kısa (en az maliyetli) mesafeleri bulmak."
---
2. Dijkstra Algoritmasının Çalışma Mantığı: Açgözlü (Greedy) Yaklaşım
Dijkstra algoritması **Açgözlü (Greedy)** bir algoritmadır. Yani her adımda o an için bilinen en ucuz, en yakın düğümü seçerek genişler.
Adım Adım İşleyiş Algoritması:
1. **Mesafe Tablosu Oluşturma:** Başlangıç düğümünün mesafesi $0$ olarak atanır. Diğer tüm düğümlerin mesafesi henüz bilinmediği için sonsuz ($\infty$) yapılır.
2. **Ziyaret Edilmemişler Kümesi:** Graf içerisindeki tüm düğümler "ziyaret edilmemiş" olarak işaretlenir.
3. **En Yakın Düğümü Seçme:** Ziyaret edilmemiş düğümler arasından mesafesi en küçük olan düğüm seçilir (Buna aktif düğüm $U$ diyelim).
4. **Komşuları Gevşetme (Relaxation):** Aktif düğüm $U$'nun tüm komşularına ($V$) bakılır:
5. **Düğümü Kapatma:** Aktif düğüm $U$ "ziyaret edildi" olarak işaretlenir ve bir daha geri dönülmez.
6. Tüm düğümler ziyaret edilene veya hedefe ulaşılana kadar 3. adıma geri dönülür.
---
3. Örnek Simülasyon Üzerinde İnceleme
Aşağıdaki 4 şehirli basit haritayı ele alalım:
(4)
[A] ───> [B]
│ │
(2)│ (1)│ (5)
▼ ┌────┘
[C] ─┴──────> [D]
(7)Adım Adım Tablo Güncellemesi:
---
4. Zaman Karmaşıklığı ve Öncelik Kuyruğu (Priority Queue / Min-Heap)
Eğer algoritmayı düz bir liste üzerinde en küçük elemanı arayarak ($O(V)$) kurarsanız, toplam karmaşıklık $O(V^2)$ olur.
Ancak modern bilgisayar bilimlerinde en küçük düğümü anında çekebilmek için **İkili Yığın (Binary Min-Heap)** veya **Öncelik Kuyruğu (Priority Queue)** veri yapısı kullanılır.
$$O((V + E) \log V)$$
(Burada $V$ düğüm sayısı, $E$ ise kenar / yol sayısıdır).
Bu sayede milyonlarca sokak ve kavşaktan oluşan devasa ülkeler saniyeler içinde taranabilir.
---
5. Tam ve Çalışan Python Kodu
import heapq
def dijkstra(graph, start_node):
# Tüm mesafeleri sonsuz yap, başlangıcı 0 yap
distances = {node: float('inf') for node in graph}
distances[start_node] = 0
# Rota takibi için önceki düğümleri tutan sözlük
previous_nodes = {node: None for node in graph}
# Min-heap öncelik kuyruğu: (mesafe, düğüm)
priority_queue = [(0, start_node)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# Eğer kuyruktan çıkan mesafe mevcut kaydedilenden büyükse atla
if current_distance > distances[current_node]:
continue
# Komşuları incele
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# Daha kısa bir yol bulundu mu? (Relaxation)
if distance < distances[neighbor]:
distances[neighbor] = distance
previous_nodes[neighbor] = current_node
heapq.heappush(priority_queue, (distance, neighbor))
return distances, previous_nodes
def rota_cikar(previous_nodes, target_node):
path = []
curr = target_node
while curr is not None:
path.append(curr)
curr = previous_nodes[curr]
return path[::-1] # Listeyi ters çevir
# Test Grafı
harita = {
'A': {'B': 4, 'C': 2},
'B': {'D': 5},
'C': {'B': 1, 'D': 7},
'D': {}
}
mesafeler, rotalar = dijkstra(harita, 'A')
print("A noktasından tüm şehirlere en kısa mesafeler:", mesafeler)
print("A'dan D'ye giden en ideal rota:", rota_cikar(rotalar, 'D'))---
6. Dijkstra'nın Kritik Kısıtlaması: Negatif Ağırlık Çıkmazı
> **Hayati Uyarı:** Dijkstra algoritması **NEGATİF KENAR AĞIRLIKLARI** bulunan graflarda ÇALIŞMAZ!
Neden? Çünkü Dijkstra bir düğümü bir kez kapattığında ("ziyaret edildi" dediğinde), o düğüme daha kısa bir yoldan asla ulaşılamayacağını varsayar. Ancak negatif bir kenar varsa, ileride maliyet geriye doğru düşebilir ve açgözlü varsayım çöker. Eğer grafınızda negatif maliyetler (örneğin indirim kuponları, ters rüzgar akımı) varsa, Dijkstra yerine **Bellman-Ford Algoritması** kullanılmalıdır.
---
7. Kendini Geliştirme Görevi (Challenge)
**Görev:** Bir labirent robotu tasarlıyorsunuz. Labirentteki her hücre bir düğümdür ve robotun hücreler arasında geçerken harcadığı pil miktarı kenar ağırlığıdır. Yukarıdaki koda başlangıç ve bitiş koordinatlarını vererek, robotun pili en az tüketen rotasını ekrana yazdıran bir grid simülasyonu hazırlayın!
---
Sonuç
Dijkstra algoritması, matematiksel zekanın pratik hayattaki en somut zaferlerinden biridir. İnternet yönlendiricilerinden (OSPF protokolü) uçak rotalarına, oyunlardaki yapay zeka karakterlerinin hareketinden lojistik kargo dağıtımına kadar modern dünyanın tüm damarları Dijkstra mantığıyla beslenmektedir. Daha fazla algoritma içeriği için [Tüm Derslerimizi](/dersler) inceleyebilirsiniz!