Dijkstra Algoritması Nedir?
Dijkstra algoritması, belirli bir başlangıç noktasından graf üzerindeki tüm diğer noktalara olan en kısa yolları bulan temel bir yönlendirmeli (greedy) algoritmadır. Genellikle ağ yönlendirme protokolleri ve harita uygulamalarında kullanılır.
Dijkstra algoritması, ağırlıklı kenarlara sahip bir graf üzerinde, tek bir kaynaktan diğer tüm hedeflere giden en kısa yolları bulmak için kullanılan bir keşif algoritmasıdır. Başlangıç noktasından uzaklıkları artan bir sıra ile ziyaret ederek çalışır.
Adım adım çözümlü örnekler
Dijkstra algoritması ile bir graf üzerinde en kısa yolu nasıl buluruz?
1. Tüm düğümlerin uzaklığını sonsuz, başlangıç düğümünün uzaklığını 0 olarak ayarla. 2. Ziyaret edilmemiş düğümler kümesini oluştur. 3. Şu anki düğümün komşularının uzaklıklarını güncelle: mevcut düğüme olan uzaklık + kenar ağırlığı. 4. En küçük uzaklığa sahip ziyaret edilmemiş düğümü seç ve ziyaret edildi olarak işaretle. 5. Hedef düğüme ulaşılana veya tüm düğümler ziyaret edilene kadar 3. ve 4. adımları tekrarla.
Dijkstra algoritmasının temel mantığı nedir?
Algoritma, her adımda başlangıç noktasına en yakın olan ve henüz tam olarak işlenmemiş düğümü seçer. Bu düğümün komşularının başlangıç noktasına olan uzaklıklarını, bu yeni düğüm üzerinden geçerek daha kısa bir yol olup olmadığını kontrol ederek günceller. Bu şekilde, her zaman yerel olarak en iyi kararı vererek küresel olarak en kısa yolu bulmaya çalışır.
Bilgi kartları
Mini test
S1.Dijkstra algoritması hangi tür graf kenarlarında doğru çalışır?
S2.Dijkstra algoritması bir yönlendirmeli (greedy) algoritma mıdır?
S3.Dijkstra algoritmasının temel veri yapısı genellikle hangisidir?
Sık yapılan hatalar
Dijkstra algoritması negatif ağırlıklı kenarları da işleyebilir. — Doğrusu: Dijkstra algoritması yalnızca pozitif veya sıfır ağırlıklı kenarlarda doğru çalışır. Negatif ağırlıklar için Bellman-Ford gibi farklı algoritmalar kullanılmalıdır.
Her adımda rastgele bir düğüm seçilir. — Doğrusu: Dijkstra algoritması, her adımda başlangıç noktasına en yakın ve henüz ziyaret edilmemiş düğümü seçer.
Sıkça sorulan sorular
Dijkstra algoritması neden negatif kenar ağırlıklarıyla çalışmaz?
Negatif kenar ağırlıkları, algoritmanın 'yerel olarak en iyi' seçimi yaparken 'küresel olarak en iyi' yolu bulma varsayımını bozabilir. Bir düğüme daha önce daha uzun bir yol bulunmuş olsa bile, negatif ağırlıklı bir kenar üzerinden geçerek daha kısa bir yol elde edilebilir, bu da algoritmanın temel mantığına aykırıdır.
Dijkstra algoritmasının zaman karmaşıklığı nedir?
Kullanılan veri yapısına bağlı olarak değişir. Basit bir dizi ile O(V^2), bir ikili yığın (binary heap) ile O((V+E)logV) veya bir Fibonacci yığını (Fibonacci heap) ile O(E + V logV) zaman karmaşıklığına sahiptir, burada V düğüm sayısı ve E kenar sayısıdır.
Dijkstra algoritması tek yönlü (directed) ve çift yönlü (undirected) graflarda kullanılabilir mi?
Evet, Dijkstra algoritması hem tek yönlü hem de çift yönlü graflarda kullanılabilir. Çift yönlü graflar, her iki yönde de aynı ağırlığa sahip iki tek yönlü kenar olarak temsil edilebilir.