12.7.1. Dijkstra'nın Algoritması

Dijkstra1'nın algoritması belirli bir başlangıç noktasına göre en kısa yolu belirleyen bir algoritmadır; bir düğümden, yani başlangıç düğümünden, diğer tüm düğümlere olan en kısa yolu belirler. Ağırlıklı ve yönlü graflar için geliştirilmiş olup graf üzerindeki herbir kenarın ağırlığı sıfır veya sıfırdan büyük sayıdır. Eğer, grafın kenar maliyetleri eksi olabiliyorsa belirli bir başlangıç düğümüne göre en kısa yolu bulmak için daha genel bir algoritma olan Bellman-Ford [CORMEN ve ark.-1999] kullanılabilir. Dijkstra'nın algoritmasının zaman karmaşıklığı tipik olarak hesaplanmıştır. Dijkstra'nın algoritmasını kaba-kodu aşağıdaki gibi verilebilir:

 

ROTA matrisini sıfırla;
for(başlangıç düğümü hariç tüm düğümler için)
    UM[i] ¬ ¥;

UM[başlangıç düğümü]=0;
S Ü Ø; (Seçilen düğümler kümesi; başlangıçta boş küme)

while(varış düğümü Ï S) {
        düğüm=Henüz S'de olmayan ve maliyeti en küçük olan düğüm;
        S=S U düğüm;
        for(Henüz S'de olmayan tüm düğümler için)
                if(UM[düğüm]+A[düğüm][aradüğüm]<UM[aradüğüm])
                        UM[aradüğüm]= UM[düğüm]+A[düğüm][aradüğüm];

1 DİJKSTRA, Edsger Wybe, - 1930 yılında doğan DİJKSTRA teorik fizik üzerine çalışırken 1950'li yılların başında programlamaya ilgi duymaya başladı. Bilgisayar bilimindeki birçok problemin çözümüne öneriler sunmuştur. En kısa yol algoritmasını da 1959 yılında sunmuştur.