한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘
주로 간선에 가중치가 주어질 때 사용한다.
단, 다익스트라 알고리즘은 가중치가 음수인 경우에는 적합하지 않다.
(이유는 나중에 설명)
우선순위 큐를 이용하지 않고 구현하는 방법과 우선순위 큐를 이용하여 구현하는 방법이 있다.
우선순위 큐를 이용할 때 시간복잡도는 더 줄어든다.
<우선순위 큐를 이용하지 않는 다익스트라 알고리즘>
시간 복잡도 : O(N²)
다익스트라 알고리즘을 구현할 때 필요한 몇 가지가 있다.
- 시작점과 각 정점들간의 최단거리를 저장하는 이차원 배열
dist[start][end] : start 정점부터 end 정점까지의 최단거리
과정을 진행하면서 계속해서 최단거리를 업데이트하기 때문에 처음에 dist 배열의 모든 요소를 Integer.MAX_VALUE
값으로 초기화해준다. 그리고 새로 업데이트된 거리가 기존의 거리보다 작다면 갱신시켜주는 방식으로
최단거리를 계속 수정한다.
- 정점 간의 가중치를 저장하는 인접리스트 혹은 인접행렬
- 정점의 최단거리를 구했는지 안 구했는지 확인하는 일차원 배열
check[n] = true 라는 것은 시작점부터 n 정점까지의 최단거리가 이미 구해졌음을 의미
알고리즘 :
0. dist[start] = 0 으로 변경한다(시작점에서 시작점까지의 거리는 0이기 때문)
1. 체크되지 않는 정점 중에서 시작점과의 거리가 가장 작은 정점(n)을 선택
2. 해당 정점(n)을 check[n] = true 로 변경한다.
3. 해당 정점(n)과 인접한 정점들을 차례로 검사
- 인접한 정점(m)과 정점(n) 간의 가중치를 w 라고 하면, dist[m] > dist[n] + w 이면 dist[m]를 갱신
4. 모든 정점을 체크할 때까지 1-3단계들을 반복한다.
아래 예제를 보자.
정점 1번부터 6번까지 있고, 가중치 정보는 아래와 같다.
먼저, 시작점을 정점 1번이라고 하면 dist[1] = 0 으로 초기화해준다. 정점1부터 정점1까지의 최단거리는 0이다.
정점1번부터 6번까지 중 시작점과 가장 짧은 거리를 가지고 있는 정점은 1번이다.
나머지는 무한대의 거리를 갖는다. (위 표 참고)
정점1번의 최단거리가 가장 짧으므로 check[1] = true로 변경
이제 정점1번과 인접한 정점들의 거리를 새롭게 갱신해준다.
정점1번과 인접한 정점은 2번과 3번이다.
[정점2] dist[2] > dist[0] + 3 이므로 dist[2] = dist[0] + 3 으로 갱신 dist[2] : INF -> 3
[정점3] dist[3] > dist[0] + 5 이므로 dist[3] = dist[0] + 5 으로 갱신 dist[3] : INF -> 5
정점1번은 최단거리 구하기 완료! (회색 동그라미)
check가 false인 정점 중에서 시작점과의 거리가 가장 짧은 정점은 dist[2] =3 인 정점2번이다.
정점2번의 거리가 가장 짧으므로 check[2] = true 로 변경
정점2번의 인접한 정점은 1번, 3번, 4번, 5번이다.
[정점1번] dist[1] < dist[2] + 3 이므로 dist[1] 는 갱신되지 않는다.
[정점3번] dist[3] > dist[2] + 1 이므로 dist[3] = 3 + 1 = 4 로 갱신 dist[3] : 5 -> 4
[정점4번] dist[4] > dist[2] + 4 이므로 dist[3] = 3 + 4 = 7 로 갱신 dist[4] : INF -> 7
[정점5번] dist[5] > dist[2] + 6 이므로 dist[5] = 3 + 6 = 9 로 갱신 dist[5] : INF -> 9
check가 false인 정점 중에서 가장 거리가 짧은 정점은 dist[3] = 4 인 정점 3번이다.
check[3] = true로 변경
정점3번의 인접한 정점은 1번, 2번, 5번이다.
[정점1번] dist[1] < dist[3] + 5 이므로 dist[1] 는 갱신되지 않는다.
[정점2번] dist[2] < dist[3] + 1 이므로 dist[2] 는 갱신되지 않는다.
[정점5번] dist[5] > dist[3] + 2 이므로 dist[3] = 4 + 2 = 6 으로 갱신 dist[5] : 7 -> 6
check가 false인 정점 중에서 가장 거리가 짧은 정점은 dist[5] = 6 인 정점 5번이다.
check[5] = true로 변경
정점5번의 인접한 정점은 2번, 3번, 4번, 6번이다.
[정점2번] dist[2] < dist[5] + 6 이므로 dist[2] 는 갱신되지 않는다.
[정점3번] dist[3] < dist[5] + 2 이므로 dist[3] 는 갱신되지 않는다.
[정점4번] dist[4] < dist[5] + 8 이므로 dist[3] 는 갱신되지 않는다.
[정점6번] dist[6] > dist[5] + 1 이므로 dist[6] = 6 + 1 = 7 로 갱신 dist[6] : INF -> 7
check가 false인 정점 중에서 가장 거리가 짧은 정점은 dist[4] = dist[6] = 7인 정점 4,6번이다.
거리가 같은 정점이 두 개 이상일 때는 번호가 작은 것부터 선택하는 것으로 하자.
check[4] = true로 변경
정점4번의 인접한 정점은 2번, 5번, 6번이다.
[정점2번] dist[2] < dist[4] + 4 이므로 dist[2] 는 갱신되지 않는다.
[정점5번] dist[5] < dist[4] + 8 이므로 dist[5] 는 갱신되지 않는다.
[정점6번] dist[6] < dist[4] + 10 이므로 dist[6] 는 갱신되지 않는다.
-> 아무 것도 갱신되지 않음
check가 false인 정점은 하나밖에 남지 않았다. dist[6] = 7
check[6] = true로 변경
정점6번의 인접한 정점은 4번, 5번이다.
[정점4번] dist[4] < dist[6] + 10 이므로 dist[4] 는 갱신되지 않는다.
[정점5번] dist[5] < dist[6] + 1 이므로 dist[5] 는 갱신되지 않는다.
-> 아무 것도 갱신되지 않음
모든 정점을 다 확인했으므로 반복문을 종료한다.
최종적으로 시작점인 정점1번과의 각각의 정점의 최단거리는 다음과 같다.
dist[1] = 0
dist[2] =3
dist[3] = 4
dist[4] = 7
dist[5] = 6
dist[6] = 7
소스코드 :
<우선순위 큐를 이용한 다익스트라 알고리즘>
시간복잡도 : O(N*logN)
위의 우선순위 큐를 이용하지 않는 소스코드에서 check가 false인 정점들 중 거리가 최소인 정점을
선택하는 부분을 좀 더 자세히 보자.
위 코드에서는 1번부터 N번 정점까지 모든 정점을 매번 탐색하므로 N의 시작복잡도가 발생한다.
우리는 이 부분에서 우선순위 큐를 이용하여 시간복잡도를 줄일 수 있다.
우선순위 큐는 힙 정렬을 사용하기 때문에 logN의 시간복잡도로 매번 가장 작은 거리를 갖는 정점을 찾을 수 있다.
현재 정점과 인접한 정점들의 dist 를 갱신시키고 나서, 정점과 거리 정보를 우선순위 큐에 넣어준다.
그러면 우선순위 큐에는 check가 false인 정점들의 정보가 담기게 된다.
poll() 메서드를 호출하는 행위만으로 가장 짧은 거리를 갖는 정점의 정보를 얻을 수 있다.
우선순위 큐에 정점의 번호와 거리 정보를 넣기 위해 Pair 라는 클래스를 별도로 만들어서 정점 번호와 거리를 넣고,
우선순위 큐에 들어가는 자료형을 Pair로 설정하였다.
* 주의해야 할 것은, 기본 자료형이 아니기 때문에 Comparable 를 구현하여서 정렬 기준을 정해줘야 한다.
가장 짧은 거리부터 선택되어야 하므로 거리를 기준으로 오름차순이 되도록 compareTo()를 구현한다.
우선순위 큐를 이용한 소스코드 :
'Algorithm & DS > 그래프' 카테고리의 다른 글
| 플로이드 워셜(Floyd - Warshall) (0) | 2021.03.10 |
|---|---|
| BFS(Breadth First Search) - 너비 우선 탐색 (0) | 2021.02.25 |
| DFS(Depth First Search) - 깊이 우선 탐색 (0) | 2021.02.24 |
| MST(Minimum Spanning Tree) - 1. 프림 알고리즘 (0) | 2021.02.23 |
| 그래프 연결관계 - 인접 행렬, 인접 리스트 (0) | 2020.01.05 |