Dijkstra En Kısa Yol Algoritması: Robotik Rota Planlama projesini yapmak ne kadar sürer ve kimler için uygundur?

Bu proje ortalama 30-45 dakika sürmektedir. Adım adım montaj rehberi ve test kodları sayesinde okul bilim fuarları, TÜBİTAK sergileri veya evde maker projeleri geliştirmek isteyen tüm meraklılar için uygundur.

Python kodlarında IndentationError (girinti hatası) nasıl önlenir?

Python'da bloklar süslü parantez yerine girintilerle belirlenir. if, for ve def satırlarından sonra gelen alt satırların 4 boşluk (veya 1 tab) içeride olduğundan ve boşluk ile tab karakterlerinin karıştırılmadığından emin olunmalıdır.

Dijkstra En Kısa Yol Algoritması: Robotik Rota Planlama çalışmasını tamamladıktan sonra nasıl daha ileri bir seviyeye taşıyabilirim?

Bu çalışmaya ek sensörler (kablosuz Bluetooth/Wi-Fi modülü, OLED ekran veya sesli buzzer uyarısı) entegre edebilir; verileri internet ortamına aktararak Nesnelerin İnterneti (IoT) tabanlı akıllı bir sisteme dönüştürebilirsiniz.

Dijkstra En Kısa Yol Algoritması: Robotik Rota Planlama

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:

Düğümler (Nodes / Vertices): Şehirler, kavşaklar veya robotun durabileceği koordinat noktalarıdır ($A, B, C, D$).

Kenarlar (Edges): Düğümleri birbirine bağlayan yollar veya kablolardır.

Ağırlıklar (Weights): Bu yolların maliyetidir. Bu maliyet fiziksel mesafe (metre), geçiş süresi (dakika) veya yakıt tüketimi olabilir.

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ı:

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.

Ziyaret Edilmemişler Kümesi: Graf içerisindeki tüm düğümler "ziyaret edilmemiş" olarak işaretlenir.

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).

Komşuları Gevşetme (Relaxation): Aktif düğüm $U$'nun tüm komşularına ($V$) bakılır:

Eğer `(U'ya gelme maliyeti + U'dan V'ye giden yol) < V'nin mevcut mesafesi` ise;

$V$'nin mesafesi bu daha kısa yeni değerle güncellenir!

Düğümü Kapatma: Aktif düğüm $U$ "ziyaret edildi" olarak işaretlenir ve bir daha geri dönülmez.

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:

Başlangıç Şehri: A

$A o B$: Maliyet = 4

$A o C$: Maliyet = 2

$C o B$: Maliyet = 1

$C o D$: Maliyet = 7

$B o D$: Maliyet = 5

 (4) [A] ───> [B] │ │ (2)│ (1)│ (5) ▼ ┌────┘ [C] ─┴──────> [D] (7)

Adım Adım Tablo Güncellemesi:

Başlangıç: $Dist[A]=0$, $Dist[B]=\infty$, $Dist[C]=\infty$, $Dist[D]=\infty$.

1. Adım (A Seçildi): Komşuları $B$ ve $C$.

$Dist[B] = \min(\infty, 0 + 4) = 4$.

$Dist[C] = \min(\infty, 0 + 2) = 2$.

$A$ kapatıldı.

2. Adım: Ziyaret edilmeyenler içinde en küçük $Dist[C] = 2$ olduğu için C seçilir!

$C$'den $B$'ye yol var: $2 + 1 = 3$. Önceki $Dist[B]=4$ idi; $3 < 4$ olduğu için B'nin mesafesi 3 olarak güncellenir!

$C$'den $D$'ye yol var: $2 + 7 = 9$. $Dist[D] = 9$.

$C$ kapatıldı.

3. Adım: Kalanlar içinde en küçük $Dist[B] = 3$ olduğu için B seçilir!

$B$'den $D$'ye yol var: $3 + 5 = 8$. Önceki $Dist[D]=9$ idi; $8 < 9$ olduğu için D'nin mesafesi 8 olarak güncellenir!

$B$ kapatıldı.

Sonuç: $A$'dan $D$'ye en kısa yol $A o C o B o D$ olup toplam maliyeti 8'dir!

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.

Öncelik Kuyruklu Dijkstra Karmaşıklığı:

$$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!