알고리즘 & 자료구조 복기글 (3) - 다익스트라

이번에 그래프 관련 알고리즘 다익스트라 (dijkstra) 를 들고 오게 되었다. 
우리가 앞으로 그래프 문제를 많이 보게 될 텐데, 그래프 문제에서 가장 많이 다루게 되는 요소가 무엇일까? 바로 거리일 것이다. 가장 짧은 거리, 가장 짧은 거리의 경로, 임의의 두 노드 사이의 거리 등 정말 다양한 거리들을 알아야 할 필요성이 앞으로 생기게 된다. 다익스트라는 그 중 한 노드에서부터 모든 노드까지의 각각의 거리를 알아내고 싶을 때 사용되어진다.

어느정도 bfs랑 비슷한 느낌일 수 있다. bfs를 할 때는 queue의 맨 앞 노드에서 도달할 수 있는 모든 노드를 다시 queue에 넣어 탐색을 한다. 다익스트라는 도달할 수 있는 노드 중 기준노드로부터 가장 가까운 점을 뽑아 그 점을 거쳐 도달할 수 있는 다른 모든 노드를 다시 저장해놓는다. 하지만 언제나 저장공간에서 조건을 만족하는(기준노드로부터 가장 가까운) 노드를 뽑아내야되고, 이때 사용되어지는 자료구조가 priority queue(우선순위 큐)이다. 
내가 STL 활용을 정말 못하는 편이라 STL 관련글들도 쓰기는 해야하는데 언제가 될 지는 모르겠다. 일단 우선순위 큐에 대해서 개념이 알고 싶으면 여기가 좋고, 활용방법등과 예시를 알아보려면 여기도 좋다.

기본 로직 소개

설명하기 위해 그래프 하나를 가지고 왔다.

위는 방향그래프이고 A번 노드에서를 기준 노드로 잡고 각 점까지의 최단 거리를 구해보자.
처음 시작은 아래와 같이 초기화가 되어있는 상태이다.

A	B	C	D	E	G
0	INF	INF	INF	INF	INF

PQ [ {0,A} ]

1. 이제 A를 꺼내고 A까지의 거리는 0으로 확정짓는다. 연결된 B는 5,C는 1로 거리를 업데이트 하면서 PQ에 넣는다.

A	B	C	D	E	G
0	5	1	INF	INF	INF

PQ [ {1,C} , {5,B} ]

2. 이제 C를 꺼내고 C의 거리는 1로 확정지어주며 B,D,E를 업데이트 시켜준다. D와 E는 각각 1+2=3, 1+17=18 으로 업데이트하며 PQ에 넣어준다. 이때 B는 (C까지의 거리+C에서 B까지의 거리)와 현재 B까지의 최단거리를 비교한다. 1+3<5이기 때문에 B를 4로 업데이트 시켜주고, PQ에 {4,B}를 추가한다.

A	B	C	D	E	G
0	4	1	3	18	INF

PQ [ {3,D} , {4,B} , {5,B} , {18,E} ]

3. 이제 D를 꺼내서 D까지의 거리를 3으로 확정지어준다.

A	B	C	D	E	G
0	4	1	3	18	INF

PQ [ {4,B} , {5,B} , {18,E} ]

4. 이제 B를 꺼내서 거리를 4로 확정지어주고 D,E를 업데이트 시켜준다. D는 기존의 방식이 더 짧으므로 바뀌지 않고 E는 4+2로 바뀐다.

A	B	C	D	E	G
0	4	1	3	6	INF

PQ [ {5,B} , {6,E} , {18,E} ]

5. B를 꺼내지만 B는 이미 확정이므로 무시한다. 똑같은 방법으로 6,E는 꺼내지만 업데이트 할 것이 없고, 18,E 는 이미 E를 꺼냈었으므로 무시한다.
그러면 PQ가 비게되고, 다익스트라가 끝나게 된다.

A	B	C	D	E	G
0	4	1	3	6	INF

이와 같은 방법으로 한 개의 노드씩 확정지어 가주면서 각 노드까지의 최단거리를 구하였다.

구현 & 유의할 점.

구현은 위의 설명대로 하면 된다. pair를 지어주면 first부터 판단한다는 라이브러리 기본 기준이 있어서 pq에 바로 넣을 수 있지만, 구조체는 pq에 넣기 전에 정렬 방식을 선언해 주어야한다. 또한, 구현할 때 그냥 pq를 쓰면 큰 값부터 나오기 때문에, greater pq를 사용하거나 모든 간선의 값을 pq에 넣을 때 -로 바꿔주는 방법이 있다.  또한 유의할 점은 다익스트라는 음의 가중치가 있는 그래프에 대해서 제대로 된 답을 내주지 못한다. 
시간복잡도는 O( (E+V) lg E) 

추천 문제

기본 연습문제 : BOJ 1753 최단 경로 
기본 활용문제 : BOJ 1238 파티, 1504 특정한 최단 경로

코드

여기에는 함수 부분의 코드만 담았다. 다익스트라 그 자체를 물어보는 BOJ 1753 최단경로 문제 코드 전체는 다음 글에 포스팅을 할 예정이다.