Dijkstra Algoritması

İngilizcesi: Dijkstra's Algorithm
Okunuşu: daykstrız elgıridım

Güncellendi 30 Eylül 20263 dk okuma

Kısaca

Dijkstra algoritması, tüm kenar ağırlıkları sıfır ya da pozitifken bir başlangıç düğümünden diğer tüm düğümlere en kısa yolları bulan çizge algoritmasıdır.

Dijkstra algoritması nedir?

Dijkstra algoritması, her kenarın mesafe, süre ya da fiyat gibi bir maliyeti olduğu ağırlıklı bir çizgede, tek bir başlangıç düğümünden diğer tüm düğümlere giden en ucuz yolu bulur. 1959'da Hollandalı bilgisayar bilimci Edsger W. Dijkstra tarafından yayımlanmıştır ve hâlâ bilgi işlemde en yaygın kullanılan algoritmalardan biridir. Yalnızca hiçbir kenarın negatif ağırlığı olmadığında çalışır.

Algoritma, kaynak için 0, diğer her şey için sonsuz olmak üzere her düğüm için geçici bir uzaklık ve düğümleri bu uzaklığa göre sıralayan bir öncelik kuyruğu tutar. Uzaklığı artık kesinleşmiş olan, ziyaret edilmemiş en küçük uzaklıklı düğümü tekrar tekrar alır ve onun her kenarını gevşetir (relax): bu düğümden geçmek bir komşuya kaydedilenden daha kısa bir uzaklık veriyorsa komşuyu günceller ve kuyruğa ekler. Öncelik kuyruğu olarak ikili heap ile O((V + E) log V) sürede çalışır; V köşe sayısı, E kenar sayısıdır. Her iyileştirmenin hangi düğümden geldiğini kaydetmek, sonunda gerçek rotayı yeniden kurmanızı sağlar.

Farklı uzunluklardaki borulardan oluşan bir ağın başlangıç noktasına dökülen suyu düşünün: yakın kavşaklara önce ulaşır ve dışa doğru yayılır; bir kavşağa vardığı anda oraya en kısa yoldan gelmiştir. Dijkstra algoritması ya da ona dayanan daha hızlı varyantlar, harita ve navigasyon uygulamalarındaki rota planlamayı, yönlendiricilerin bir ağ üzerindeki yolları hesaplamak için kullandığı OSPF gibi bağlantı durumu (link-state) yönlendirme protokollerini ve oyunlarda ile robotikte yol bulmayı yürütür. A* algoritması, aramayı tek bir hedefe yöneltmek ve daha az düğüm keşfetmek için buna kalan mesafenin tahmini olan bir sezgisel (heuristic) ekler.

Dijkstra algoritması sıklıkla genişlik öncelikli aramayla karşılaştırılır. BFS en az kenarlı yolu bulur ve her kenar aynı maliyetteyse doğru araçtır; Dijkstra algoritması ise farklı ağırlıkları hesaba katar ve tüm ağırlıklar 1 olduğunda ikisi aynı cevapları verir. Ayrıca negatif kenar ağırlıklarında başarısız olur, çünkü bir düğümün uzaklığının ziyaret edildiğinde kesinleştiğini varsayar; bu çizgeler için daha yavaş olan Bellman-Ford algoritması gerekir. Her zaman ziyaret edilmemiş en yakın düğüme bağlandığı için açgözlü bir algoritmadır, ancak birçok açgözlü yöntemin aksine en iyi cevabı verdiği kanıtlanmıştır.

Önemli noktalar

Dijkstra algoritması, ağırlıklı bir çizgede tek bir kaynaktan diğer tüm düğümlere en kısa yolları bulur.
Her kenar ağırlığının sıfır ya da pozitif olmasını gerektirir.
Ziyaret edilmemiş en yakın düğümü tekrar tekrar kesinleştirir ve o düğümün kenarlarını gevşetir.
İkili heap ile O((V + E) log V) sürede çalışır.
Tüm kenarlar aynı maliyetteyse BFS yeterlidir; A* ise tek bir hedefe daha hızlı ulaşmak için bir sezgisel ekler.

Örnek

Python'da heap ile Dijkstra algoritmasıpython

import heapq
def dijkstra(graph, source):
    dist, queue = {source: 0}, [(0, source)]  # queue holds (distance so far, node)
    while queue:
        d, node = heapq.heappop(queue)  # the closest node not yet finalized
        if d > dist[node]:
            continue  # a stale entry: a shorter path was already found
        for neighbor, weight in graph[node]:
            if d + weight < dist.get(neighbor, float("inf")):
                dist[neighbor] = d + weight  # relax the edge
                heapq.heappush(queue, (d + weight, neighbor))
    return dist

roads = {"A": [("B", 5), ("C", 2)], "B": [("D", 4)], "C": [("B", 1), ("D", 8)], "D": []}
print(dijkstra(roads, "A"))  # {'A': 0, 'B': 3, 'C': 2, 'D': 7}

Sık sorulan sorular

Dijkstra algoritması neden negatif ağırlıklarla çalışmaz?

Bir düğüm öncelik kuyruğundan alındığında uzaklığının kesinleştiğini varsayar, çünkü diğer her rota daha uzun olmak zorundadır. Sonradan bulunan negatif bir kenar başka bir rotayı daha kısa yapıp bu varsayımı bozabilir; bu yüzden negatif ağırlıklı çizgeler bunun yerine Bellman-Ford algoritmasına ihtiyaç duyar.

Dijkstra algoritması ile BFS arasındaki fark nedir?

BFS en az kenarlı yolu bulur; bu da yalnızca her kenar aynı maliyetteyse en kısa yoldur. Dijkstra algoritması kenar ağırlıklarını hesaba katar ve düz kuyruk yerine öncelik kuyruğu kullanır; tüm ağırlıklar eşit olduğunda ikisi aynı sonucu verir.

Dijkstra algoritmasının zaman karmaşıklığı nedir?

İkili heap ile O((V + E) log V) sürede çalışır; V köşe sayısı, E kenar sayısıdır. Dizi tabanlı basit bir sürüm O(V^2) sürede çalışır ve bu, çok yoğun çizgelerde daha iyi olabilir.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin