DIJKSTRA En Kısa Yol Algoritması

Ünlü algoritmalardan bir tanesidir. En Kısa Yol Algoritması basit bir mantıkla oluşturulmuş ve günümüzde oldukça kullanılan algoritmalardan bir tanesidir. En Kısa Yol Algoritması’nın çıkış noktası farklı düğümlerden en kısa yoldan hedefe ulaşmayı amaçlamaktadır. Bu amaçla günümüzde de internet trafiğinin yönlendirilmesinde, oyun programlamada sıkça kullanılmaktadır ve en çok karşılaştığımı navigasyon ve gps sistemlerinde kullanılmaktadır.

En Kısa Yol Algoritması iki hedef düğüm arasında en az uğraş ile gidilebilecek yolun belirlenmesidir. Bu yol algoritmasının nasıl olması gerektiğinin üzerinde çok düşünülmüş ve en çok kullandığım ise Dijkstra’nın En Kısa Yol Algoritması. En Kısa Yol Algoritması‘nın Bellman ve Ford’un da geliştirdiği algoritmalar mevcut.

Bu yazıda DIJKSTRA’nın En Kısa Yol Algoritması‘nı anlatmaya çalışacağım.

1. Düğümler arasında uzaklık değerleri belirlenmiş olmalı.
2. Bir başlangıç noktası belirliyoruz. Bu başlangıç noktası 0 noktamız.
3. Başlangıç noktasından diğer düğümlerin uzaklıkları hesaplıyoruz.En küçük uzaklığı buluyoruz.
4. En küçük uzaklığı bulduktan sonra daha küçük bir değer bulunduysa yeni bulunan değer kabul edilir.
5. Son düğüme gelene kadar bu işleme devam edilir.
6. Sonunda programımız bize en kısa yolun olduğu düğümleri gösterir.

En Kısa Yol Algoritmasının Sözde Kodu bu adımlardan oluşmakta.

En Kısa Yol Alg0ritmasının günümüzde oldukça sık kullanıldığını dile getirmiştim. En Kısa Yol Algoritması’nıın üzerindeki çalışmalar devam ederken bu yazıyı yazmadan önce hem öğrenme aşamasında güzel bir kaynak buldum. Yönsüz Çinli Postacı Problemi: Polis Devriye Araçları İçin Bir Uygulama’sı adlı makalede, En Kısa Yol Algoritmasını bir tez tarzında benim anlatamayacağım şekilde çok güzel özetlenmiş halini bu yazıda bulacaksınız.

http://blog.burakkutbay.com/wp-content/uploads/2014/05/q3etgfa%C5%9Fklfasdf.pdf

Döküman Kaynağı: https://s3.amazonaws.com/kaynakca/24919383-0959-4289-a846-b8990ec8b1c1/emtullah.pdf