개요
그래프에서 한정점A에서 다른정점B까지의 최단거리를 구하는 문제를 종종 마주치곤한다.
이런 최단거리문제는 보통 아래의 세 알고리즘을 사용한다.
- 다익스트라 알고리즘(Dijkstra Algorithm)
- 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)
- 벨만 포드 알고리즘(Bellman-Ford's algorithm)
다익스트라 알고리즘은 양의 가중치를 갖는 그래프에서의 최단거리 문제를 푸는 그리디형 알고리즘에 속한다.
매 탐색마다 이전에 탐색한 정점들과 연결된 정점들의 가중치. 거리를 최단거리로 갱신하며, 이중에 거리가 가장짧은것을 다음 탐색정점으로 하는 알고리즘이다.
구현은 크게 두가지 방법이있다.
1. 단순 반복문이용 (중복방문X) : O(N^2)
2. 우선순위큐를 이용 (중복방문 가능) : O(E log N)
아마 다익스트라 알고리즘을 찾아봤다면 그 이전에 유명한 그래프탐색알고리즘인 BFS, DFS를 접해봤을것이다.
그렇기에 2번의 방법으로 구현하는것이 좀 더 수월할것이므로
본 포스트는 직관적이고 시간복잡도가 낮은 2번방법만 설명할것이다.
작동 원리
!! 모든 간선은 양방향연결이며 양의 가중치를 갖는 그래프로 설명해보겠다.
여기서 dist는 모든 정점의 번호를 인덱스로 가지는 일차원 배열로, 매 탐색마다 갱신될 출발정점으로부터 인덱스에 해당하는 정점번호로 가는 최단거리 값이다.
pq는 우선순위큐로, <거리, 정점번호>를 담고있다.
중요한것은 우선순위큐는 내부적으로 최대힙을 구성하게되므로,
우리는 최단거리를 구하기위해, 이 우선순위큐에 거리값을 넣을때는 음수를 취하여 넣고, 실제 꺼내서 비교할땐 다시 역으로 양수로 변환해서 사용할것이다.
-
dist를 모두 최댓값으로 초기화한다.
-
출발정점의 dist를 0으로 초기화하고 pq에 거리0과 출발정점을 넣는다.
이때 거리는 음수로 기록한다. ( <-0, 출발정점> )
이제 위 그림에서 출발정점이 1번이고, 끝정점이 5일때 최단거리를 구해보겠다. -
pq(우선순위큐)에서 거리d, 정점v을 꺼낸다.
-
꺼낸 정점이 끝점(5)이라면 같이 꺼낸 거리d를 리턴하고 알고리즘을 종료한다.
(이때 끝정점을 목적지정점으로 생각하면 목적지까지의 최단거리르 구한것이다.) -
그렇지 않다면 꺼낸 정점v와 인접한 모든 정점을 탐색한다.
인접정점하나를 vv, 그 정점의 가중치를 dd라고 하자.
4-1. dist를 수정한다.
dist[vv] = min(dist[vv] , dist[v] + dd);
즉 첫번째로 인접정점vv의 현재 최단거리값 dist[vv]과
두번째 정점v를 지나 가중치 dd만큼 가서 vv에 도착하는경우
이 두가지 중 짧은것은 현재 정점 vv의 dist로 갱신하는것이다.
이것이 연쇄작용으로 다음 모든 정점의 dist를 구하게되는 다익스트라 알고리즘의 핵심이다.!
4-2. 만약 dist[vv]가 갱신되었다면 우선순위큐에 <dd, vv>를 넣는다. -
위 2~4번을 반복한다.
-
반복 결과 끝점을 만난 경우 최단거리를 찾은것이고,
끝점을 만나기전에 우선순위큐가 비워지면 최단거리를 못찾은것이다.
이제 위 그래프로 탐색과정을 살펴보자.
0~1번 과정으로 우선순위큐에 <0, 1>(출발정점 1번)이 들어간모습이다.
2번과정, pq에서 요소를 꺼낸뒤에 d, v를 지정한다.
4번과정, pq에서 꺼낸 요소를 제거한다.
꺼낸 정점과 인접한 정점들 그리고 거리들 (vv1~vv3, dd1~dd3)을 초록색으로 마킹했다.
4-1번, vv1과 dd1만 살펴보자.
inf값보다 dist[v] + dd = 2로 작으므로
dist를 갱신하고, 이어서 pq에 갱신정보를 넣는다.
이렇게 dist가 최단거리로 갱신될때만 pq에 넣는다.
이어서 다른 인접정점도 최단거리를 비교하여 갱신한다.
나머지 정점들은 dist가 갱신되지않아 아무것도 pq에 넣지 않았다.
이제 pq에서 다음 요소를 꺼낼 차례다.
운선순위 큐이고 거리값들을 음수로 넣었으니 거리값 기준으로 오름차순 정렬이 되었을것이다.
이 그림처럼 pq 내부 요소들은 오름차순 정렬 되있다.
pq가 비어있지 않으므로 다시 요소를 꺼내 d, v를 갱신한다.
다시 d, v에 인접한 정점을 살펴보자.
여기서 dd1, vv1 만 살펴보자.
dist[vv]에 해당하는 dist[1]=0 이고 dist[v] + dd = 3 + 1 = 4이므로, 최솟값은 갱신되지않는다.
dist가 갱신되지 않았기에 pq에 요소를 넣지 않는다.
다음 vv2, dd2를 살펴보자.
dist[4] = 3 이고 dist[v] + dd2 = 3 이므로 같으므로 갱신하지않고 pq에도 넣지 않는다.
이제 큐의 다음요소를 꺼내 d, v를 갱신하고 이어서 인접 정점을 탐색해보자.
당연히 dist[5]만 2 + 2 = 4 로 갱신될것이고, 따라서 큐에 요소를 넣을것이다.
여기서!!!! 우리는 우선순위큐를 사용하므로, 끝점을 방문했다고 우리의 알고리즘이 끝나지않는다.
큐 내부에서 오름차순 정렬이되어, 더 짧은거리의 정점이 있으면 우선탐색해가며
매 탐색마다 인접한 정점의 최단거리를 갱신하니까 말이다.!!
따라서 현재의 값 dist[5]는 끝점이지만 갱신될 가능성이 있다.!
(하지만 현재 4가 최단거리일것이다.)
이어서 큐에서 요소를 꺼내 탐색을 진행한다.
인접 정점들이다. 이 중에서는 아무것도 갱신되지 않을 것이고 따라서 큐에는 아무것도 넣지않는다.
그럼 큐의 마지막요소를 꺼내자.
3번에의해서 큐에서 꺼낸 v가 끝점이면 꺼낸 거리 d를 리턴하고 알고리즘을 종료한다.
따라서 1번정점에서 5번정점까지 가는 최단거리는 4가 나오게된다.
이로써 우선순위큐를 사용하여 단순히 요소수만보면 5 x 2(평균인접정점수) (~ O(E log N) ) 만의 비교로 최단거리를 찾을 수 있었다.
반복문만을 이용했다면 똑같이 매번 최소거리 dist를 갱신하며
5 x 5 (~ O(N^2) )가 걸렸을것이다.
구현
먼저 vector<pair<int, int>> edge[N]; 벡터배열을 선언했고,
edge[a].pb({b, c}); : a와 인접한정점은 b이고 가중치는 c
라는 벡터로 인접 정점의 정보를 저장했다.
이제 코드를 보자.
- 103 : 출발지start로부터의 최단거리를 저장할 일차원배열이다. 크기는 그래프의 정점갯수만큼, 그 값은 INT_MAX( INF )로 초기화 했다.
- 104 : priority_queue<pair<int, int>> pqq; : 사용될 우선순위큐. {거리, 노드}를 요소로 갖는다.
- 106 : 출발지start의 최단거리는 0으로 설정해준다.
- 107 : 큐의 출발지를 넣는다. 여기서 중요한것이 큐에 요소를 넣을때 거리는 항상 음수로 넣어줘야 내부적으로 최소힙을 구현한것과 같은의미, 거리기준 오름차순 정렬을 할 것이다.
- 109 : 큐가 빌때까지 반복한다. (그래프알고리즘 BFS, DFS와 유사한 모습)
- 110~112 : 큐에서 요소를 꺼낸다. 이때 거리값은 음수를 취해서 다시 양수로 변환시켜준다. (BFS, DFS와 유사하죠?)
- 113 : 큐에 저장된 요소중 최단거리 순서대로 꺼냈는데, 이게 끝점이라면 해당 최단거리값 d를 리턴하고 종료.
- 115 : 꺼낸 정점 v와 인접한 모든 정점을 탐색
- 116~117 : 정점간 연결정보 edge를 이용해 인접 정점을 정의 (BFS, DFS와 유사)
- 119 : 인접 정점의 새로운 최단거리값을 찾았다면 갱신하고 동시에 큐에 넣는다.! (BFS, DFS와 유사)
- 121 : 큐에 넣을때 거리값은 항상 음수로 넣는다.
- 125 : 최단거리를 찾지 못한경우 -1을 리턴하고 종료한다.
실제 구현 코드를 보면 어렵진않다. 어쩌면 코드를 보고 다시 작동원리를 살펴보면 이해가 빠를지도?
관련문제
https://www.acmicpc.net/problem/1238 >> https://velog.io/@cldhfleks2/1238
https://www.acmicpc.net/problem/1504 >> https://velog.io/@cldhfleks2/1504
https://www.acmicpc.net/problem/1753 >> https://velog.io/@cldhfleks2/1753
