Dijkstra Algoritması

Dijkstra Algoritması, 1956 yılında Hollandalı bilgisayar bilimci Edsger W. Dijkstra tarafından geliştirilen, çizge teorisinde kullanılan bir en kısa yol algoritmasıdır. Bu algoritma, belirli bir başlangıç düğümünden diğer tüm düğümlere olan en kısa yolları bulmak için kullanılır. Algoritma, ağırlıklı çizgelerde (kenarların belirli bir ağırlığı olduğu durumlarda) çalışır ve negatif ağırlıklı kenarlar içermeyen çizgeler için geçerlidir.

Çalışma Prensibi

Dijkstra Algoritması, açgözlü (greedy) bir yaklaşım benimser. Her adımda, o ana kadar bilinen en kısa yolu seçer ve bu yolu genişleterek diğer düğümlere ulaşmaya çalışır.

1- Başlangıç:

• Başlangıç düğümü belirlenir ve bu düğümün mesafesi 0 olarak ayarlanır.
• Diğer tüm düğümlere olan mesafeler sonsuz (∞) olarak başlatılır.
• Tüm düğümler ziyaret edilmemiş olarak işaretlenir.

2- En Kısa Mesafeli Düğüm Seçimi:

• Ziyaret edilmemiş düğümler arasından en küçük mesafeye sahip olan düğüm seçilir.
• Bu düğüm, mevcut düğüm olarak belirlenir.

3- Komşu Düğümlerin Güncellenmesi:

• Mevcut düğümün komşularına olan mesafeler hesaplanır.
• Eğer mevcut düğüm üzerinden komşu düğüme ulaşmak, daha kısa bir yol sağlıyorsa, komşu düğümün mesafesi güncellenir.
• Bu işlem, tüm komşu düğümler için tekrarlanır.

4- Ziyaret Edildi İşareti:

• Mevcut düğüm, ziyaret edildi olarak işaretlenir ve bir daha işleme alınmaz.

5- Tekrar:

• Tüm düğümler ziyaret edilene kadar 2. ve 3. adımlar tekrarlanır.

6- Sonuç:

• Algoritma tamamlandığında, başlangıç düğümünden diğer tüm düğümlere olan en kısa yollar bulunmuş olur.

Dijkstra Algoritması çizgesi

Zaman Karmaşıklığı

Dijkstra Algoritması'nın zaman karmaşıklığı, kullanılan veri yapısına bağlıdır:

• Dizi kullanıldığında: O(V2)
• Öncelik kuyruğu (min-heap) kullanıldığında: O((V+E)log⁡V)

Burada V düğüm sayısını, E ise kenar sayısını temsil eder.

Sınırlamalar

• Negatif Ağırlıklı Kenarlar: Dijkstra Algoritması, negatif ağırlıklı kenarlar içeren çizgelerde doğru sonuç vermez. Bu tür durumlarda Bellman-Ford Algoritması kullanılabilir.
• Yönlü Çizgeler: Algoritma, hem yönlü hem de yönsüz çizgelerde çalışır.

Dijkstra Algoritması, özellikle yol bulma, ağ yönlendirme ve coğrafi bilgi sistemleri gibi alanlarda yaygın olarak kullanılır.