Algorithm/알고리즘_개념

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

레에몽 2021. 3. 24. 13:36

 그래프에서 최소 비용을 탐색하는 알고리즘으로는 다익스트라 알고리즘, 벨만 포드 알고리즘, 플로이드 와샬 알고리즘, SPFA 알고리즘 등이 있다. 이 글에서는 다익스트라 알고리즘에 대해 다룬다.

 

 다익스트라 알고리즘은 정해진 노드에서 다른 모두의 노드까지 최소 비용을 구하는 알고리즘이다. 다익스트라는 Greedy하게 작동한다고 생각하자.

 

 작동 과정

1. 정해진 노드가 들어가있는 모든 간선 중에서 제일 비용이 낮은 간선을 선택하여 다음 노드를 활성화 시킨다.
2. 정해진 노드와 다음 노드가 포함되어 있는 모든 간선 중에서 제일 비용이 낮은 간선을 선택하여 또다른 노드를 활성화 시킨다.
3. 이를 계속해서 반복한다.

 다익스트라는 생각보다 간단하다. 단순하게 "활성화 되어 있는 간선 중 제일 비용이 낮은 간선"을 선택하는 Greedy 알고리즘이다. 사실, 위의 설명이 정확한 것은 아니다. 2번의 작동과정을 조금 더 구체적으로 설명하겠다.

 

 GIF파일과 같이 확인해보자.

출처 : 위키백과

 (1) 과정에 의해서 시작점 노드1로부터 3개의 간선이 활성화 된다.

E1 : 1->6 비용 14,   E2 : 1->3 비용 9,   E3 : 1->2 비용 7. 이라고 지칭하겠다.

Greedy한 방법으로 작동하므로, E3이 선택하여 두 개의 간선이 더 활성화 된다.(E4 : 2->3 비용 10, E5 : 2->4 비용 15)

 

 자, 여기서 잠시 멈춰서 생각을 해보자. 아까 다익스트라 알고리즘의 정의를 얘기할 때 "정해진 노드"에서 "모든 다른 노드"로 가는 최소비용을 구한다고 했다. 여기서 정해진 노드는 노드1이다.

 위의 기재한 과정에서는 노드1에서 노드2로 가는 최소비용인 7을 구한 것이다. 그러면 여기서 문제. 노드1에서 노드3으로 가는 방법은 몇개가 있을까?

 

 현재 활성화 되어 있는 노드는 노드1, 노드2가 전부다. 노드1에서 노드3으로 가려면 간선을 1개 선택해서 직접 가는 방법(E2)이 있고, 노드1에서 노드2를 거쳐서 노드3으로 가는 간선을 2개 선택하는 방법(E3, E4)이 있다.

 여기서 비교를 해주는 것이다. E2의 비용과 E3 + E4의 비용을 비교하면 E2의 비용이 더 작다. 그렇기에 E2를 선택해서 노드3을 활성화 시키는 것이다.

 

 작동과정 중 2번을 진행할 때에는 다음 노드로 가는 여러 가지의 방법 중 비교해서 한 개의 방법을 선택해서 가야 한다.

 

 

 코드로 구현하기 전에 여기서는 우선순위 큐(Priority_Queue)를 사용할 것이다. 우선순위 큐는 쉽게 MaxQ와 MinQ로 나누어서 생각을 하면 되는데 최소 비용을 선택하기 위해서는 MinQ(작은 것부터 나오는 Queue)를 선택하면 된다. 하지만, C++에서 우선순위 큐의 Default는 MaxQ가 나오기 때문에 코드의 낭비를 줄여 MaxQ에서 작은 값이 먼저 나오게 만들어 보자.

 

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
vector<pair<intint>> tree[20001]; // node - child&cost
priority_queue<pair<intint>> pq; // cost&node
 
vector<int> dijkstra(int node){
    vector<int> cost(N+1, INT_MAX); // 노드가 선택되지 않아 시작 노드에서 다른 노드의 모든 거리를 MAX로 초기화
   cost[node] = 0// 자기 자신으로 가는 비용은 0
    pq.push({node, 0}); // 자기 자신부터 우선순위 큐를 순회
 
    while (!pq.empty()) {        
        int nowCost= -pq.top().first; // pq는 기본 내림차순 정렬이므로 부호를 반대로 넣고, 반대로해서 빼면 오름차순 정렬을 할 수 있다. 
        int nowNode = pq.top().second;
        pq.pop();
 
        // 이어진 값보다 기존값을 쓰는게 빠르므로 넘긴다.
        if (nowCost> cost[nowNode]) {
            continue;
        }
 
        //현재 node와 연결되있는 점을 모두 탐방한다
        for (int i = 0; i < tree[nowNode].size(); i++) {
            int nextNode = tree[nowNode][i].first; // child
            int nextCost = tree[nowNode][i].second; // cost
 
            // dist를 갱신할 수 있으면 갱신하고 push한다.
            if (nextCost + nowCost < cost[nextNode]) {
               cost[nextNode] = nextCost + nowCost;
 
                pq.push({ -cost[nextNode], nextNode });
            }
        }
    }
 
    return cost;
}
cs

 

 코드가 막 길지 않다. 여기서 pq를 node - cost순으로 사용하게 되면 default값에 의해 node순으로 정렬됨을 명심하자. pq를 cost로 정렬을 하는데 maxQ의 성질을 반대로 넣으려면 거리에 '-'부호를 넣으면 된다. 음수의 성질에 의해서 음수끼리 비교 연산은 "절댓값이 낮을 수록 크다." pq에 넣을 때 '-'부호를 사용하고, pq에서 뺄 때 '-'를 다시 붙여 양수로 만들어준다면 절댓값이 낮은 수 -> 양수 기준에서 최소값이 나오게 됨을 볼 수 있다.

 

 혹시 여기서 tree에서 cost값을 뺄 때 '-'를 왜 안붙일까라고 생각하면 글을 다시 읽어보자. 

 

 만약에 minQ로 선언해서 사용하고 싶으면 아래와 같이 코드를 작성하자.

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; // value&node

 

 이것도 아니라, tree구조와 통일되게 node & value 순으로 만들고 싶으면 greater대신에 구조체를 만들어 cmp를 하나 만들어주자. 

struct Edge
{
	int node, cost;
};

struct cmp {
	bool operator()(Edge &node, Edge &cost) {
    	if(a.cost == b.cost){
        	return a.node < b.node; // x의 값이 오른쪽으로 갈수록 커지게
        }
		return a.cost < b.cost; // y의 값이 오른쪽으로 갈수록 커지게
	}
};

priority_queue<Edge,vector<Edge>, cmp > pq;