[ Algorithm ] Dijkstra's Algorithm?

Dijkstra's Algorithm 이란?

       최단 경로(Shortest Path) 탐색 알고리즘이다. 한 정점(Vertex)에서

       다른 정점(Vertex)까지의 최단 경로를 구하는 알고리즘 중 하나이다. 최단 경로(Shortest Path)를 찾는 과정에서, 도착 정점(Vertex)        뿐만 아니라, 다른 정점(Vertex)까지 최단 경로로 방문하여, 각 정점(Vertex)까지의 최단 경로를 찾게 됩니다.

 

      시간복잡도 (Time Complexity)

            - using priority queue case : O(ElogE)

            - common case : O(n^2)

Dijkstra's Algorithm 동작

       1. 시작 정점(Vertex)를 설정합니다. (시작 정점(Vertex) 비용 : 0)

       2. 시작 정점(Vertex)과 인접한 정점(Vertex)중에서, 최단 거리가 가장 짧은 정점(Vertex)을 선택합니다.

       3. 해당 정점(Vertex)을 거쳐서, 다른 정점(Vertex)으로 가는 비용을 게산하여, 최단 거리 배열을 갱신합니다.

       4. 위 2 ~ 3 과정을 도착 정점(Vertex)까지 반복합니다.

Dijkstra's Algorithm code with C/C++

int choose(int distance[], int n, int found[]){
    int i, min, minpos;		// 아직 방문하지 않은 smallest distance를 찾습
    min = INT_MIN;
    minops = -1;
    
    for (i = 0; i < n; i++) {
        if (distance[i] < min && !found[i]) {
            min = distance[i];
            minops = i;            
        }    
    }
    
    return minops;
}

void shortestPath(int v, int cost[][MAX_VERTICES], int distance[], int n, short int found[]) {
    int i, u, w;
    for (i = 0; i < n; i++) {
        found[i] = False;
        distance[i] = cost[v][i];
    }    
    
    found[v] = TRUE; distance[v] = 0;
    for (i = 0; i < n-2; i++) {
        u = choose(distance, n, found);
        found[u] = TRUE;
        for (w = 0; w < n; w++) {
            if (!found[w]) {		// 만약 방문하지 않았다면, 최단경로 갱신
                if (distance[u] + cost[u][w] < distance[w])
                    distance[w] = distance[u] + cost[u][w];
            }
        }
    }    
}

Author's GitHub

https://github.com/kalelpark