Yazıdaki Başlıklar
Dijkstra Algoritması Nedir?
Dijkstra algoritması verilen bir şeklin en kısa yolunu bulmak için kullanılır. Basit bir mantıkla oluşturulan ve günümüzde çok fazla kullanılan bir algoritmadır. En kısa yoldan hedefe ulaşmayı amaçlayan en kısa yol algoritması, internet trafiğinin yönlendirilmesinde ve oyun programlamada da kullanılıyor. İki hedef düğüm arasında en az uğraşla gidilecek yolu belirleyen bu algoritma için düğümler arasındaki uzaklık belirlenmiş olmalıdır. Ayrıca başlangıç noktası belirlenerek bu noktadan diğer düğümlere olan uzaklıklar hesaplanarak en küçük uzaklık belirlenir. Bu uzaklık belirlendikten sonra bundan daha küçük bir değer bulunursa, bulunan son değer kabul edilir ve son düğüme gelene kadar bu işlem devam eder. Sonunda en kısa uzunluğun olduğu düğümler bulunur. Algoritmanın izlediği adımlar bu şekildedir.
Dijkstra Algoritması Örnek
Dijkstra algoritması örnek olarak Google Maps veya diğer navigasyon uygulamalarını verebiliriz. Bu uygulamalar, en kısa ve en karlı şekilde gidilebilecek rotayı belirler. Araç seçiminize göre farklı rotalar da navigasyon uygulamaları sayesinde oluşturulur. Bu uygulamalar da dijkstra algoritmasına dayanır.
A, B ve C noktalarının bulunduğu bir yol için, A’ya en yakın düğümün B olması durumunda A’dan B’ye gitmek, A’dan C’ye ve C’den B’ye gitmekten daha kısa bir yol olacaktır. Mesafelerini ölçtüğümüz düğümleri adım adım silerek güncelleştiriyoruz ve elimizde kalan son kısa yol en kısa yol olarak bulunuyor.
Dijkstra Algoritması Özellikleri
Algoritma, her bir düğümün durumunu belirler ve bu düğümlerin durumları iki farklı özelliğe sahiptir. Bunlardan ilki mesafe diğeriyse durum etiketidir. Bir düğümdeki mesafe değeri, kaynaktan düğüme olan mesafeyi gösteren sayıdır. Durum etiketi de düğümün mesafe değerinin diğer bir düğüme en kısa yol olduğunu veya olmadığını gösterir. Bir düğümün mesafe değeri, diğer bir düğümden olan en kısa yol ise o düğümün durum etiketi kalıcıdır denebilir. Bunun tersi durumunda ise geçici olarak değerlendirilir. Algoritma sayesinde, tüm adımlar güncellenerek devam edilir ve her adımda bir düğüm “şuan ki” olarak işaretlenir.
Dijkstra Algoritması Adımları
Algoritmanın ilk adımı ilklendirme olarak geçer. Bu adımda s düğümüne sıfır mesafe değeri atanarak kalıcı olarak etiketlenir. Diğer düğümlerin mesafe değerleri hesaplanarak geçici olarak etiketlenir. Üzerinde olunan düğüm ise üzerinde bulunulan düğüm olarak işaretlenir. İkinci adımda, mesafe değeri güncelleme yapılır. Üzerinde bulunulan düğümden ulaşılabilecek geçici etikete sahip düğüm bulunarak bu düğümün mesafe değerleri güncellenir.
Başka bir düğüm kümesine giderek en küçük mesafe değeri bulunur. Üzerinde bulunulan düğümün etiketi kalıcı yapılır ve şuanki düğüm olarak belirtilir. Üçüncü ve son adımda ise, s düğümünden gidilebilecek diğer düğümlerin tamamı kalıcıysa algoritma son bulur. Ancak değilse ve geçici düğümler hala devam ediyorsa ikinci adıma tekrar dönülerek aynı işlemler tekrarlanır. Mesafe değeri güncellenerek, hiç geçici düğüm kalmayana kadar devam edilir.
