En kısa yol problemi (Shortest path problem) — Dijkstra algoritması ve C kodu

Bu yazımda en kısa yol problemi ve dijkstra algoritmasından bahsedecek, C kodunu paylaşacağım.

En kısa yol problemi ağırlıklı bir grafta herhangi bir tepeden diğer tüm tepelere (veya herhangi bir tepeye) en kısa yolun bulunması problemidir. Dijkstra algoritması bu problemin çözümü için kullanılan en popüler algoritmalardan biridir. Adını Hollandalı Matematikçi ve Bilgisayar Bilimci Edsger Dijkstra'dan alır. Dijkstra algoritmasının popülaritesine aldanıp mükemmel bir algoritma olduğunu düşünebilirsiniz ama Dijkstra algoritması sezgisel açgözlü bir algoritmadır. Yani en iyi sonucu vermeyi garanti etmez. Bunun yanı sıra çok etkili bir algoritmadır. En kısa yol problemleri gerçek hayatta büyük problemlerdir, kesin sonucu verecek algoritmaları çalıştıracak süper bilgisayalar ile bile çok geç cevap almanız veya hiç cevap almamamız büyük olasılıktır.

Şimdi algoritmayı olabilecek en basit şekilde açıklamaya çalışalım. Adım adım yazacak olursak :

1- Tüm tepelere gidiş maaliyetlerini SONSUZ olarak işaretle. Başlangıç düğümünü gidildi olarak işaretle ve komşularının maaliyetlerini güncelle.

2- Gidilmemiş (işaretlenmemiş) en ağırlıklı tepeyi bul , gidildi olarak işaretle. O tepeye komşu tepelerin ağırlıklarına bak . Eğer gelinen düğümün ağırlığı bakılan düğümün ağırlığından küçükse o tepeyi güncelle ve yolu not et.

3- Tüm tepeler için adım 2'yi tekrarla.

Aşağıda algoritmanın görsel olarak anlatılması mevcut. Daha iyi anlaşılması için düğümleri şehir merkezleri , bağıntıları uzunlukları bilinen yollar olarak düşünülebilir.

Şimdi son tabloyu 0. düğümden diğer düğümlere gitmenin maaliyeti tablosu olarak düşünün. Örneğin 0'dan 4'e maaliyet en düşük 5 tir. 0 dan 5'e gitmenin maaliyeti en düşük 7 dir. Peki o en az maaliyetli yolu nasıl bulacağız. Onu da geriye izleme yaparak bulabiliriz. Maaliyetlerin altındaki geldiğimiz yolu kaydettiğimiz işaretlere göre;

5'e 4'ten, 4'e 1'den, 1'e de 0'dan gelmişiz. Yani yolumuz 0 ->1->4->5.

Gerçekten de en düşük maaliyetli yolun bu olduğunu bu basit graf’a bakarak algoritmanın harika iş çıkardığını görebilirsiniz. Algoritma fazla aç gözlü davranarak 0'dan en düşük maaliyetli yolu seçip 2 ye gidebilir ve toplam maaliyeti arttırabilirdi ama ileriye dönük karar verip ilk başta daha maaliyetli yolu yani 4'ü seçti.

C implementasyonu aşağıdaki gibidir. Program bir komşuluk matrisi okur. Komşuluk matrisi basitçe 0. düğümden 1. düğüme gitmenin maaliyeti 4 ise matris[0][1]=4 tür. Örnekteki komşuluk matrisi aşağıdaki linktedir. Aynı zamanda tüm repoya buradan ulaşabilirsiniz: