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. Kaynak düğümden gidilebilen diğer diğer düğümler seçilir.

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

3. İkinci adımda seçilen maliyeti en az olan düğümden gidilebilen düğümler arasında aynı işlem uygulanır. 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. Örneğin K’ya giden yol J ve I düğümlerinden daha kısa görünürken önceden işaretlenmediği için değiştirilmiştir.

AA

Bu tabloyu çıkardıktan sonra A ve düğümler arası gidilen en kısa yol bulunabilir. Örneğin A – H arası gidilebilecek en kısa yol, tabloya göre A-C-F-E-H yolu izlenerek toplamda 2+1+1+2 olmak üzere 6 birim olduğu görülür.

Reklamlar

6 thoughts on “Dijkstra Algoritması ile En Kısa Yol Bulma

Bir Cevap Yazın

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 )

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 )

Google+ fotoğrafı

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

Connecting to %s