13. 다익스트라(Dijkstra) 최단 거리 알고리즘

1. 개요

 이번 글에서는 드디어 내게 수많은 시련과 아픔을 줬던 알고리즘인 다익스트라 알고리즘을 작성한다. 다익스트라 알고리즘

은 방향성이 있고 가중치가 있는 그래프에서 노드에서 노드까지 최단 거리를 찾는 알고리즘이다. 이 알고리즘은 취업 관문

에서 2번이나 만나본 알고리즘이다. 최고의 게임 회사 중 하나에서 최종 코딩테스트에서 나온 문제이기도 하고 최고의 

소셜커머스 기업에서 코딩 문제로 나온 문제이기도 하다. 그리고 나는 나올 때 마다 풀긴 풀었는데 뭔가 미흡하게 풀었고

결과는 탈락이었다. 왜냐하면 그 당시의 나는 STL을 쓰지 않고 미련하게 모든 자료구조 하나하나 다 내가 만들어서 풀려고

했기 때문에 언제나 시간이 부족했다. 다익스트라 알고리즘의 특성상 우선순위 큐 만들기도 힘든데 그 제한 시간동안 우선

순위 큐인 힙을 만드는데 주어진 시간 대부분을 써버리고 정작 알고리즘에 넣어서 최종 테스트할 시간하기도 벅찼기 때문

이다. 그래서 이번 기회에 확실하게 정리해서 다시는 틀릴 일 없도록 머릿속에 담아둔다.

 다익스트라 알고리즘은 탐욕 알고리즘(Greedy Algorithm)을 사용한다. 탐욕 알고리즘이란 현재 상황에서 여러가지 경우가

있을 경우 그 순간의 최선의 선택을 하는 알고리즘이다. 그 순간 순간 최선을 선택해 결국 최종적으로 답을 도출하지만 

이렇게 얻은 문제의 답이 전체적으로 최선이라고 보장되지는 않는다.

 필요한 재료는 다음과 같다.

 (1) 시작 노드에서 각 노드들의 최단 거리를 기록하는 거리 배열(일차원 배열)

 (2) 시작 노드에서 끝 노드까지 경유한 노드를 기록하는 경로 배열(일차원 배열)

     ( 구조: Path[CurrentNodeIndex] = BeforeNodeIndex, 각 노드 인덱스의 배열값은 이전 노드 인덱스이다. )  

 (3) 우선순위 큐 (왜 일반 큐가 아닌 우선순위 큐일까?, 왜 음의 가중치는 안될까? (답은 해설에서))

 

 알고리즘은 다음과 같다.

 (1) 거리 배열을 -1로 초기화한다. (단, 시작점은 0으로 만든다. 0은 시작점, -1은 아직 계산 안한 노드 의미)

 (2) 경로 배열을 -1로 초기화한다. (단, 시작점은 0으로 만든다. 0은 시작점, -1은 이전 노드가 없다는 의미)

 (3) 현재 노드에서 연결된 노드들을 우선순위 큐에 넣는다. 우선순위 큐이므로 최단거리로 정렬된다.

     (시작점 일 경우, 시작 노드를 큐에 넣는다.)

 (4) 현재 노드와 연결된 노드들 사이의 최단거리를 찾아서 거리 배열과 경로 배열을 채운다.

 (5) (3) ~ (4)을 모든 노드를 방문할 때 까지 반복한다.

2. 문제

 다음 그림에서 다익스트라 알고리즘을 작성하시오. (STL 사용시 편함)

3. 코드

3-1) 메인

3-2) 다익스트라(Dijkstra Alg) 알고리즘

3-3) 경로추적 알고리즘

3-4) 출력

4. 해설

 드디어 다익스트라 알고리즘 정리가 끝났다. STL을 안썼을때는 코드가 그렇게 커졌는데 STL을 쓰기 시작하니

코드가 기하급수적으로 줄어든다. 참 편리하다. 지금 생각하면 아쉽다. 진작 STL 썼으면 최종 코딩 테스트에서

무난히 통과했을 것 같았는데, 괜히 무리하게 모든건 다 만들어서 하려고 했던 내가 미련스럽다. 하지만 그런

과정이 있었으니 지금 더욱 발전했겠지.

 다음은 해설이다.

 (1) 왜 우선순위 큐를 쓸까?

 결론적으로 말해서 최소거리 값 갱신 횟수의 증가때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과

에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다. 다익스트라 알고리즘에서 

속도에 영향을 주는 요소는 큐에서 노드를 꺼내오는 횟수와 우선순위 큐의 갱신 횟수이다. 이게 무슨 뜻이냐면 

예를들어 보자. 만약 위의 예제에서 일반 큐를 쓴다면 A에서 검사를 시작할 때, 연결된 두 노드 B와 C중 B부터 

검사한다. 하지만 우선순위 큐라면 C부터 검사한다. 왜냐하면 우선순위 큐로 인해 최소 거리로 정렬된 순서로 

큐에서 추출되기 때문이다. 이 상황을 정리하면

A에서 E까지 최소거리를 검사할 때

일반 큐)

A -> B -> C -> E -> B -> D -> E -> E 순으로 검사

첫 번째 E 노드를 검사할 때, 현재 B까지 최소거리는 4, C까지 최소거리는 1, E까지 최소거리는 8이 된다.

하지만 그 다음 B노드를 검사할 때 B의 최소거리가 3으로 갱신되기 때문에 이전에 계산한 작업이 

무의미한 값이 된다. 이런 경우가 일반 큐를 사용할 때 나타나는 시간상의 비효율적인 대표 예이다.

우선순위 큐)

A -> C -> B -> B -> D -> E -> E -> E 순으로 검사

이 검사는 이전에 계산해둔 값이 그 단계에서 최소값이라는 것이 보장되기 때문에 갱신 횟수가 현저히 적어진다.

 이해를 돕기위한 작은 예지만 그래프의 크기가 커지면 커질수록 이런 일반 큐와 우선순위 큐 사이의 중복갱신

횟수가 일반큐가 월등히 많아지게 된다. 그러므로 최종적으로 일반 큐에서는 O(E+V^2)에서 우선순위 큐 사용 시

O(ElogV)으로 시간상의 이점이 발생하게 된다. (V는 정점 수, E는 엣지 수)

 (2) 왜 음의 가중치는 계산을 못할까? 

결론적으로 말해서 그 이유는 이전 노드까지 계산해둔 최소거리 값이 최소라고 보장할 수 없기 때문이다.

다익스트라는 정점을 지날수록 가중치가 증가한다 라는 사실을 전제하고 쓰여진 알고리즘이다. 하지만 음의

가중치가 있다면 정점을 지날수록 가중치가 감소할 수도 있다는 의미가 되므로 앞선 전제가 무너진다. 그러므로

다익스트라 알고리즘에서는 음의 가중치를 계산할 수 없다. 하지만 이와같은 점을 음의 가중치에서도 최소거리를

계산하는 벨만-포드 알고리즘이 존재한다.  

*현재 이 코드는 정점 이름을 숫자로 표기하면 상관없지만 고유 이름으로 나타낼 수 없다. (지명 이름을 표기하고 싶으면 추가 작업 필요)