Dijkstra Algoritması ile En Kısa Yol Bulma

Dijkstra Algoritması, graflar içinde birbirine bağlı düğümler arasında gidilebilen en kısa yolu bulmayı amaçlar. Algoritma, İnternet ağ trafiği protokolünü yönlendiren OSPF (Open Shortest Path First) protokolünde, oyun programlamada, ulaşım ağlarında kullanılır.

Algoritmanın Çalışması

1. Kaynak düğüm belirlenir (örneğimizde A). Kaynak düğümden gidilebilen diğer düğümler, “bir önceki düğüm / maliyet” şeklinde not edilir.

2. Bu düğümlerden en az maliyete sahip olan işaretlenir, diğerleri aynı bilgiyle devam eder. Ulaşılamayan düğümler için maliyet sonsuz olarak işaretlenir.

3. En az maliyete sahip düğüm için, henüz işaretlenmemiş diğer düğümlerin maliyeti hesaplanır, daha az maliyetli bir yol bulunduğunda değişiklik yapılır. Bu maliyet hesaplanırken, işaretlenmiş son düğümün maliyetini eklemeyi unutmayın, yola A’dan başlayıp çıkmıştık.

Bu işlemler sonsuz işaretlenen düğümler bitinceye kadar devam edilir.

Bu grafta A düğümünden diğer düğümlere giden en kısa yolu Dijkstra algoritmasıyla bulalım. Dikkat edilecek nokta; önceden işaretlenmiş düğümler için daha kısa mesafeye bakılmaz. Seçim her zaman işaretlenmemiş düğümler arasında yapılır.

Bu tabloyu çıkardıktan sonra bir düğümü başlangıç noktası kabul edip en kısa yolu ve toplam maliyeti görebiliyoruz. Örneğin A – H arası gidilebilecek en kısa yol için H sütununa baktığımızda maliyetin 6 olduğunu görüyoruz. A sütununa ulaşana kadar düğümleri takip ettiğimizde ise H -> E -> F -> C -> A yolunu buluyoruz.