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.

Ekran Alıntısı

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.

Dijkstra Algoritması ile En Kısa Yol Bulma’ için 6 yanıt

tt için bir cevap yazın Cevabı iptal et

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google fotoğrafı

Google hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Connecting to %s