[알고리즘] 4. 최단 거리 - Dijkstra 알고리즘

[알고리즘] 4. 최단 거리 - Dijkstra 알고리즘

1. Shortest Path

Shortest Path (이하 $S.P.$) 문제는 Source (시작점) 부터 다른 모든 노드로 가는 $S.P.$를 구하는 것이 목적이다. 예를 들어 서울에서 부산까지의 $S.P.$에는 서울과 부산 사이에 지나가는 모든 지역까지의 $S.P.$도 포함되어 있다. 즉, $S.P.$의 모든 부분은 $S.P.$이다.

Versions of S.P.

- 각 노드별 $S.P.$의 길이만 구하기

- 각 노드별 실제 $S.P.$ 구하기

- 각 노드별 모든 가능한 $S.P.$ 구하기

2. Dijkstra 알고리즘의 Idea

용어 정의

- $G = (V, E)$: 그래프 입력 - 정점과 엣지들

- $n$: 노드의 총 개수

- $v_0$: Source Node

- $d_{min}$: $S.P.$ length (출력될 정답)

- $g(v, u)$: $v$ 에서 $u$ 로 가는 Edge Weight

- $R$: Red Set. 여기 속한 노드들의 $d_{min}(v)$는 최종 정답을 의미함

- $B$: Blue Set. 여기 속한 노드들의 $d_{min}(w)$는 Red Set만 거치는 $S.P.$의 길이를 의미함

- Input: $Dijkstra(G,\ n,\ v_0,\ d_{min})$

Source와 연결된 모든 정점마다 Edge Weight 를 $d_{min}(v)$에 넣어 갱신한다. Source와 연결되지 않은 노드들로의 Edge Weight는 $\infty$라고 가정한다. $R$ 에 Source 노드를 넣는다. Red 집합의 크기가 $n$이 될때까지 다음 과정(3번)을 반복한다. $R$ 바깥에 있는 $d_{min}(u)$들 중 가장 작은 값을 가진 노드 $u$를 찾아서 $R$에 넣는다. 그리고 $R$에 속하지 않는 노드들 $w$에 대해서 $min(d_{min}(w), d_{min}(u) + g(u, w))$ 값으로 집합 $B$를 갱신시켜준다.

3. 각 노드들의 S.P.의 길이

Dijkstra Algorithm이 각 노드들의 S.P.의 길이를 찾을 수 있음을 증명하자.

Base: $n=1$ 즉, Source 노드 하나만 존재하므로 $d_{min}(v_0) = 0$ 으로 주장이 성립한다. Step: 어떤 시점에 집합 $R = {v_0, v_1, ..., v_i}$, $B = {w_0, w_1, ..., w_j}$ 이라고 하자. $B$ 에 속한 노드들 중 $d_{min}(w)$ 값이 가장 작은 노드를 $w$ 라고 하자. 이 노드를 집합 $R$에 추가하자. $R$ 집합에 $B$에 있던 노드 $u$를 추가하면, $u$를 통하는 더 좋은 길이 생길 수 있기 때문에 집합 $B$의 $d_{min}(w)$ 값들을 모두 $min(d_{min}(w), d_{min}(u) + g(u, w))$ 값으로 갱신해줘야 한다.

집합 $B$에 속하는 노드들 중 $d_{min}(w)$가 제일 작은 것을 넣는 것이 정당한 이유

$w$가 다음에 집합 $R$에 추가할 노드가 아니라면, $R$ 집합을 거쳐서 오는 제일 짧은 것이 아니라는 뜻이므로 $B$ 집합의 노드를 거쳐서 와야 더 짧아진다. 그 경로에서 처음으로 만난 $B$ 집합의 노드를 반드시 존재하는데, 그 노드는 $d_{min}(w)$ 보다 항상 크다. 따라서 모순이 발생하므로, $w$를 넣는 것이 정당하다.

$u \rightarrow w$ 인 경우만 따지는 것이 정당한 이유 (중간에 다른 노드를 거치지 않는 이유)

$u \rightarrow v \rightarrow w$인 경우가 $w$까지의 $S.P.$ 이라고 가정해보자. $u$는 방금 집합 $R$에 들어갔기 때문에, $v$는 그 이전에 집합 $R$에 들어가있었다. 즉, $v$가 $R$에 들어간 시점에는 $u$가 $R$ 바깥에 있었다. 이 경우, source에서 $v$로 가는 $S.P.$ 중에서 $u$를 안쓰고 $R$에 속하는 경로가 존재하게 된다. 따라서 $u$가 필요 없어지므로 가정에 모순이다. 그러므로 $u \rightarrow w$인 경우만 따지는 것이 정당하다.

4. 실제 S.P.를 찾을 수 있는 S.P. 트리

Dijkstra Algorithm을 통해 각 노드들의 실제 S.P.를 찾을 수 있는 S.P. Tree를 만들 수 있음을 증명하자.

모든 노드는 최단경로 내에서 자기 앞에 무슨 노드가 있는지 알고 있다고 가정하자. $R$ 집합에 $B$에 있던 노드 $u$를 추가할 때, 현재 $B$에 있는 노드 $w$ 까지의 기존 S.P.와 $u \rightarrow w$ 를 통과하는 새로운 경로 중에서 더 짧은 것으로 경로가 갱신된다. 거리가 같을 경우, $u \rightarrow w$의 새로운 경로를 버리고 기존 S.P.를 선택한다. 따라서 S.P. Tree가 만들어진다.

5. 각 노드들의 모든 가능한 S.P. 찾기

Dijkstra Algorithm을 통해 모든 가능한 S.P. 들을 찾을 수 있음을 증명하자.

모든 노드는 최단경로 내에서 자기 앞에 무슨 노드가 있는지 알고 있다고 가정하자. $R$ 집합에 $B$에 있던 노드 $u$를 추가할 때, 현재 $B$에 있는 노드 $w$ 까지의 기존 S.P.와 $u \rightarrow w$ 를 통과하는 새로운 경로 중에서 더 짧은 것으로 경로가 갱신된다. 거리가 같을 경우, 두 노드의 정보를 모두 저장하면 된다. 따라서 S.P. DAG(Directed Acyclic Graph)가 만들어진다.

6. Dijkstra 알고리즘의 노드 선택 순서

Dijkstra Algorithm 이 집합 $R$에 넣는 노드들을 순서대로 $V_1, V_2, ..., V_n$ 라고 할 때, 모든 $k$에 대하여 $d_{min}(V_k) \leq d_{min}(V_{k+1})$ 임을 증명하자. (가까운 순서대로 선택하는 것을 보이자.)

$V_k$가 집합 $R$에 있고, $V_{k+1}$이 집합 $B$에 있을 때는 정의에 의해 $d_{min}(V_k) \leq d_{min}(V_{k+1})$ 이다. 집합 $R$에 $V_{k+1}$이 들어간 후, 두 가지 케이스를 고려할 수 있다.

$d_{min}(V_{k+1})$가 바뀌지 않는 경우: 성립한다.

$d_{min}(V_{k+1})$가 바뀌는 경우: $d_{min}(V_{k+1}) = d_{min}(V_k) + g(V_k, V_{k+1}) \geq d_{min}(V_k)$ 이므로 성립한다.

따라서 모든 $k$에 대하여 $d_{min}(V_k) \leq d_{min}(V_{k+1})$ 이다. 즉, 이미 집합 $R$에 들어간 것들과 direct하게 연결된 edge들만 보면 $V_{k+1}$을 반드시 찾을 수 있다.

7. Dijkstra 알고리즘의 구현과 성능

$\left\vert V \right\vert = n,\ \left\vert E \right\vert = m$ 이라 하자. Source와 연결된 모든 정점마다 Edge Weight 를 $d_{min}(v)$에 넣어 갱신한다. Source와 연결되지 않은 노드들로의 Edge Weight는 $\infty$라고 가정한다. - $O(n)$ $R$ 에 Source 노드를 넣는다. - $O(1)$ $R$ 바깥에 있는 $d_{min}(u)$들 중 가장 작은 값을 가진 노드 $u$를 찾아서 $R$에 넣는다. 그리고 $R$에 속하지 않는 노드들 $w$에 대해서 $min(d_{min}(w), d_{min}(u) + g(u, w))$ 값으로 집합 $B$를 갱신시켜준다. - 가장 작은 $d_{min}(u)$는 Priority Queue를 사용하여 검색하므로 $O(log n)$이 걸린다. 그리고 갱신할 때는 $u$와 인접한 노드들만 따지면 된다. 갱신하는 것도 $O(\log n)$이 걸리고, 이 행위를 모든 Edge들에 해야하므로 총 $m$번 일어난다. 따라서 $O(m\log n)$의 시간이 걸린다.

\[ \therefore T(n) = O(m\log n) \]

8. BFS로 표현한 Dijkstra 알고리즘

노드 사이의 Edge Weight 만큼 더미 노드를 삽입하면 BFS를 통해 S.P.를 구할수도 있다. ($\because$ 모든 Edge Weight가 1로 맞춰짐) 모든 Edge Weight가 같을 경우 BFS를 통해 S.P.를 구할 수 있다는 것을 이용한 것이다. 이 경우에는 Priority Queue를 사용하지 않고 그냥 Queue만 쓴다. 하지만 엄청 느려지는 단점이 존재한다.

9. Prim 알고리즘과의 비교

Prim 알고리즘은 지금까지 방문한 노드들에 연결된 엣지의 가중치 중 최소인 것을 선택하지만, Dijkstra 알고리즘으로 바꾸려면 시작점으로부터 이동했을 때 누적된 엣지의 가중치 중 최소인 것을 선택해야 한다.

from http://pongkijoa.tistory.com/11 by ccl(A) rewrite - 2021-12-27 11:01:19