그래프 알고리즘에서 '최소 비용'을 구해야 하는 경우 사용할 수 있는 대표적인 알고리즘으로는

'다익스트라 알고리즘' , '벨만-포드 알고리즘' , ' 플로이드 워샬 알고리즘' 이 있다.

이번 글에서는 '다익스트라 알고리즘'에 대해서 알아보자.


1. 다익스트라 알고리즘 ??

다익스트라 알고리즘은 위에서도 말했듯이, 그래프에서 '최소 비용'을 구해야 하는 경우 유용하게 사용되는 알고리즘이다.

최소 비용 중에서도, 주어진 두 노드(시작노드 , 도착노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.


2. 다익스트라 알고리즘의 동작 원리

지금부터 '비용' 이라는 말을 많이 사용하게 될 텐데, 이 값은 1차원 배열 Dist[] 라는 배열에 저장되어 있다고 생각하자.

초기 Dist배열의 모든 값은 무한대(INF)로 초기화 되어 있다.

다익스트라 알고리즘의 동작 원리를 순서대로 적어보자면 다음과 같이 작동한다.

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로

   체크한다.

2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로

   선택해준다.

3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

4. 2 ~ 3번 과정을 반복한다.

위의 과정을 그림으로 한번 알아보자.

위의 그림을 토대로 한번 알아보자. 시작 노드가 '1'번이라고 가정하겠다.

현재 Dist배열 (해당 정점까지의 최소비용을 저장하는 배열) 은 모두 무한대(INF)로 초기화 되어 있는 상태이다.

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로

   체크한다.

- 시작 노드로 부터 직접 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주면 다음과 같이 될 것이다.

  2번 정점은 길이가 '4'인 간선과 연결되어 있으므로 Dist[2] = 4.

  3번 정점은 길이가 '2'인 간선과 연결되어 있으므로 Dist[3] = 2.

  1번 정점은 자기 자신이므로 Dist[1] = 0.

  이 후, 시작노드를 방문한 노드로 체크해주자. 여기서 방문한 노드로 체크를 한다는 것은, 다시는 이 정점의 최소비용은

  건들지 않겠다는 의미이다. 다른 경로로 갔을 때 작은 비용이 나오게 되면?? 이라는 의문점이 생길 수 있는데, 이 부분에

  대해서는 밑에서 알아보자.

  그럼 위의 상태를 그림으로 나타내면 다음과 같이 나타낼 수 있다.

 

  여기서 초록색으로 동그라미를 칠한 것은 "이미 방문한 노드이니, 더 이상 건들지 않겠습니다" 를 의미한다.

  또한, 1, 2, 3번 정점의 Dist값이 바뀌었다는 것을 확인할 수 있다.

2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로

   선택해준다.

- 방문한 정점들과 연결되어 있는 정점은 { 2, 3 } 2개의 정점이 있다.

  현재 방문한 정점은 { 1 } 1개 뿐이고, 이 정점과 연결되어 있는 정점 중 가장 비용이 적게 드는 정점은 비용이 '2'가 드는

  '3'번 정점일 것이다.

  해당 간선이 연결해주는 새로운 정점을 방문한 정점으로 체크해주자.

  그렇게 되면 다음과 같이 된다.


3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

- 2번 과정에 의해서 '3'번 정점이 새로운 방문한 정점이 되었고, 이로 인해서 Dist배열의 값, 즉, 최소비용의 값이 업데이트 되

  는 정점들이 존재하므로 업데이트를 해주자.

  위의 그림에서는 '3'번 정점에 의해서 '5'번 정점의 Dist 값이 무한대 에서 6이 될 것이다.

  왜냐하면 ! 1번 정점에서 5번정점까지의 거리는 무한대였지만, 즉, 직접적으로 연결되어 있지 않아서 갈 수 없다고 생각하고

  있었지만, 3번 정점에 의해서 연결이 되었고, 결국 1 → 3 → 5 로 갈 수 있기 때문에 가는데 걸리는 비용은

  1 → 3 으로 갈 때 드는 비용 '2' + 3 → 5로 갈 때 드는 비용 '4' = 6 이 된다.

4번 과정은 2 ~ 3번의 과정을 반복하는 것이다.

그럼 다시 2번 과정을 진행해보자.

2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로

   선택해준다.

- 방문한 정점들과 연결되어 있는 간선들 중에서 가장 짧은 간선은 1번과 2번을 잇는 길이가 '4'인 간선일 것이다.

  왜냐하면, 현재 상황을 보면 Dist[2] = 4, Dist[5] = 6, Dist[4] = INF, Dist[6] = INF 이고, 이 중에서 현재 방문한 정점들과

  연결되어 있는 정점은 { 2, 5 } 2개의 정점이 있고, 그 중 더 적은 비용이 드는 정점은 '2'번 정점이기 때문이다.

  그럼 '2'번 정점을 방문한 정점으로 표시해주자.

  그리고, 이 2번에 의해서 비용이 새롭게 갱신될 수 있는 정점들을 업데이트 해주자.

  위의 상황에서는 '4'번 정점이 '8'로 갱신될 것이다.

  왜냐하면 1 → 2 → 4 = 1 → 2 (4) + 2 → 4 (4) = 8 < INF 이므로, 8로 갱신될 것이다.

  하지만 '5'번 정점은 갱신되지 않을 것이다. 현재 '5'번 정점까지 가는데 드는 최소 비용은 6이다.(Dist = 6)

  그런데, 1 → 2 → 5 로 오게 될 경우, 1 → 2 (4) + 2 → 5 (5) = 9 이므로 9 > 5 이므로 갱신되지 않는다.

  따라서 업데이트 되는 값을 적어보면 다음과 같다.

   3번 과정을 따로 표시하지 않고 위에서 진행해버렸다...

   다시 2번과정이다. 방문한 정점들과 연결되어 있는 정점들 중에서, 가장 적은 비용이 드는 정점을 찾아보자.

   이번에는 '5'번 정점이 선택될 것이다. 왜냐하면 Dist[5] = 6, Dist[4] = 8, Dist[6] INF 이므로 5번 정점이 가장

   비용이 적게 든다.

   따라서, 5번 정점을 선택했다고 표시하고, 5번 정점 선택에 의해서 갱신되는 '6'번정점의 비용까지 표시해보면

   다음과 같아진다.

  

    그럼 이제 다시 방문한 정점들 중에서 가장 적게 비용이 드는 정점을 찾아보자. 그런데 보니, Dist[4]와 Dist[6]의 값이

    8로 동일하다. 이럴때는 어떤 값을 선택해도 상관이 없다. '4'를 선택했다고 가정해보자.

    4번을 선택하더라도, 4번 정점에 의해서 6번 정점이 업데이트 되지는 않는다. 왜냐하면

    현재 Dist[6] = 8 인데, 1 → 2 → 4 → 6 으로 올 경우 9의 비용이 들기 때문에 기존의 값보다 더 큰 비용이 들기 때문에

    갱신해 주지 않는다.

    마지막으로 6번 정점까지 선택해 버리면 최소비용을 구하는 과정을 모두 마치게 된다.

    그럼 지금부터는 위에서 빨간색으로 표시해 놨었던 "다른 경로로 갔을 때, 더 작은 비용이 나오지 않을까?" 에 대해서

    이야기해보자.


3. 다익스트라 알고리즘의 한계

- 우리는 위에서 왜인지도 모른채, "현재 선택된 정점들과 연결된 정점들 중, 가장 적게 비용이 드는 정점을 무조건적으로

  방문했다고 체크" 후, 연결된 다른 정점들의 값을 업데이트 시켜주었다.

  그런데, 과연 지금 눈앞에 드는 비용이 가장 적다는 이유만으로, 해당 정점을 다시는 안쳐다봐도 될까 ??

  분명, 위에서 초록색으로 표시된 '이미 방문한 정점' 에 대해서는 "더 이상 쳐다보지 않겠습니다." 라고 단정짓고

  진행하였다.

  그런데 보면.. 위의 과정을 해봐서 알겠지만 우리는 모든 정점을 방문할 때 까지, 기존에 초록색으로 표시한 정점의

  값을 다시 갱신시킨다거나 건드리는 일이 없었다.

  왜 이게 가능할까 ??

  간단하게 정점 3개만 가지고 한번 생각을 해보자.

 

   위의 상황을 통해서 다시한번 정리해보자. 우리가 지금까지 이야기한 걸로는 A에서 B를 선택하는게 맞다.

   그 이후, B는 방문한 정점이라 표시해버린 이후에 다시는 쳐다도 보지 않았다. 그런데, B로 가는데 드는 최소비용이

   단지, A 에서 연결된 정점들 중 비용이 가장 적다는 이유만으로 최소비용이 '5' 라고 단정지을 수 있냐 라는 것이다.

   그럼 "단정지을 수 없다." 라고 가정을 하고 위의 X값을 한번 구해보자.

   5 라고 단정지을 수 없다라는 말은, A → C → B가 5보다 더 작은 값이 나와야 한다는 말이다.

   그럼 X값은 ?? 10 + X < 5 이기 때문에, X < - 5. 즉, X가 -5보다 작다면 위의 상황에서 B로 가는데 최소 비용이

   '5' 라고 단정지을 수 없게 된다.

   이게 다익스트라 알고리즘의 한계(?) 이다. 바로, 그래프에서 정점을 잇는 간선의 가중치에 '음수'가 들어가버리면,

   다익스트라 알고리즘은 적용할 수가 없게 된다.

   즉, 다익스트라 알고리즘은 '모든 가중치가 양수일 경우' 에만 적용시킬 수 있는 최소비용을 구하는 알고리즘이다.

   그럼 다시 위의 상황을 봐보자.  A → B가 5이다. 마찬가지로, B로 가는데 드는 최소비용이 5라고 단정지을 수 없다

   라고 가정을 해보자. 이 때 X값을 구해보자. 단, (X > 0) 이다.

   위의 조건을 만족하는 X값을 찾는게 가능할까 ?? 위의 조건을 만족하는 X값은 없다.

   이러한 이유 때문에, 위에서 설명할 때에도 "현재 선택된 정점들과 연결된 정점들 중, 가장 적게 비용이 드는 정점을 방문했

   다고 체크"하고 이미 방문한 정점에 대해서는 값을 업데이트 하거나 하지 않았던 것이다.

   위의 과정을 다시 한번 살펴보면, 값을 업데이트 할 필요가 있었는데 억지로 피하거나 한 것은 아니다. 다익스트라 알고리즘

   그대로 진행하다보니 방문한 정점의 값을 업데이트를 하지는 않았다.

   즉, 다익스트라 알고리즘은 모든 가중치가 양수일 때만 적용할 수 있는 최소비용을 찾는 알고리즘이다 !


4. 다익스트라 알고리즘 구현

그럼 ! 이제 가장 중요한 실제로 코딩으로 구현해보는 방법에 대해서 알아보자.

이번 글에서는 2가지 방법에 대해서 알아볼 것이다.

첫 번째 방법은 위의 과정을 그대로 코드로 옮겨 놓은 것이다. 

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로

   체크한다.

2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로

   선택해준다.

3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

4. 2 ~ 3번 과정을 반복한다.

위에서 말한 과정을 그대로 가져온 것이다.

1번 과정부터 알아보자.

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로

   체크한다.

1
2
3
for (int i = 1; i <= V; i++) Dist[i] = MAP[Start][i];
Dist[Start] = 0;
Select[Start] = true;

c


여기서 Dist배열은 위에서 말한 '각 정점까지 가는데 드는 최소비용'을 저장해놓은 배열이고, Select배열은 '선택한 정점'을
표시하기 위해서 사용한 배열이다.
Dist배열의 초기값은 모두 INF(무한대) 이고, Select배열의 초기값은 모두 false(선택하지 않음 or 방문하지 않음) 이다.
1번 과정에서 "시작노드와 직접적으로 연결된 모든 정점들의 거리를 업데이트" 하는 과정이 line1 에 있는 for문이다.
초기 Dist배열은 모두 무한대이기 때문에, 위와 같이 업데이트 해 주었다.
그리고 line2, 3 에서는 "시작노드를 방문한 노드로 체크" 하고, 시작노드와 자기자신의 거리는 0으로 갱신시켜 주었다.

2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로

   선택해준다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Find_Shortest_Node()
{
    int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
 
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == truecontinue;
        if (Dist[i] < Min_Dist)
        {
            Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}
cs

2번 과정을 나타낸 코드이다. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하는 과정인데,

line10) 에서 Dist[i] < Min_Dist로 비교할 수 있는 것은, 어차피 방문한 정점들과 직접적으로 연결되어 있지 않다면

Dist[i] = 무한대 일 것이기 때문에, 저 조건문을 만족해서 line 11 ~ 14를 진행한다는 것은 "방문한 정점들과 연결되어 있다"

라는 것을 의미한다.

그 중에서 가장 비용이 적게드는 정점을 선택해서 return 해주는 함수이다.

위의 코드에서는 "해당 정점을 방문한 정점으로 선택해준다" 를 구현한 부분이 없는데, 이 부분은 마지막 전체 코드에서

확인해보자.


3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.

1
2
3
4
5
6
7
8
9
10
11
void Update_Dist(int NewNode)
{
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == truecontinue;
        if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
        {
            Dist[i] = Dist[NewNode] + MAP[NewNode][i];
        }
    }
}
cs

이 함수에서 매개변수 'NewNode'는 2번 과정에서 return된 'Min_Idx' 이다. 즉 ! 비용이 가장 적게 드는 정점을 선택해서,

해당 정점을 선택했다고 표시하는 것 까지 2번과정에서 진행했고, 해당 정점에 의해서 드는 비용이 업데이트 될 수 있는

정점들의 Dist값을 모두 갱신해 주는 것이다.


4. 2 ~ 3번 과정을 반복한다.

2 ~3 번의 과정을 반복해야 하는데, 과연 몇번을 반복할까 ??

다시 이 경우를 확인해보자. 우리는 처음에 Start 노드를 '1'번 노드로 선택하고 다익스트라 알고리즘을 시작하였다.

그럼 2 ~ 3번의 과정, 즉, 비용이 가장 적게드는 새로운 정점을 찾고, 값을 업데이트를 하는 과정을 몇 번 진행했을까 ?

1. 1번 정점에서 3번 정점을 선택하고, 3번정점에 의해서 값을 업데이트. = 1번

2. 2번 정점을 선택하고, 2번 정점에 의해서 값을 업데이트. = 2번

3. 5번 정점을 선택하고, 5번 정점에 의해서 값을 업데이트. = 3번

4. 4번 정점을 선택하고, 4번 정점에 의해서 값을 업데이트. = 4번

5. 6번 정점을 선택하고, 종료. = 5번

우리는 총 5번을 진행하였다. 즉 ! N - 1번(N = 정점의 수) 위의 과정을 반복하게 된다.

따라서 전체 코드를 보면 다음과 같다.

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
int Find_Shortest_Node()
{
    int Min_Dist, Min_Idx;
    Min_Dist = INF;
    Min_Idx = -1;
 
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == truecontinue;
        if (Dist[i] < Min_Dist)
        {
            Min_Dist = Dist[i];
            Min_Idx = i;
        }
    }
    return Min_Idx;
}
 
void Update_Dist(int NewNode)
{
    for (int i = 1; i <= V; i++)
    {
        if (Select[i] == truecontinue;
        if (Dist[i] > Dist[NewNode] + MAP[NewNode][i])
        {
            Dist[i] = Dist[NewNode] + MAP[NewNode][i];
        }
    }
}
 
void Dijkstra()
{
    for (int i = 1; i <= V; i++) Dist[i] = MAP[Start][i];
    Dist[Start] = 0;
    Select[Start] = true;
    
    for (int i = 0; i < V - 1; i++)
    {
        int NewNode = Find_Shortest_Node();
 
        Select[NewNode] = true;
        Update_Dist(NewNode);
    }
}
cs

line 37)을 보게되면 i = 0 ~ V - 1 까지( 코드에서 V = 정점의 수) 즉, N - 1번만 반복한다는 것을 알 수 있다.

그리고 위에서 2번과정에서 빼먹은 "해당정점을 방문했다고 표시" 하는 과정은 line 41)에 있다.

하지만 이렇게 구현할 경우, 전체 (N - 1)번 탐색 x ( 최소비용이 드는 정점 찾기(N번 순차탐색) ) 만큼 걸리게 된다.

즉, O(N^2) 만큼의 시간복잡도를 갖게 되는데, 그리 빠른 편은 아닌 것 같다.

그래서 다익스트라 알고리즘을 자료구조 힙을 이용하는 우선순위큐를 사용하면 조금 더 시간을 줄일 수 있다.


두 번째 방법은 위에서 말한 우선순위 큐를 이용하는 방법이다.

우선순위 큐를 이용해서 구현하였을 때, 동작방식은 인접한 간선들을 모두 Queue에 집어 넣은 후, 최소힙을 구하는 연산을

통해서 최소비용이 드는 정점들부터 처리하는 방식이다.

이렇게 처리했을 경우, 시간복잡도는 O(E * logN) (E = 간선의 수, N = 정점의 수) 이다.

( 나무위키 참고 내용 )

모든 정점들에 대해서 최소힙으로 추출하는데 걸리는 시간복잡도가 O(logN)이 되고, 각 노드마다 인접한 모든 간선들을

확인해 봐야 하므로, 결국 모든 간선들을 확인하는 것과 같으므로 O(E) 만큼 걸리게 되어서 결과적으로는

O(E * logN) 이 걸리게 된다.

무튼 이렇게 우선순위큐를 이용하게 되면 시간을 조금 더 빠르게 해서 구현할 수 있다.


[ 우선순위 큐를 이용한 다익스트라 소스코드 ]

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
void Dijkstra_Using_Heap()
{
    priority_queue<pair<intint>> PQ;
    PQ.push(make_pair(0, Start));
    Dist[Start] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < Vertex[Cur].size(); i++)
        {
            int Next = Vertex[Cur][i].first;
            int nCost = Vertex[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
 
    for (int i = 1; i <= V; i++)
    {
        if (Dist[i] == INF) cout << "INF" << endl;
        else cout << Dist[i] << endl;
    }
}
cs

코드는 위와 같다.

line 9번과 line 21번에 보면, Queue에 값을 넣고 빼는 연산을 할 때, 간선의 길이에 '-'를 붙여서 연산을 해주는데,

이는 최소힙으로 구현하기 위해서이다.

line 3번과 같이 일반적으로 Priority_Queue를 선언해서 사용할 경우 '값이 클 수록 더 높은 우선순위'를 갖게된다.

즉 { 2, 3, 5 } 를 넣게 되면, 우리는 더 최소비용인 '2'를 우선적으로 뽑아서 사용하고 싶지만, 저렇게만 선언해 놓을 경우

'5'를 가장 우선적으로 뽑아서 사용하게 된다. 따라서 '-'를 붙임으로써 값의 크기를 반전시켜 주는 효과이다.

물론, priority_queue를 아래와 같이 선언해서 사용하면 '-'를 붙이기 않고도 최소힙을 구현할 수 있다.

1
priority_queue<intvector<int>, greater<int>> PQ;
cs

위와 같이 선언하게 되면, 값이 작을수록 우선순위를 갖는 최소힙으로 사용이 가능하다.




 

+ Recent posts