[자료구조]다익스트라 알고리즘(Dijkstra Algorithm)

가정

'그림'과 같이 방향이 없는 weighted edge로 구성된 그래프라고 가정한다.

방향이 있는 edge도 가능하다.

결과

내가 정한 시작 노드 한 개에서 모든 노드로 가는 가장 빠른 길과 cost를 알 수 있다.

 

과정

초기화

먼저 시작 노드를 정한다. (나는 U라고 정했다.)

U에 인접한 노드들의 distance를 저장해준다.

 

루프

저장한 노드들 중에 가장 빠르게 갈 수 있는 노드를 고른다. 그리고 그 노드에서 갈 수 있는 길들을 찾아서 업데이트 해준다.

(기존 distance와 새로 찾은 node를 통해서 가는 것중에 짧은 distance로 업데이트 한다. distance = min(저장된 값, 새로 찾은 노드까지 가는 값 + 새로운 노드에서 원하는 노드까지 거리))

 

모든 노드를 방문할때까지 반복.

시간복잡도

처음에는 N개 노드 확인, 그 다음에는 N-1개 노드 확인... 하다가 1개 확인하므로 N(N+1)/2 -> O(N^2)

 

* heap에서 sort함수를 사용하면 O(N*logN)으로 줄어들 수 있다.

 

코드 (C++)

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];
                    
                }
            }
        }
        
    }
}