다익스트라(Dijkstra) 정확성 증명

앞서 최단거리 알고리즘으로 Prim, Kruskal 을 다뤄보았다.

이번 포스팅에서 다룰 Shortest Path 알고리즘은 다익스트라(dijkstra)이다.

다익스트라 알고리즘이 왜 정확한지 정확성 증명을 해보고, 코드로 구현을 해보겠다.

 

Dijkstra Algorithm 정확성 증명

• Source 노드에서 시작
• 각 노드에 적힌 숫자는 source 노드와의 최단거리를 나타낸다.
• 정답을 찾아가면서 이 노드들의 숫자를 update 하면 된다.

다익스트라의 특징

• 모든 노드에서 시작점까지의 최단 거리를 구할 수 있다.
• 단순히 거리만 구하는 것이 아니라, 지나온 경로도 알 수 있다. (백 트래킹)

 

진행 방법

위처럼 노드들이 있고, 노드마다 적힌 숫자는 시작 노드와의 최단거리를 나타낸다.

 

빨간 영역은 알고리즘에 의해 확정된 값으로, 정답이다. 

파란 영역은 빨간 영역에 포함되지 않은 곳이다.

• 빨간 영역의 숫자 : 알고리즘이 구한 값으로, 정답.
• 파란 영역의 숫자 : source 로부터의 최단 거리

 

단 파란영역에 적힌 숫자는 빨간 영역에서 인접한 edge 들로 갱신된 값이다.

즉, 다른 파란영역간의 경로는 고려하지 않은 것이다. 

 

알고리즘은 실행하면서 빨간색 영역을 하나씩 늘려나간다. 모든 노드가 빨간 영역에 들어오게 되면 그것이 최종 답이다.

 

 

빨간색 영역 갱신 방법

• 파란 영역의 값 중 최소값을 빨간 영역에 포함시킨다. 
• 15 가 빨간 영역에 들어오면 나머지 파란영역 값(17, 19, 20)을 노드 15를 지나는 간선과 거리를 비교해 갱신한다.

얼핏 들어서는 이해가 가지 않는데, 차근차근 알아보자.

 

 

Why?

왜 파란 값 중 최솟값을 가진 노드를 빨간색에 포함시킬까?

위 그림에서 파란 영역에 있는 노드 중 최소값은 15이다.

노드에 적힌 값은 현재 상황에서 Source 까지의 최단거리를 의미한다.

 

시작 노드에서 15가 적힌 노드까지 가려면, edge 가 빨간색 영역 -> 파란색 영역 으로 넘어와야 한다.

source 노드에서 15가 적힌 노드까지의 경로들 중 빨간색 영역 안에서의 경로는 알 수가 없다. (8을 지나든, 10을 지나든...)

하지만 15가 적힌 노드에 도달하려면 빨간색 영역에서 파란색 영역으로 넘어와야 한다는건 자명하다.

 

결국 빨간색 영역을 넘은 edge는 다이렉트로 15 노드로 연결되어야 한다.

파란색 영역의 다른 노드를 거쳐오는게 더 짧을수도 있잖아요?

=> 그럴수는 없다. 고른 15가 적힌 노드는 blue 영역의 최솟값이기 때문에 파란 영역의 다른 노드를 거쳐오게 되면 무조건 15보다 거리가 크게 나온다. 따라서 다이렉트로 와야한다.

 

따라서 15가 적힌 노드를 빨간 영역으로 포함시켜 갱신한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

들어간 15가 적힌 노드를 기준으로 다른 노드와의 direct edge 비교.

이 작업을 blue 영역의 모든 노드에 적용한다. 

 

In Node P:

15 + w(e) > w(p) : 원래 길이가 더 짧으므로 유지

15 + w(e) < w(p) : 원래 길이가 더 길므로 갱신.

 

 

왜 15가 적힌 노드와의 direct edge 값을 비교할까?

red 영역안의 다른 노드(0, 8, 10...)를 통해 나오는 가중치 값은 이미 적힌 값에 포함되어 있다.

원래 노드에 적힌 17, 19, 20 은 15가 적힌 노드를 거치지 않고 구해진 값이라는 뜻.

따라서 새로 빨간 영역에 편입된 노드 15 를 거쳐가는 값과 비교해서, 더 작은 값으로 갱신한다는 것이다.

 

그럼 15를 거치고 다른 노드를 거쳐올수도 있지않나?

=> 그럼 거리가 더 길어지므로, 고려대상이 아니다... (direct edge 만 고려)

 

이런식으로 다소 난해하지만 답이 갱신되는 과정을 살펴보았다.

알고리즘이 구한 빨간 영역에 파란 영역의 가중치가 가장 작은 노드를 포함시키고, 빨간 영역 갱신.

직전에 들어간 노드와 direct edge 값을 계산해 더 작은 값으로 갱신. 그렇게 해야하는 이유를 보였다.

 

구현

#include <iostream>
#include <vector>
#define INF 1000000
using namespace std;

class TREE{
public:
    int a; // 시작 노드
    int b; // 도착 노드
    int w; // edge 값(무게)
};

class PQ{
public:
    TREE arr[1001]; // 1 ~ 1000개까지 가능
    int n;
    PQ();
    void insert(TREE x);
    TREE Delete();
    void swap(int index);
    int isEmpty();
};

PQ::PQ(){
    n = 0;
}
int PQ::isEmpty(){
    return n==0;
}

void PQ::swap(int idx){
    TREE tmp = arr[idx];
    arr[idx] = arr[idx/2];
    arr[idx/2] = tmp;
}

void PQ::insert(TREE x){
    int i, tmp;
    arr[n+1] = x;
    i = n +1;
    while(i>1 && arr[i].w < arr[i/2].w){
        swap(i);
        i /= 2;
    }
    n++;
}

TREE PQ::Delete(){
    TREE ret = arr[1];
    if(n==1) { n=0; return ret;}
    int i;
    // 트리의 맨 나중의 원소 값을 맨 꼭대기에 저장.
    arr[1] = arr[n];
    i = 1; n = n-1; 

    while(1){
        if(2*i > n) // no child
            break;
        else if(2*i+1 >n){ // only left child
            if(arr[2*i].w < arr[i].w){
                swap(2*i);
                i = 2*i; // 한칸 내려감
            }
            else break;
        }
        else{ // left, right child
            int cur = arr[i].w;
            int l = arr[2*i].w, r = arr[2*i+1].w;
            if(cur > l && cur > r){
                int j = 0;
                if(l < r) j = 2*i;
                else j = 2*i + 1;
                swap(j);
                i=j;
            }
            else if(cur > l && cur <= r){
                swap(2*i);
                i = 2*i;
            }else if(cur <= l && cur > r){
                swap(2*i+1);
                i = 2*i+1;
            }
            else
                break;
        }
    }

    return ret;
}

PQ pq;
vector<pair<int, int>> edges[1000];
int M[1000]; // shortest path length

int main(){
    int n, m, c; // node, edge, curNode
    cin >>n >>m;
    for(int i=0;i<m;i++){ // O(M)
        int a,b,w;
        cin >> a >>b >>w;
        edges[a].push_back(make_pair(b,w));
        edges[b].push_back(make_pair(a,w));
    }
    for(int i=1; i<=n; i++)
        M[i] = INF;
        
    // 1번을 source라 가정.
    c = 1; M[1] = 0;

    for(int i=0;i<edges[c].size();i++){
        TREE x;
        x.a = c;
        x.b = edges[c][i].first;
        x.w = M[c] + edges[c][i].second;
        pq.insert(x);
        printf("(%d , %d) : %d\n",x.a,x.b,x.w);
    }

    while(!pq.isEmpty()){
        TREE y = pq.Delete();
        TREE tmp;
        if(M[y.b] < INF){ 
            continue;
        }else{
            printf("edge from Node %d to Node %d of Total Path length %d Selected.\n",y.a, y.b, y.w);
            c = y.b; // curNode
            M[c] = y.w;

            for(int i=0;i<edges[c].size();i++){
                tmp.a = c;
                tmp.b = edges[c][i].first;
                tmp.w = M[c] + edges[c][i].second;
                pq.insert(tmp);
            }
        }
    }
    return 0;
}

구현은 우선순위 큐를 써서 했다. 가중치가 낮은 값을 우선순위로 골라 정답 영역에 포함시켜야 하기 때문.

따라서 이 알고리즘도 그리디(Greedy)이다.

앞선 Prim, Kruskal 과 구현은 비슷하다고 볼 수 있다.