다 익스트라 우선순위 큐 C 언어 - da igseuteula useonsun-wi kyu C eon-eo

프로그래밍/알고리즘 이론

우선순위 큐를 활용한 다익스트라 알고리즘 O(E log V)

restudy 2022. 3. 28. 13:51

일반적인 다익스트라 알고리즘의 경우 O(|V|^2 + |E|)이므로, 정점이나 간선의 수가 아주 많아지는 경우 시간 초과가 발생하여 문제를 풀 수 없는 경우가 있습니다.

그래서 여기서 개선된 방법이 바로 우선순위 큐(priority_queue)를 활용하여 다익스트라 알고리즘을 사용하는 방법입니다.

우선순위 큐를 활용하여 다익스트라 알고리즘을 사용하면, O(E log V) 시간에 최단경로를 찾을 수 있습니다.

그 이유는 기존 다익스트라 알고리즘의 경우 "특정 노드와 가장 거리가 짧은 노드"를 찾는 과정에서 매번 일일이 탐색하는 과정을 거쳐야 하는데, 우선순위 큐를 활용할 경우 top에서 그 값을 바로 빼올 수 있기 때문입니다.

물론 데이터를 힙에 저장하고 갱신하는 과정에서 log 시간이 걸리긴 하지만, 결과적으로는 훨씬 짧은 시간에 알고리즘을 수행할 수 있게 됩니다.

이를 구체적인 예시로 확인해보기 위해, 백준 Online Judge의 1504번 : '특정한 최단 경로' 문제를 풀이해보도록 하겠습니다.

BOJ 1504 특정한 최단 경로

E개의 간선들이 주어질 때, 1번 정점 → A번 정점 → B번 정점 → N번 정점으로 가는 경로와, 1번 정점 → B번 정점 → A번 정점 → N번 정점으로 가는 경로 중 최단 경로의 길이를 출력하는 문제입니다.

우선순위 큐를 활용한 다익스트라 알고리즘을 구현하여 문제를 풀이해보도록 하겠습니다.

#include <bits/stdc++.h>
#define MAX 805
using namespace std;

int N, E;
vector<pair<int, int>> adj[MAX];
int dist[MAX];

void Dijkstra(int start) {
    for(int i=1; i<=N; i++) dist[i] = INT_MAX;
    dist[start] = 0;

    priority_queue<pair<int, int>> pQueue;
    pQueue.push({0, start});

    while(!pQueue.empty()) {
        int dist1 = -pQueue.top().first;
        int curr = pQueue.top().second;

        pQueue.pop();

        for(int i=0; i<adj[curr].size(); i++) {
            int next = adj[curr][i].first;
            int dist2 = adj[curr][i].second;

            if(dist1 + dist2 < dist[next]) {
                dist[next] = dist1 + dist2;
                pQueue.push({-dist[next], next});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> E;

    for(int i=0; i<E; i++) {
        int a, b, c; cin >> a >> b >> c;

        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    int A, B; cin >> A >> B;

    int route1 = 0, route2 = 0;
    bool check1 = true, check2 = true;

    Dijkstra(1);
    if(dist[A] == INT_MAX) check1 = false;
    else route1 += dist[A];

    Dijkstra(A);
    if(dist[B] == INT_MAX) check1 = false;
    else route1 += dist[B];

    Dijkstra(B);
    if(dist[N] == INT_MAX) check1 = false;
    else route1 += dist[N];


    Dijkstra(1);
    if(dist[B] == INT_MAX) check2 = false;
    else route2 += dist[B];

    Dijkstra(B);
    if(dist[A] == INT_MAX) check2 = false;
    else route2 += dist[A];

    Dijkstra(A);
    if(dist[N] == INT_MAX) check2 = false;
    else route2 += dist[N];

    if(!check1 && !check2) cout << "-1";
    else if(!check1) cout << route2;
    else if(!check2) cout << route1;
    else cout << min(route1, route2);
}

이 문제의 경우 다익스트라 알고리즘을 여러 번 사용해야 합니다.

먼저 1번 정점에서 다익스트라를 사용한 뒤 A번 정점까지의 최단 거리와 B번 정점까지의 최단 거리를 구합니다.

그 다음 A번 정점에서 다익스트라를 사용하여 B번 정점까지의 최단 거리와 N번 정점까지의 최단 거리를 구해야합니다.

B번 정점에서도 마찬가지로 A번 정점까지의 거리와 N번 정점까지의 거리를 구해야합니다. (간선의 방향이 있으므로 B에서 A로 거리는 다를 수 있습니다.)

이제 위에서 구한 거리들을 합쳐서 두 경로 중 최단 경로의 길이를 구해주면 됩니다.

이 때 위의 경로들 중에서 INF로 초기화한 값들 중 갱신되지 않은 것이 있을 수 있는데 이것은 경로가 존재하지 않는 경우에 해당하므로, bool 변수를 적당히 활용하여 -1을 출력해줄 수 있도록 해주면 됩니다.

제출해보면 정답 처리를 받을 수 있습니다.

Applied/알고리즘

우선순위 큐 다익스트라 알고리즘(Dijkstra Algorithm)

가누 2016. 11. 21. 03:56

우선순위 큐 다익스트라 알고리즘의 코드 구현은 다음 책의 내용을 참조하였다.

http://book.naver.com/bookdb/book_detail.nhn?bid=7058764

923쪽, 다익스트라의 최단 거리 알고리즘의 구현

그리고 다익스트라 알고리즘이 진행되는 과정은 다음 게시물에 수록되어 있다.

http://www.crocus.co.kr/532 :: 다익스트라 개념

아래 내용을 통해 우선순위 큐 다익스트라 알고리즘의

개념 및 소스 코드를 확인하고, 이 코드를 이용해서 풀 수 있는 문제는 다음과 같다.

문제 원본 :: https://www.acmicpc.net/problem/1753

문제 풀이 :: http://programbasic.tistory.com/545

이 코드에서의 핵심은 다음과 같다.

1. priority_queue를 이용함으로써

즉, MinHeap(우선순위 큐)을 이용하여 시간 복잡도를 현저히 줄일 수 있게 되었다.

이때 log|V|가 되는 이유는 일반 다익스트라에서는 가장 최단 거리를 가진 정점을 찾기위해 선형 탐색을 이용하지만,

MinHeap을 이용하면 log|V|만에 최솟값이 가장 위로 올라오도록 정렬되기에 log|V|이다.

2. priority_queue에서는 기본적으로 가장 큰 원소가 pop의 우선순위를 가지기 때문에

가중치가 3, 2, 1이라는 값이 들어왔다면 우선순위는 3, 2, 1이아닌 1, 2, 3이어야 하기에

음의 가중치로 바꾸어 우선순위 큐에 넣는다.(-1, -2, -3으로)

3. A정점에서 B정점으로 가는 값이 이미 있는데 더 작은값이 생긴다면 

우선순위 큐에서 찾지 않고, 그냥 push한 후에, 나중에 가중치를 비교하여 

가중치가 더 큰 것이었다면 무시하도록 한다. 

아래 그림을 통해 우선순위 큐의 알고리즘이 어떻게 작동하는지 확인하자.

(a~d까지를 확인)

1) a번 정점에서 시작한다고 가정한다.

2) a번 정점은 시작점이므로 0의 최단 거리 값을 가지게 된다.

현재 dist 값 (a번 순서로 0,1,2,3 으로 간다고 가정)

dist[0] = 0

3) a번 정점에서 c번 정점으로의 최단 거리는 1임을 알 수 있다.

dist[0] = 0

dist[2] = 1

4) a번 정점에서 b번 정점으로의 최단 거리는 5임을 알 수 있다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

5) a번 정점에서 가장 최단거리는 c이므로 c부터 방문한다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

6) c번 정점에서 d까지의 최단거리는 3이다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

dist[3] = 3

7) c번 정점에서의 방문이 끝났으니 그다음 가장 최단 거리를 가진 d번 정점을 방문한다.

dist[0] = 0

dist[1] = 5

dist[2] = 1

dist[3] = 3

8) d번 정점에서 b정점까지의 최단거리는 5에서 4로 변한다. 

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

여기서 아래의 코드에 의해 5가 아닌 4로 갱신됨을 알 수 있다.

8-1) 만약 d->b의 가중치를 4라고 하자.

a번 정점에서 b번 정점으로 갈 때 최단거리는 7이라고 알고있었지만,

a->b의 5라는 가중치가 존재하고 있다.

따라서 그림 아래의 알고리즘을 통해 비교가 된다.

결국 7 > 5이므로 업데이트 된다. (그림의 내용 참조)

현재 dist 값 (a번 순서로 0,1,2,3 으로 간다고 가정)

dist[0] = 0

dist[1] = 5 (7->5로 바뀜)

dist[2] = 1

dist[3] = 3

9) d번 정점에서 e정점까지의 최단거리는 8이다. 

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

dist[4] = 8

10) b번 정점에서 인접한 정점은 없으므로 그대로 있는다.

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

dist[4] = 8

11) e번 정점에서 인접한 정점은 없으니 그대로 있는다. 

dist[0] = 0

dist[1] = 4

dist[2] = 1

dist[3] = 3

dist[4] = 8

< 소스 코드 >