[Algorithm] 다익스트라 알고리즘(priority_queue 적용)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

ㅇ 다익스트라 알고리즘

  - 간선값이 양수일 때만 적용

먼저 인접 리스트를 그려본다.

1	(2,12) -> (3,4)
2	(1, 2) -> (3,5) -> (5,5)
3	(4,5)
4	(2,2) -> (5,5)
5
6	(4,5)

 

그리고 1번 정점에서 i번 정점으로 가는데 최소 비용을 저장하는 dist[] 배열도 필요하다.

우리는 최소 거리비용을 구해야하므로 초기값은 최대한 큰 값으로 초기화시켜준다.

dist[]

1	2	3	4	5	6
2147000000	2147000000	2147000000	2147000000	2147000000	2147000000

방문한 정점을 체크하는 배열도 필요할 것 같다.

ch[]

1	2	3	4	5	6

먼저 1번 정점에서 시작하므로

dist[1] = 0 으로 하고 시작하자.

dist[]

1	2	3	4	5	6
0	2147000000	2147000000	2147000000	2147000000	2147000000

dist[] 에서 최솟값을 찾아보자.

정점 1의 거리 1이 최솟값이다.

그럼 정점 1과 연결된 정점들에 1부터의 거리를 저장한다.

정점 1은 (2,12), (3,4) 와 연결되어있으므로,

dist[2] = dist[1] + 12

dist[3] = dist[1] + 4

가 된다. 이 값들은 기존 dist[2], dist[3] 과 비교해서 작다면 값을 수정해주고 작지 않다면 pass 해주면 된다.

기존 dist[2] 와 dist[3] 은 2147000000 으로 저장되어있으므로 

아래와 같이 dist 배열이 수정된다.

그리고 1번 정점은 방문했으므로 체크하해주자.

dist[]

1	2	3	4	5	6
0	12	4	2147000000	2147000000	2147000000

ch[]

1	2	3	4	5	6
1

또 dist[] 에서 최솟값을 찾는데 방문했던 정점은 제외한다.

그러면 3번 정점이 되겠다.

3번 정점과 연결된 정점은 (4,5) 이다.

그렇다면 dist[4] = dist[3] + 5 가 되어서

아래와 같이 될 것이다. 

마찬가지로 3번 노드도 방문했으니 check!

dist[]

1	2	3	4	5	6
0	12	4	9	2147000000	2147000000

ch[]

1	2	3	4	5	6
1		1

다음 단계까지 해보자.

dist[] 에서 아직 방문하지 않은 정점의 최솟값은 정점 4이다.

정점 4와 연결된 정점은 (1, 2), (3,5), (5,5)이다.

dist[2] = dist[2] > dist[4] + 2 ? dist[4] + 2 : dist[2];

dist[5] = dist[5] > dist[4] + 5 ? dist[4] + 5 : dist[5];

가 되어 아래처럼 수정될 것이다.

그리고 4번 노드를 방문했으므로 체크해준다.

dist[]

1	2	3	4	5	6
0	11	4	9	14	2147000000

ch[]

1	2	3	4	5	6
1		1	1

진짜 마지막!으로 

dist[] 에서 아직 방문하지 않은 정점의 최솟값은 정점 2이다.

정점 2와 연결된 정점은 (1, 2), (3,5), (5,5) 이다.

dist[1] = dist[1] > dist[2] + 2 ? dist[2] + 2 : dist[1];

dist[3] = dist[3] > dist[2] + 5 ? dist[2] + 5 : dist[3];

dist[5] = dist[5] > dist[2] + 5 ? dist[2] + 5 : dist[5];

가 되어 아래처럼 수정될 것이다.

그리고 2번 노드를 방문했으므로 체크해준다.

dist[]

1	2	3	4	5	6
0	11	4	9	14	2147000000

ch[]

1	2	3	4	5	6
1	1	1	1

이와 같은 방법으로 남은 과정도 진행된다.

그런데 여기서 포인트!

dist[] 에서 방문하지 않은 최솟값을 탐색하기 위해 priority_queue 를 사용한다면 O(logN) 만에 수행할 수 있다는 것이다.

만일 priority_queue 를 사용하지 않는다면 매 탐색마다 N만큼 반복하면서 최솟값을 찾을 것이다.

#. Code

구현 능력을 키우기 위해 위 과정을 코드로 옮겨보았다.

뭔가 굉장히 복잡해보이네..

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
int ch[21];
 
struct Info
{
    int v;
    int w;
    Info(int a, int b)
    {
        v = a;
        w = b;
    }
    bool operator<(const Info& b) const
    {
        return w > b.w;
    }
};
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, m, i, j, a, b, c;
 
    scanf("%d %d", &n, &m);
    vector<int> dist(n + 1, MAX);
    vector<pair<int, int> > gl[21];
    priority_queue<Info> pQ;
 
    for (i = 0; i < m; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
 
        gl[a].push_back({ b, c });
    }
 
    dist[1] = 0;
    for (i = 1; i <= n; i++)
        pQ.push(Info(i, dist[i]));
 
    for (i = 1; i <= n; i++)
    {
        Info tmp = pQ.top();
        pQ.pop();
 
        int tmpx = tmp.v;
        int tmpw = tmp.w;
 
        for (j = 0; j < gl[tmpx].size(); j++)
        {
            int f = gl[tmpx][j].first;
            int s = gl[tmpx][j].second;
 
            if (dist[f] > dist[tmpx] + s)
            {
                dist[f] = dist[tmpx] + s;
 
                pQ.push(Info(f, dist[f]));
            }
        }
 
        ch[tmpx] = 1;
    }
 
 
    for (i = 2; i <= n; i++)
    {
        if (dist[i] != MAX)
            printf("%d : %d\n", i, dist[i]);
        else
            printf("%d : impossible\n", i);
    }
 
    return 0;
}

line 9~22) 도착 정점과 가중치를 priority_queue 에 넣을 건데, 가중치 기준 최소힙으로 트리를 구성하기 위해 

             구조체를 만들었다.

line 31) 거리는 모두 max 로 초기화

line 35~40) 방향 인접 리스트를 생성

line 42) 초기 시작 정점은 1 이므로 dist 1 의 최소 거리는 0 으로 수정

line 43~44) priority_queue 에 dist 정보를 push 

line 46~68) 총 N 만큼 반복

line 48~52) 최소 거리를 가진 구조체를 꺼내고 해당 구조체의 정점과 가중치를 저장

line 54~65) 해당 정점과 연결된 정점 개수만큼 반복

line 56~57) 해당 정점과 연결된 정점의 번호와 가중치를 저장

line 59~64) 해당 정점과 연결 정점을 연결했을 때 연결 정점이 최소 거리를 갖는다면

    연결 정점의 최소 거리를 수정하고 수정된 연결 정보를 priority_queue 에 push 해준다.

line 67) 해당 정점의 동작을 모두 완료하였으면 check!

뭔가 많이 부족해보이지만.. 그래도 나름대로 구현해보았다.

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include<stdio.h> #include<vector> #include <queue> #include<algorithm> #define x first #define y second using namespace std;   struct Edge {     int vex;     int dis;     Edge(int a, int b)     {         vex = a;         dis = b;     }     bool operator<(const Edge& b) const     {         return dis > b.dis;     } };   int main() {     freopen("input.txt", "rt", stdin);     priority_queue<Edge> Q;     vector<pair<int, int> > graph[30];     int i, n, m, a, b, c;       scanf("%d %d", &n, &m);     vector<int > dist(n + 1, 2147000000);     for (i = 1; i <= m; i++) {         scanf("%d %d %d", &a, &b, &c);         graph[a].push_back(make_pair(b, c));     }       Q.push(Edge(1, 0));     dist[1] = 0;          while (!Q.empty())     {         int now = Q.top().vex;         int cost = Q.top().dis;         Q.pop();           if (cost > dist[now]) continue;         for (i = 0; i < graph[now].size(); i++)         {             int next = graph[now][i].first;             int nextDis = cost + graph[now][i].second;             if (dist[next] > nextDis)             {                 dist[next] = nextDis;                 Q.push(Edge(next, nextDis));             }         }       }       for (i = 2; i <= n; i++) {         if (dist[i] != 2147000000) printf("%d : %d\n", i, dist[i]);         else printf("%d : impossible\n", i);     }     return 0; } Colored by Color Scripter

cs

사실상 check 배열이 필요가 없었고, 초기 MAX 거리를 priority_queue 에 넣어줄 필요가 없었다.

어차피 안 쓰일 것들이므로.. 

이거 말고도 참고하고 적용시켜야 할 부분이 많은 것 같다.. 하핳

line 9~22) 구조체 생성 부분은 동일하다. 다만 구조체 이름과 변수를 좀 더 보기 쉽게 작명해야겠다.

line 37) 시작 정점 1은 1까지의 거리가 0 이므로 (1,0) 을 queue 와 dist[] 에 저장해준다.

line 40~58) 이 부분이 다익스트라의 핵심 코드이다. queue 가 빌 때까지 반복

line 42~44) queue의 top() 원소를 저장하고 빼냄

line 46) 이 부분은 최적화 방법이 적용된 것이다. 

          queue에서 빼낸 cost 정보가 기존 cost 정보보다 크다면 아래 for 문을 동작해봐야 소용이 없으므로

          불필요한 연산을 최소화 시켜준 것이다.

line 47~56) 여기서 해당 정점과 연결된 정점의 수만큼 반복

line 49~50) 연결된 정점 번호와 거리 비용을 저장

line 51~55) 새로 계산된 거리 비용이 기존 거리 비용보다 작다면, 새로 계산된 거리 비용을 dist[] 배열에 저장

               변경된 정보를 queue 에 push 

비록 내 코드가 부족한 부분이 많았지만.. 

그래도 구현해보면서 어떤 부분이 부족했는지 캐취해낼 수 있었다.

#. Result

  - Input --------------------------------------------------------

6 9 

1 2 12 

1 3 4 

2 1 2 

2 3 5 

2 5 5 

3 4 5

4 2 2 

4 5 5 

6 4 5

------------------------------------------------------------------

  - Output --------------------------------------------------------

2 : 11 

3 : 4 

4 : 9 

5 : 14 

6 : impossible

------------------------------------------------------------------