[ DP ] Dijkstra Algorithm

금일은 다익스트라 알고리즘에 대하여 자세히 알아보자. 다익스트라 알고리즘은 Dynamic Programming을 활용한 최단 경로 탐색 알고리즘이다. 다익스트라를 DP를 활용하여 접근할 수 있는 이유는 최단 경로는 각각의 최단 경로를 포함하고 있기 때문이다. 따라서 이전까지 계산해 둔 최단 경로를 사용하여 하나의 최단 거리를 구한다.

 

기본적은 다익스트라 알고리즘의 프로세스는 다음과 같다.

 

1. 출발 노드 설정 

2. 출발 노드를 기준으로 각 노드의 최소 비용 저장

3. 방문하지 않은 노드 중 최소 비용 노드 설정

4. 해당 노드를 경유해서 특정한 노드로 가는 경우를 고려해 최소 비용 갱신

5. 2~4번 과정 반복

 

 

위와 같은 그래프가 주어졌다고 하자. 각 노드사이로 연결 된 간선은 비용을 의미한다. 각 문제에 따라서 모든 노드에서 마지막 노드로 가는 최소 비용을 구하거나, 특정한 노드에서 마지막 노드로 가는 최소 비용을 구하는 등 변형이 가능하다.

 

1번 노드가 시작 출발 노드, 도착 노드는 4번 노드라고 가정하자. 그러면 우리는 다음과 같은 Table을 생성할 수 있다. 

 

 

위 테이블은 행 인덱스에서 열 인덱스로 가는 최소 비용을 의미한다. 자기 자신으로 가는 경우는 없으니 0으로 설정 하였지만, 코드적으로 구현할 때는 최소 비용을 고려해야 하기 때문에 똫같이 무한대로 설정하는 것이 편하다. 따라서 현재 최소 비용은 다음과 같다.

 

0

3

6

7

 

1번 노드에서 방문할 수 있는 2,3,4번 노드에 대하여 최소 비용은 2번 노드이다. 따라서, 2번 노드를 경유해서 가는 경우를 고려한다면, 1->2->3번 노드의 경우 비용이 4로, 기존 비용인 6보다 작다. 따라서 최소 비용이 갱신된다.

 

0

3

4

7

 

그 다음으로 비용이 적은 3번 노드를 살펴보자. 3번 노드를 경유해서 가는 경우 1 -> 3 -> 4번 노드의 경우 비용이 5로 기존 비용인 7보다 작다. 따라서 최소 비용이 갱신된다.

0

3

4

5

 

마지막으로 4번 노드를 살펴보자. 4번 노드를 경유해서 가는 경우, 1 -> 4 -> 3을 생각 해 볼 수 있는데, 이는 기존 비용인 4보다 더 크기 때문에 갱신되지 않는다. 

 

따라서 우리는 1에서 4번 노드로 가는 최소 비용인 5를 적절하게 계산할 수 있다. 이를 코드적으로 살펴보면 다음과 같다.

 

int32_t DoDijkstra(int32_t s32_StPnt, int32_t s32_DstPnt)
{
    // 최소 거리 배열 Infinite Value로 초기화 
    fill(ars32_MinDist, ars32_MinDist + 1002, C_INFINITE);
    // greater -> MinHeap
    // { Distance , Node }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st_PQ;

    st_PQ.push({ 0, s32_StPnt });
    ars32_MinDist[s32_StPnt] = 0;

    int32_t s32_I, s32_NextPnt, s32_Dst2NextPnt;

    while (!st_PQ.empty())
    {
        int32_t s32_StartPnt = st_PQ.top().second;  // 현재 Node
        int32_t s32_Distance = st_PQ.top().first;    // 현재 Node까지의 거리

        st_PQ.pop();

        if (s32_StartPnt == s32_DstPnt)
        {
            s32_Result = ars32_MinDist[s32_StartPnt];
            break;
        }

        for (s32_I = 0; s32_I < v[s32_StartPnt].size(); s32_I++)
        {
            s32_NextPnt = v[s32_StartPnt][s32_I].first; // 다음 정점
            s32_Dst2NextPnt = v[s32_StartPnt][s32_I].second + s32_Distance;   // 다음 정점까지의 거리 계산

            if (ars32_MinDist[s32_NextPnt] > s32_Dst2NextPnt)
            {
                ars32_MinDist[s32_NextPnt] = s32_Dst2NextPnt;
                st_PQ.push({ s32_Dst2NextPnt,s32_NextPnt });
            } 
        }

    }

    return s32_Result;
}

 

 

먼저 최소 거리(비용)을 저장하는 배열을 모두 무한대로 초기화 해 준다.

    // 최소 거리 배열 Infinite Value로 초기화 
    fill(ars32_MinDist, ars32_MinDist + 1002, C_INFINITE);

 

이후, MinHeap 객체를 생성한다. 이는 최소 비을 가지는 Node부터 순차적으로 접근하기 위함이다. pair의 첫번째는 1번 노드로 부터 pair의 두번째 원소인 해당 노드로 가기 위한 최소 비용이 들어가며, 두번째는 Node 번호가 들어간다. 처음 MinHeap에는 시작 노드가 들어가기 때문에 비용을 0으로 설정하였다. 그리고, 자기 자신의 노드로 가는 경우는 최소 비용을 0으로 설정하였다.

 

    // greater -> MinHeap
    // { Distance , Node }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st_PQ;

    st_PQ.push({ 0, s32_StPnt });
    ars32_MinDist[s32_StPnt] = 0;

 

MinHeap이 Empty일 때 까지 다음 과정을 반복하는데, 이는 위에서 언급한 2~4번 과정을 반복하는 것이다.

현재 MinHeap에 들어있는 Node번호와, 해당 Node로 이동하기 위한 비용을 받아오고, 방문했음을 의미하기 위해 MinHeap에서 삭제한다.

 

    while (!st_PQ.empty())
    {
        int32_t s32_StartPnt = st_PQ.top().second;  // 현재 Node
        int32_t s32_Distance = st_PQ.top().first;    // 현재 Node까지의 거리

        st_PQ.pop();

 

만약 해당 Node가 인자로 받아온 도착 Node라면, 최소 비용이 전부 갱신 된 상황이므로, 결과를 저장하고 반복문을 탈출한다. 그게 아니면, 현재 노드(s32_StartPnt)에서 갈 수 있는 노드수(v[s32_StartPnt].size())만큼 반복하여, 현재 노드에서 갈 수 있는 노드까지의 최소 비용을 Update 한다. 현재 전부 무한대로 초기화를 시켰기 때문에,

if (ars32_MinDist[s32_NextPnt] > s32_Dst2NextPnt) 해당 조건문에 걸리게 된다. Update가 된다면, 시작 노드에서 다음 노드까지의 최소 거리와, 다음 노드 정보를 MinHeap에 추가시킨다.

 

        for (s32_I = 0; s32_I < v[s32_StartPnt].size(); s32_I++)
        {
            s32_NextPnt = v[s32_StartPnt][s32_I].first; // 다음 정점
            s32_Dst2NextPnt = v[s32_StartPnt][s32_I].second + s32_Distance;   // 다음 정점까지의 거리 계산

            if (ars32_MinDist[s32_NextPnt] > s32_Dst2NextPnt)
            {
                ars32_MinDist[s32_NextPnt] = s32_Dst2NextPnt;
                st_PQ.push({ s32_Dst2NextPnt, s32_NextPnt });
            } 
        }

 

왜 이렇게 동작하는지 이해가 되지 않을 수도 있다. 각 배열과 비교문이 비교하는 대상을 하나하나 살펴보자. 

 

v 2차원 벡터는 다음과 같다.

 

즉, 각 행의 pair 객체는 각 행에 해당하는 번호의 Node로 부터, 각 pair 객체의 첫번째 원소의 번호의 Node로 이동하는데 요구되는 비용을 의미한다. {4,7}의 경우 1번째 행에 있으니 1번 노드로 부터 4번 노드로 이동하는데 요구되는 비용이 7임을 의미한다.

 

그리고 MinHeap에 처음 들어가는 pair 객체는 {0, s32_StPnt}로 시작 노드번호와 0이 들어간다. 그렇기 때문에 다음 반복문에서는 시작 노드에서 갈 수 있는 노드들을 s32_NextPnt 변수로 받아오고, 시작 노드로 부터 해당 노드들 까지의 거리를 s32_Dst2NextPnt로 받아온다. 그리고 ars32_MinDist에는 시작 노드로 부터 각 노드까지의 최소 비용이 저장되어 있기 때문에, s32_Dst2NextPnt와 비교되어야 하는 것이다. 

 

그러면 처음 while문을 한번 돌면 ars32_MinDist는 다음과 같이 바뀌어 있을 것이다.

 

그리고 MinHeap에는 최소거리와 각 노드들의 번호가 pair 객체로 들어가 있을 것이다. 따라서, 다음으로 선정되는 s32_StartPnt는 2가 되고, s32_Distance는 3이 된다. 그러면 2번 노드와 연결된 노드는 3번 노드 밖에 없으므로 반복문에서 s32_NextPnt = 3, s32_Dst2NextPnt = v[2][3] + 3이 된다. 즉, s32_NextPnt는 시작 노드인 1번 노드로 부터 2번 노드를 거쳐 3번 노드로 갈 때의 최소 비용을 의미한다. 

 

 

따라서 원래 ars32_MinDist에 저장되어 있던, 1번 노드에서 3번 노드의 최소 거리인 6보다 작기 때문에 Update가 이뤄지며, 그 결과는 다음과 같다.

 

 

이를 전체 노드에 대하여 반복하기 때문에, 결국 우리는 최소 비용(거리)를 구할 수 있는 것이다. 

 

해당 과정을 하나하나 써가며 이해하면 조금 쉬울 것이다.