[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

반응형

 

다익스트라 알고리즘

다음과 같은 도시들과 그 도시들끼리 이어주는 도로망이 있다고 해보자.

A 도시에서 F 도시를 방문한다고 하자. 최단 거리를 찾아서 방문한다면 시간이 절약될 것이다. 그러므로, C 도시를 거쳐서 F 도시로 가는 것이 가장 짧은 경로이다. 이때의 거리는 도로의 길이의 합이 가장 짧은 60km가 된다.

 

가중치 그래프에서도 마찬가지이다. 한 정점 v에서 각 정점들까지의 최단 경로를 구하고자하는 경우가 있다. v에서 각 정점까지의 가중치들을 더하고, 그 가중치가 가장 작으면 최단 거리가 된다. 이렇게 한 시작 정점 v에서 모든 다른 정점들 까지의 최단 경로를 구하는 알고리즘이 다익스트라 알고리즘(Dijkstra Algorithm)이다. 단, 모든 가중치가 음수가 아닐 경우에 사용이 가능하다.

 

---

 

Dijkstra Algorithm

모든 가중치가 0 이상인 가중치 그래프 \(G = (V, E)\) 에 대해

1. 시작 정점\(r\)을 0으로, 나머지 정점들까지의 최단 거리는 무한대로 한다.
2. \(r\)을 방문한 정점의 집합 \(S\)에 넣는다.
3. \(r\)과 집합 \(S\)에 포함되지 않은 정점들과의 거리를 계산한다.
4. 계산된 거리 중 더 작은 값으로 최단 거리를 갱신한 후, 가장 작은 정점을 집합 \(S\)에 포함시킨다.
5. 모든 정점이 집합 \(S\)에 속할 때 까지 3~4를 반복한다.

 

출처 : 위키백과 데이크스트라 알고리즘

 

int dist[MAX_VTX];
bool found[MAX_VTX];

// 집합 S에 속하지 않은 정점들 중에서 현재의 거리가 가장 작은 정점 선택
int choose_vertex() {
    int min = INF;
    int minpos = -1;
        
    for (int i = 0; i < vtxsize; i++) {
        if (dist[i] < min && found[i] != true) {
            min = dist[i];
            minpos = i;
        }
    }
    
    return minpos;
}

void dijkstra(int start) {
    // 초기화
    for (int i = 0; i < vtxsize; i++) {
        dist[i] = grp[start][i];
        found[i] = false;
    }
    found[start] = true;
    dist[start] = 0;
    
    // 모든 정점이 집합 S에 속할 때 까지 반복
    for (int i = 0; i < vtxsize - 1; i++) {
        int u = choose_vertex();
        found[u] = true;
        
        // 더 작은 값으로 최단 경로 갱신
        for (int w = 0; w < vtxsize; w++) {
            if (found[w] == false) {
                dist[w] = min(dist[w], dist[u] + grp[u][w]);
            }
        }
    }
}

시간 복잡도는 for문이 외부에서 \(n\)번, 내부에서 \(2n\)번으로 \(O(n^2)\)이 된다. 힙을 이용하게 된다면 \(O(ElogV)\)로 단축시킬 수 있다.

힙을 이용한 다익스트라 (우선순위 큐 사용)

void dijkstra(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push({ 0, Start });
    dist[Start] = 0;

    while (!pq.empty()) {
        int weight = -pq.top().first;
        int node = pq.top().second;
        pq.pop();

        for (int i = 0; i < Vertex[node].size(); i++) {
            int next = GRP[node][i].first;
            int next_w = GRP[node][i].second;

            if (dist[next] > weight + next_w)
            {
                dist[next] = weight + next_w;
                pq.push({ -dist[next], next });
            }
        }
    }
}

 

 

 

[Reference]

문병로, 「쉽게 배우는 알고리즘」 (한빛 아카데미, 2018)

 

 

728x90