DIJKSTRA En Kısa Yol Algoritması

10312629_10152490043223938_6432979453490371210_n

Ü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.

dg34g21ggg

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.

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

1 Yorum

  1. seda

    Good day, I am studying master’s degree in Turkey.
    Dijkstra algorithm’ MATLAB code is necessary for Master’s thesis .
    Can you help me?

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir