다익스트라 도입

1. 접근

지금까지 최단경로 문제를 접근하는 알고리즘은 BFS 밖에 배우지 않았다.

하지만 BFS로는 간선에 가중치가 부여된 그래프에서의 최단경로를 풀 수 없다.

중간 노드를 거치는 경로의 간선 수는 많아도, 가중치의 합은 적은 경우를 반영해줄 수 없기 때문이다.

따라서 우리는 가중치가 부여된 최단경로 문제를 위해 다익스트라 알고리즘을 새로 배워야 한다.

다익스트라 알고리즘은 음의 가중치가 없는(0도 허용한다) 그래프에서, 한 노드에서 나머지 모든 노드들 까지의 최단경로를 구해준다.

음의 가중치를 가지는 그래프에서의 최단경로 문제는 플로이드-워셜 / 벨만포드 알고리즘 을 사용해야 한다고 한다..

이제부터 이 알고리즘이 어떻게 동작하는지 단계별로 살펴보자.

0. 정의

• 집합 S = 방문한 노드들의 집합

• d[N] = A노드에서 N까지의 최단 거리

• 집합 Q = 방문하지 않은 노드들의 집합

1. 아직 확인되지 않은 d[x]는 모두 무한으로 초기화한다.

초기화가 실행된 후의 그래프. (노드 A에서 나머지 모든 노드들까지의 최단 경로를 구하고자 한다.)

2. 첫 루프 : 이웃 노드들을 방문하고 d[x]를 갱신한다.

첫 루프를 마치고 난 뒤의 그래프.

• d[N]이 최소값인 노드 N을 Q에서 제거하고, S에 추가한다. 즉, N을 방문한다.

• N의 이웃 노드와의 거리를 측정하여

• d[N](=출발지로부터 N까지 계산된 최소 거리값) + (N과 이웃 노드 간의 거리값) = (출발지부터 이웃 노드까지의 거리값)

• d[B] = 10, d[C] = 30, d[D] =15 는 Infinity보다 작으므로 갱신된다.

3. 두 번째 루프 : 이웃 노드들을 방문하고 d[x]를 갱신한다.

두 번째 루프를 마치고 난 뒤의 그래프.

• 방문할 노드는 Q에 남아있는 노드들 중 d[N] 값이 제일 작은 것(d[B]=10)으로 선택된다. B를 방문하여 S에 추가하고 Q에서 제거한다.

• B의 이웃 노드들을 모두 탐색하여 거리를 재고 d[N]에 기록한다. d[E] 값이 무한에서 d[B]+(B와 E 사이의 값 = 20) = 30 으로 업데이트된다.

4. 세 번째 루프 : 더 작은 d[x]를 발견한다면?

• Q의 원소 중에서 제일 낮은 d[N] 값을 가지고 있기 때문에 방문되는 노드는 D이다.

• D의 이웃 노드들(C, F)의 거리를 잰 후, d[N]값을 업데이트해야 하는데, d[C]의 값이 A를 방문할 때 이미 계산되어 30으로 정해져 있었다. 하지만, D를 방문하여 C와의 거리를 확인해 보니 20으로 더 짧은 최단 경로가 발견되었다! 따라서 d[C]의 값을 30에서 20으로 갱신한다.

• d[F]의 경우는 원래의 값이 무한이므로, 더 작은 값인 15+20=35로 갱신한다.

5. Q가 공집합이 될 때 까지 루프를 반복한다.

• 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 = ∅

알고리즘의 흐름을 보면, 계속 가중치가 작은 간선을 골라 인접한 노드들의 데이터를 갱신해나가는 과정이란 것을 알 수 있다.

따라서 이 알고리즘은, 한 정점에서 다른 정점까지의 최단경로는, 중간에 방문하는 노드들도 최단경로로 방문해야 한다고 주장하는 것이다.

생각해보면 당연하다. A에서 C로 가는 최단경로가 A-(10)->B-(20)->C = 30라고 해보자.

만약 중간 노드인 B까지의 최단경로가 사실은 A-(3)->D-(4)->B = 7라고 한다면, 왜 A에서 C까지 가는데 D를 거치지 않겠는가?

당연히 거치는게 더 짧은 경로다. A-(3)->D-(4)->B->-(20)->C = 27

따라서 최단경로는 최단경로들로 이뤄져있다는 주장은 타당하다.

구현에서의 문제는 없을까? 초창기 이 알고리즘의 시간복잡도는 O(V^2) 였다고 한다.

문제는 Q집합 중에서 d[x]가 가장 작은 원소를 찾아 내는게 공짜가 아닌데 있었다.

지금은 최소-힙으로 Q집합을 유지하면서 O(E * logV)로 줄었다.

최소-힙에 정점은 최대 V^2번 들어가고, (힙의 삽입은 O(logN)) 간선은 E번 봐야 하므로 O(E * log(V^2)) = O(E * logV) 이다.

2. 풀이

최소 힙은 친절히도 <queue> 라이브러리에 priority_queue 를 이용해 쉽게 구현 가능하다.

우선순위 큐의 디폴트는 가장 큰 수를 top에 유지하므로 가중치를 음수화시켜 저장하거나, 큐의 선언에 greater를 쓰면 된다.

문제는 대놓고 다익스트라 알고리즘을 쓰라는 문제로, 시작점은 하나 주어지고 나머지 노드들 까지의 최단경로를 구해야 한다.

이중 벡터로 그래프를 구현하고, 집합 Q는 우선순위 큐로, d[x]는 거리를 저장하는 시퀀스를 선언해 구현해보자.

알고리즘의 구현에 대해 더 깊게 생각해보면, 꼭 INF의 초기화와 계산값을 비교하여 갱신하는 과정이 항상 필요할까?

BFS에서 편했던 점은 방문 노드를 표시하여, 다음 번엔 방문하지 않는 꼼수가 있었는데, 다익스트라는 불가능 할까?

실은 최소 힙을 쓰면서 해결된 의문점이다. 이미 INF에서 갱신된(방문한) 노드는 나중에 다시 경로값을 계산하지 않아도 된다.

무슨 소리냐, 앞에서 노드 C는 갱신하지 않았냐고 의문이 들겠지만,

이는 A의 이웃인 C를 큐에 넣으면서 갱신한데서 비롯되는 문제다. 따라서 큐에서 꺼낼 때만 d[x]를 갱신한다면,

최단경로는 최단경로의 합이란 논리하에 나중에 갱신된 값이 다시 갱신될 일은 없다.

4. 후기

최단경로 문제는 널리고 널렸다. 네이게이셔등의 현실과도 밀접한 알고리즘이기도 하다. 숙지하도록 하자.

다른 최단경로 문제들도 계속 소개하고자 한다.

알고리즘의 그래프 사진들과 설명은 위키백과를 참고하였다.

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

1) 1753 최단경로 : https://www.acmicpc.net/problem/1753