Dijkstra Algoritması

Dijkstra Algoritması, ismini bulucusu Alman bilim adamı Edsger Dijkstra'dan almıştır. Dijkstra algoritması bağlı olan düğümler arasında en kısa yolu bulmaya yarayan bir algoritmadır. Çok sık olarak ağ yapılarında, oyun programlamada ve ulaşımda kullanılır. Örnek vermek gerekirse Türkiye sınırları içerisinde dağıtım yapan bir kargo şirketi şehirlerarası yolları kullanarak bir ilden bir ile en kısa yoldan nasıl gidilebileceğini bu algoritma sayesinde bulabilir.

Algoritmayı aşağıda oluşturduğumuz bir örneklem üzerinden açıklayacağım. Aşağıdaki L matrisi bağlı olan şehirlerin arasındaki uzaklığı bize göstersin. Aşağıdaki resimde bağlı olan şehirler gösterilmiştir.

Problemimiz yukarıdaki şekilde A noktasından diğer noktalara en kısa yolu kullanarak gitmektir. Her bir düğüm için bu algoritmayı kullanarak en kısa yolu bulacağız.

int[,] L ={
                {-1,  5, -1, -1, -1,  3, -1, -1}, 
                { 5, -1,  2, -1, -1, -1,  3, -1}, 
                {-1,  2, -1,  6, -1, -1, -1, 10}, 
                {-1, -1,  6, -1,  3, -1, -1, -1},
                {-1, -1, -1,  3, -1,  8, -1,  5}, 
                { 3, -1, -1, -1,  8, -1,  7, -1}, 
                {-1,  3, -1, -1, -1,  7, -1,  2}, 
                {-1, -1, 10, -1,  5, -1,  2, -1} 
            };

D matrisimiz bize gideceğimiz düğümlere olan o anki uzaklığı gösterecektir. Algoritma bittikten sonra D matrisi her bir düğüm için en kısa yolu gösteriyor olacaktır. C matrisi daha en kısa yolu bulmadığımız şehirleri gösterecektir (0->A düğümü 1->B düğümü ...vs.). Düğümlere gidecek en kısa yolu bulduğumuzda bu şehirleri teker teker C matrisimizden çıkartacağız. C matrisinde en kısa yolu bulunacak olan düğüm kalmadığında algoritmamız bitmiş olacaktır.

Pseudocode

function Dijkstra(L[1..n, 1..n]) : array [2..n]
    array D[2..n]
    set C 
    C <- {2, 3, 4, 5, 6, …, n}
    for i <- 2 to n
        D[i] <- L[1,i]
    repeat n - 2 times
        v <- C  // en küçük D[v] C den çıkarılır
        v <- C - {v} 
        for each w in C do
            D[w] <- min(D[w], D[v] + L[v,w])
    return D

Yukarıdaki Pseudocode da anlatıldığı gibi A düğümünden başlıyoruz ve bize komşu olan düğümler için yol uzunluğunu D matrisine yazıyoruz. Daha sonra bu D matrisinde en kolay gidilebilecek olan düğümü alıp bu düğüm için gidilebilecek tüm düğümler için D matrisini yeniliyoruz. D matrisinde düğüme giden birden fazla yol olduğunda en kısa olanı alıyoruz. Her bir düğüm için bu işlemi yaptığımızda en son elimizde kalan D matrisi bizim en kısa yolumuz olacaktır.

	D[]-> -1, 5,-1,-1,-1, 3,-1,-1 C[]-> -1, 1, 2, 3, 4, 5, 6, 7 Kaynak olan A düğümünden gitmeye çalıştığımızda B ve F düğümlerinin bize komşu olduğunu görüyoruz. Bu düğümlerin yollarını D matrisine yazıyoruz. Daha sonra en kısa yol olan F düğümünü alıp C matrisimizden çıkartıyoruz. (F düğümüne en kısa yol bulunur = 3)
	D[]-> -1, 5,-1,-1,11, 3,10,-1 C[]-> -1, 1, 2, 3, 4,-1, 6, 7 A ve F düğümü çözüm oluşturduğu için F düğümü üzerinden gidebileceğimiz diğer düğümler için yolu D matrisine yazıyoruz. Daha sonra bu matris üzerinde en kısa yol olan düğümü seçiyoruz. (B düğümüne en kısa yol bulunur = 5)
	D[]-> -1, 5, 7,-1,11, 3, 8,-1 C[]-> -1,-1, 2, 3, 4,-1, 6, 7 G ve F düğümleri için D matrisini yeniliyoruz. D matrisinde en kısa yol C düğümüne doğrudur ve 7 olarak bulunur. (C düğümüne en kısa yol bulunur = 7)
	D[]-> -1, 5, 7,13,11, 3, 8,17 C[]-> -1,-1,-1, 3, 4,-1, 6, 7 C düğümü için H ve D düğümlerine olan uzaklık D matrisinde yenilenir. D matrisinde en kısa yol 8 olarak G düğümüne doğrudur. (G düğümüne en kısa yol bulunur=8)
	D[]-> -1, 5, 7,13,11, 3, 8,10 C[]-> -1,-1,-1, 3, 4,-1,-1, 7 G düğümü için H düğümüne olan uzaklık yenilenir D matrisinde en küçük yol H düğümüdür. (G düğümüne en kısa yol bulunur = 10)
	D[]-> -1, 5, 7,13,11, 3, 8,10 C[]-> -1,-1,-1, 3, 4,-1,-1,-1 H düğümğ için E düğümü maksimum uzunluğu bulunur. Yeni oluşan D matrisinde en küçük yol E düğümüne aittir. (E düğümüne en kısa yol bulunur=11)
	D[]-> -1, 5, 7,13,11, 3, 8, 8 C[]-> -1,-1,-1,-1,-1,-1,-1,-1 C matrisinde -1 olmayan tek düğümümüz D düğümüdür. D düğümünün minimum uzunluğu C matrisi üzerinden 13 olarak bulunur. Sonuç olarak elimizde oluşan D matrisi tüm düğümlere giden minimum yol uzunluklarını içerir.

Örnek Kod

    class Dijkstra
    {        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank <rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }

İyi çalışmalar

Mehmet Ali ECER