Dijkstra’s Algorithm

DIJKSTRA’S ALGORITHM

Dijkstra algoritması aynı zamanda Shortest Path Algorithm olarak adlandırılır. Bu algoritma greedy (aç gözlü) bir algoritmadır. Weighted ( ağırlıklı) graphlarda kullanılan bir graftır. Ayrıca algoritmanın uygulanacağı grafta cycle (döngü) bulunmaması gerekiyor.

Bu algoritmada minimumCosts[] adında bir dizi oluşturup, bu dizide belirlediğimiz source düğümünden en kısa yolları içerir. (Örneğin 0 vertexinden (düğümünden) 2 düğümüne gidilmesinin MINIMUM maliyetini içerir.

Algoritmamızı incelemeden önce basit bir şekilde ana mantığını kavrayalım:

Dijkstra’s Algorithm aynı zamanda minimum cost algorithm olarak da adlandırılabilir.

Edgelerin (yolların) üstüne costları (maliyetleri) yazıyoruz.Bu maliyet zaman olabilir, yakıt olabilir v.b

  1. Başlangıç vertex’i seçilir ve buna sourceVertex adı verilir.
  2. Bulunduğunuz noktadan gidilen noktalara bakın.
  3. Maliyeti en düşük olan yolu seçin.
  4. Gidilen yerin komşularına gidişinin maliyetine bakın.
  5. Eğer maliyet daha düşük oluyorsa maliyeti güncelleyin.

Algoritmamızı inceleyelim:

1- Bir cost (maliyet) grafı oluşturmamız gerekiyor. Bu matrise cost[row][column] adını verelim. Row (satır) i diyelim, column (j) dersek, i noktasından j noktasına gidişin maliyetini bu diziye yazarız. cost[i][j]. Eğer i noktasından j noktasına bir gidiş yoksa bu yolun maliyeti sonsuz olarak tabloya işleniyor. (Sonsuz kullanmak için C dilindeki INT_MAX değişkeninden faydalanabilirsiniz)

2- Bir adet isVisited (gidildi mi ?) adında bir dizi oluşturuyoruz. Bu dizinin amacı bir düğümden diğerine gidildikten sonra o düğümün visited olduğunu anlamamız için yapıyoruz. Aynı zamanda source olarak seçilen bir düğümün visited olarak işaretlememiz gerekiyor. Initialize ederken tüm diziyi 0 olarak dolduruyoruz.

3- Başlangıç düğümümüzü belirledikten sonra bu düğümü 1 olarak visited dizimizde işaretliyoruz. Hangi düğümü seçtiğiniz önemli değil ancak 0. düğümü seçtiğimizi farz edersek visited[0] = 1; şeklinde olacaktır.

4- Bir adet previousVertex (bir önceki düğüm) adında bir dizi oluşturuyoruz. Amacımız bir önceki düğümü kontrol edebilmek.

5- Bir adet minimumCosts adında bir dizi oluşturuyoruz. Bu dizide de amacımız her düğüme, source düğümünden gidilebilecek minimum uzaklıkları kaydediyoruz ve bunlar print etmemizde fayda sağlıyor.

Time Complexity

Bu algoritmada iç içe döngüler içerdiği için O(n^2) bir karmaşıklığı vardır.

Şimdi kodları paylaşmadan önce kodun içerisindeki grafın ezbere olmadığını öncelikle belirtmek istedim. Ben aşağıdaki şekildeki graftan v1 düğümünü source alarak en kısa maliyetleri bulmaya çalıştım. Siz aynı şekilde başka bir grafı da koyabilirsiniz.

 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF INT_MAX
#define VERTICES 7
#define TRUE 1
#define FALSE 0
#define VISITED TRUE
#define UNVISITED FALSE
#define INVALID_VERTEX  -1

typedef int BOOL;

// ***GLOBAL DATA***
BOOL isVisited[VERTICES];
int minimumCosts[VERTICES];
int previousVertex[VERTICES];

int costGraph[VERTICES][VERTICES] = {
    
                                           //   v1    v2   v3   v4   v5    v6   v7
                                      /*v1*/ { INF,   2,   INF, 1,   INF,  INF, INF  },
                                      /*v2*/ { INF,   INF, INF, 3,   10,   INF, INF  },
                                      /*v3*/ { 4,     INF, INF, INF, INF,  5,   INF  },
                                      /*v4*/ { INF,   INF, 2,   INF, 2,    8,   4  },
                                      /*v5*/ { INF,   INF, INF, INF, INF,  INF, 6  },
                                      /*v6*/ { INF,   INF, INF, INF, INF,  INF, INF  },
                                      /*v7*/ { INF,   INF, INF, INF, INF,  1,   INF  },

};
// ***GLOBAL DATA***

// ***FUNCTION DECLARATIONS***

void DijkstrasShortestPath(int sourceVertex);
int  FindSmallestUnvisitedVertex();
void PrintMinimumCosts(int sourceVertex);
void PrintPreviousVertex();
// ***FUNCTION DECLARATIONS***

void InitializeData(){ // FUNCTION TO INITIALIZE GLOBAL ARRAYS
    for (int i = 0; i < VERTICES; i++) {
        isVisited[i] = UNVISITED;
        minimumCosts[i] = INF;
        previousVertex[i] = INVALID_VERTEX;
    }
}

int FindSmallestUnvisitedVertex(){
    int cost = INF;
    int costVertex = INVALID_VERTEX;
    for (int i = 0; i< VERTICES; i++) {
        if (isVisited[i] == UNVISITED) {
            if (minimumCosts[i] < cost) {
                cost = minimumCosts[i];
                costVertex = i;
            } // IF
        }  // IF
    }  // FOR
    
    return costVertex;
}

void DijkstrasShortestPath(int sourceVertex){
    int costVertex,i,cost;
    minimumCosts[sourceVertex] = 0; // (First vertex should be 0)
    
    while ((costVertex = FindSmallestUnvisitedVertex()) != INVALID_VERTEX) {
        isVisited[costVertex] = VISITED;
        
        for (i = 0; i < VERTICES; i++) {
            if (costGraph[costVertex][i] != INF && isVisited[i] == UNVISITED) {
                cost = costGraph[costVertex][i];
                    
                        if(minimumCosts[costVertex] + cost < minimumCosts[i]){
                                       minimumCosts[i] = minimumCosts[costVertex] + cost;
                                       previousVertex[i] = costVertex;
                                   } // second if
            } // first if
        } // for
    } // while
}

void PrintPreviousVertex(){
    for (int i = 0; i < VERTICES; i++) {
        printf("V%d's Previous vertex is V%d\n", (i+1), (previousVertex[i] + 1));
    }
}

void PrintMinimumCosts(int sourceVertex){
    for (int i = 0; i < VERTICES; i++) {
        printf("V%d's minimum cost from %d is %d\n", (i+1), sourceVertex, minimumCosts[i]);
    }
}

void PrintPath(int vertex){
    if (vertex != INVALID_VERTEX) {
        PrintPath(previousVertex[vertex]);
        printf("V%d -> ", (vertex + 1));
    }
}


int main(){
    int i;
    int v1 = 0;
    InitializeData();
    DijkstrasShortestPath(v1);
    PrintMinimumCosts(v1);
    printf("-------------\n");
    PrintPreviousVertex();
    
    printf("-------------\n");
    printf("PATHS \n");
    for (i = 0; i < VERTICES; i++) {
        printf("PATH to reach V%d is ", (i+1));
        PrintPath(i);
        printf(" %d (Minimum cost) \n", minimumCosts[i]);
    }
    
}

Bir cevap yazın

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