[Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm)
이번 포스팅에서는 다익스트라 알고리즘(Dijkstra Algorithm)에 대해서 알아보겠습니다.
1.다익스트라 알고리즘(Dijkstra Algorithm)이란?
정의
:시작 정점에서 거리가 최소인 정점부터 선택해 나가면서 최단 경로를 구하는 방식의 알고리즘 그래프 방향의 유무는 상관 없으나, 간선들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다.
2.다익스트라 알고리즘(Dijkstra Algorithm)의 실질적 이용
가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다.
- 미로탐색 알고리즘
- 루빅스 큐브를 푸는 프로그램
- 네비게이션 길찾기
3.다익스트라 알고리즘(Dijkstra Algorithm) 그림설명
(1) 다익스트라 알고리즘은 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.
초기화가 실행된 후의 그래프.
- 출발지와 출발지의 거리는 확인해볼 필요도 없이 당연히 0 값을 가진다는 것을 알 수 있다. 출발지를 A로 설정했기 때문에, d[A]=0이 된다. (A노드를 아직 방문한 것은 아니다.)
- 출발지를 제외한 모든 노드들도 아직 확인되지 않았기에, d[다른 노드]=무한이 된다.
- Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
- S는 방문한 노드가 아직 없으므로 공집합 상태이다.
(2) 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.
첫 루프를 마치고 난 뒤의 그래프.
- 가장 먼저, 거리가 최소인 노드(d[N]이 최소값인 노드 N)를 Q(방문하지 않은 노드의 집합)에서 제거하고, 그 노드를 S(방문한 노드의 집합 및 최소 경로)에 추가한다. 이는 즉, 노드 N을 ‘방문한다’는 의미가 된다.
- 이후, 방문한 노드 N과 연결된 모든 이웃 노드와의 거리를 측정하여 dN + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)이 계산된다. 새로 계산된 값이 기존에 저장된 값보다 작은 경우에만 d[N]을 갱신한다.
-
예를 들어 초기화 직후의 첫 루프에서 거리가 최소인 노드는 A이므로, 노드 A를 방문하여 Q에서 제거하고 S에 추가하게 된다. 다만, 지금은 첫 번째 루프만을 끝낸 상태이므로, 단순히 0 + (이웃 노드와 출발지 사이의 거리값) = (출발지와 이웃 노드 간의 거리값)이 각 이웃 노드까지의 거리값으로 기록된다. 따라서, d[B] = 10, d[C] = 30, d[D] =15로 값을 갱신한다.
(3) 첫 루프 이후의 그래프의 상태가 업데이트되는 방식
두번째 루프를 마치고 난 뒤의 그래프.
- 이제 루프가 반복적으로 작동하는 방법을 설명한다. 밑의 그림들 또한 루프 안에서 알고리즘이 진행되는 순간들을 반복 설명한다. 이전에 설명했듯이, 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것으로 선택된다. 따라서, Q = {B, C, D, E, F} 중 B가 d[B] = 10으로 제일 작은 값을 가지므로, B를 방문하여 S에 추가하고 Q에서 제거한다.
- 이제, B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. B의 이웃 노드는 E뿐이므로, d[E] 값이 무한에서 d[B]+(B로부터 E까지의 거리값 20) = 30 으로 업데이트된다. 여기서 d[B] 값을 더하는 이유는 출발지부터 해당 노드까지의 거리값을 재기 위해서다.
(4) 더 빠른 경로를 발견한 경우
- 세 번째 루프에서 선택·방문되는 노드는 D이다. 두 번째 루프를 마친 후 Q의 원소 중에서 제일 낮은 d[N] 값을 가진 것이 D이기 때문이다. 따라서 세번째 루프를 마친 뒤인 위의 그림에서도 S에 D가 추가되어 있는 것을 볼 수 있다.
- 이제 D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트한다. 이 때 d[C]의 값은 A를 방문할 때 이미 계산되어 30으로 저장되해어 있었으나, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 그러므로, d[C]의 값을 30에서 20으로 변경한다.
- d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 변경한다.
(5) 또 다른 반복 루프 상황
- Q = {C,E,F} 중 d[C] = 20으로 거리가 가장 짧은 C를 방문하여, S는 {A, B, D, C}가 되었다.
- 다시 이웃 노드와의 거리 계산을 해보니,
이번에는 (A→D) + (D→F) = 15 + 20 = 35보다,
(A→D) + (D→C) + (C→F) = 15 + 5 + 5 = 25로
더 작은 값을 가지는 것이 발견되었다. d[F] = 25로 업데이트한다.
이 일련의 과정이 반복되어 Q가 공집합이 되었다면, 남아 있는 데이터로 추론하여 최단 거리를 결정한다.
(6) 결과
마지막 루프 이후, S = {A, B, D, C, F, E} (방문한 순서대로 정렬) d[A] = 0
d[B] = 10
d[C] = 20
d[D] = 15
d[E] = 30
d[F] = 25
Q = ∅
목적지가 F였으므로, A→D→C→F가 최단 경로이며, 거리는 25로 결정된다.