Dijkstra’nın en kısa yol algoritması (DJK) ya da Dijkstra’nın deyişiyle “benim en kısa yol algoritmam” graf üzerinde bir noktadan diğer tüm noktalara en kısa yolu çıkarır ve bunu n noktalı bir grafta en kötü olarak O(n*n) zorlukta tamamlar. Daha önceden bahsettiğim Floyd-Warshall algoritması ise tüm noktalar arasındaki en kısa mesafeyi O(nnn) zorlukta çıkarıyordu. Dikkat ettiyseniz birisi yolu diğeri mesafeyi çıkarıyor. Algoritmanın aşamalarını ayrı ayrı değerlendirdiğimizde anlamamız daha kolay olacaktır. Örnek olarak 10×10′luk bir tahtanın üzerinde olduğumuzu düşünün. İlerlemeye (0,0) noktasından başlayıp, (9,9) noktasına ulaşmaya çalışacağız. Tahta üzerindeki her karede bir sayı olsun ve biz o kare üzerine geldiğimizde orada yazılı olan sayı kadar saniye beklemek zorunda kalalım. Bu durumda hedefimiz olan (9,9) noktasına en kısa zamanda nasıl ulaşırız? Başlangıç noktasının diğer tüm noktalara olan mesafesini tutmak için bir tane Distance dizisine ve gittiğimiz yolu hatırlamamız için ise Previous dizisine ihtiyacımız olacak. Dizinin her elemanı tahta üzerindeki bir koordinata karşılık gelecektir. Örneğin (3,8) noktasının indeksini 3*Genişlik + 8 = 38 olarak hesaplayabiliriz. Başlangıç noktasının üzerinde olduğumuz için buraya olan mesafemiz 0, diğer tüm noktalara olan mesafemiz ise sonsuz olsun:

Distances = new int[W*H];
Previous = new int[W*H];
for (int i = 0; i < W*H; i++)
{
  Distances[i] = INF;
  Previous[i] = -1;
}
Distances[0] = 0;

Algoritmadaki her adımda kaynak bir nokta seçip, bu noktadan komşu noktalara gitmenin bize maliyetini hesaplayacağız ve bu nokta için bir daha hesap yapmayacağız. Bu yüzden hangi noktalar üzerinde çalıştığımızı da bir şekilde tutmamız gerekiyor. Bunun için bir liste kullanabilirsiniz. Gidilen noktaları listeden çıkarıp geriye kalanlar içinde hedefe en yakın olanı seçerek devam edebilirsiniz. Liste boşalana kadar bu işleme devam edip tüm noktalar için hesaplamalarımızı yapmış oluruz:

var list = new List<int>();
for (int i = 0; i < W * H; i++) list.Add(i);
while(list.Count > 0)
{
  //hesaplamalar
}

Çapraz hareketler yapamayacağımız için her kare üzerinde gidilebilecek 4 yön var: sağa, sol, yukarı ve aşağı.

private static readonly int[] dx = { 1, 0, -1, 0 };
private static readonly int[] dy = { 0, 1, 0, -1 };

Tüm bu yönlere hareket etmenin bizim için maliyeti nedir hesaplayalım ve Distance dizisinde bu noktaya karşılık gelen indekse bu değeri yazalım.

while (list.Count > 0)
{
  // hedefe en yakın noktanın indeksini al
  int bi = GetClosestIndex(list);
  int cx = bi % W, cy = bi / W; 

  for (int i = 0; i < dx.Length; i++ )
  {
    int nx = cx + dx[i];
    int ny = cy + dy[i];
    // dışarıda kalıyorsa çık
    if (0 > nx || nx >= W || 0 > ny || ny >= H) continue;
    int ci = ny * W + nx;
    // bi'den ci'ye gidersek maliyeti nedir
    int cost = CostOfGoing(bi,ci);
    int alt = Distances[bi] + cost;
    //daha kazançlıysa burdan gidelim
    if (Distances[ci] > alt)
    {
      Distances[ci] = alt;
      Previous[ci] = bi;
    }
  }
}

Bu işlem tüm noktalar için yapıldığında hedef noktanın kaynak noktaya olan mesafesi Distance[Hedef] olacaktır. Gidilecek yol ise şöyle çıkarılabilir:

int target = 99;
List path = new List<int>();
while(Previous[target]!=-1)
{
    path.Add(target);
    target = Previous[target];
}
path.Reverse();

Dijkstra Algoritmasının en güçlü taraflarından birisi, çalışma süresinin kısa olmasıdır. Örnekte, kaynaktan başlayarak diğer tüm noktalara olan mesafeyi hesaplıyoruz sonra hedefimize giden yolu çıkarıyoruz. Bunu tüm noktalar için yapmak zorunda değiliz; eğer isterseniz algoritma içinde bi = target olduğu zaman algoritmayı sonlandırarak çalışma süresini de kısaltmış olabiliriz. İkinci olarak ise; bir noktanın diğer noktaya olan mesafesini bir maliyet fonksiyonu ile hesaplıyorruz. Sadece bu fonksiyonu değiştirerek farklı sonuçlar elde edebiliriz. Örneğin; tahtanın üzerindeki her kareyi bir tepe olarak düşünelim ve üzerindeki sayı ise o tepenin yüksekliği olsun. Bir tepeden diğerine geçerken; tırmanmamız yükseklik farkı kadar, aşağı inmemiz ise yükseklik farkının yarısı kadar zaman alsın. Bu durumda maliyet fonksiyonumuzu aşağıdaki gibi değiştirmek bize istediğimiz sonucu verecektir:

private int GetCostOfGoing(int bi, int ci)
{
    int diff = Height[bi] - Height[ci];
    if (diff < 0) return -diff / 2;
    return diff;
}

Tüm bu işlemi görsel olarak takip etmeniz için bir WPF projesi hazırladım. Buradan indirip inceleyebilirsiniz.

DipNot: Bu yazıyı, yazarken kaybettiğim o tuşuma armağan ediyorum.