다익스트라 알고리즘(Dijkstra's Algorithm)은
간선(edge)의 가중치가 있는 그래프에서 시작점이 고정되어 있을 때
모든 정점(vertex, 복수형은 vertices)으로 가는 최단 경로의 거리 합을 모두 구하는 알고리즘으로
에드거 다익스트라(Edsger Dijkstra) 가 1959년에 발표했다.
알고리즘을 설명하기 앞서 몇가지 기호들을 정의하고 시작한다.
$PL$ : Permanent Label 라는 의미로, 확실하게 최단거리 계산이 끝난 정점들이 들어가는 집합이다.
$TL$ : Temporary Label 라는 의미로, 집합 PL에 포함된 정점을 거쳐 갈 수 있는 최단거리가 계산된 정점의 집합이다.
$L_j$ : 시작점에서 정점 $j$ 까지 도달하기 위한 확실한 최소 거리로써 $PL$ 집합의 원소에 대해서만 사용한다.
$\tilde{L}_j$ : 시작점에서 정점 $j$ 까지 도달하기 위한 임시 최소 거리로써 $TL$ 집합의 원소에 대해서만 사용한다.
다익스트라 알고리즘 (Dijkstra's Algorithm)
1. 초기조건 설정하기
■ 정점 $1$ 을 $PL$ 집합에 넣는다. $L_1 = 0$ 으로 설정한다.
■ 정점 $j (= 2, 3, \cdots, n)$ 은 $TL$ 집합에 넣는다.
이 때 $\tilde{L}_j = l_{1j}$ 로 설정한다. 만약 간선 $l_{1j}$ 가 없으면 $\tilde{L}_j = \infty$ 로 둔다.
2. $TL$ 에서 정점을 하나 선택하여 $PL$ 에 넣기
■ 정점 $k$ 를 선택할 것인데, $k$ 는 $TL$ 의 원소 중 가장 작은 $\tilde{L}_j$ 값을 갖는 $j$ 이다.
만약 여러개가 있으면 그들 중 가장 작은 값을 택한다.
■ 만약 $TL = \varnothing$ 이면 OUTPUT 으로 $L_1, L_2, \cdots, L_n$ 을 출력하고 종료한다.
3. $TL$ 업데이트 하기
■ $TL$ 의 모든 정점 $j$ 에 대해 $\tilde{L}_j = \min(\tilde{L}_j, \; L_k + l_{kj})$ 를 계산하여 업데이트 해준다.
여기서 $k$ 는 2번에서 구한 그 $k$ 이다. 2번으로 돌아가 종료될 때까지 반복한다.
상세 설명
1번의 초기조건을 설정한 후 종료될 때까지 2번과 3번을 반복해서 오가는 구조임을 알 수 있다.
다음의 예시 그래프를 이용해 자세한 설명을 하겠다.
시작점을 편의상 정점 $1$ 이라고 하자.
1번 과정을 거친 후 집합 $PL$ 과 $TL$ 은 다음과 같다.
$$ PL = \{1\} \quad TL = \{2, 3, 4, 5\} $$
그리고 $L_j$ 와 $\tilde{L}_j$ 들은 다음과 같다.
$$\begin{cases} L_1 = \textcolor{red}{0} \\ \\ \tilde{L}_2 = 8 \\ \tilde{L}_3 = 5 \\ \tilde{L}_4 = 7 \\ \tilde{L}_5 = \infty \end{cases} $$
해석하자면, 최단거리가 확실하게 정해진 정점은 $1$ 뿐이고
$2, 3, 4, 5$ 는 아직 최단거리가 완벽히 계산되지 않은 정점이다.
또한 $1$ 은 시작점이므로 시작점에서 시작점까지 가는 거리는 $L_1 = \textcolor{red}{0}$ 로써 확실히 정해지며
현재 단계에서 확실히 최단거리가 정해진 $1$ 을 통해 (다시 말 해 집합 $PL$ 의 원소인 정점으로 부터)
단 한 번의 이동으로 도달할 수 있는 거리들이 $\tilde{L}_j$ 로써 각각 $8, 5, 7, \infty$ 로 정해진 것이다.
(무한인 것은 현재 최단거리가 확실한 $PL$ 집합의 정점으로부터 단 한번의 이동으로 도달 못하기 때문이다.)
이제 2번 과정을 진행한다.
$\tilde{L}_j$ 중 가장 작은 값을 갖는 것은 $\tilde{L}_\textcolor{red}{3} = 5$ 이므로 $\textcolor{red}{k = 3}$ 이다.
정점 $3$ 까지 도달하는 최단 거리는 다음과 같이 확실하게 정해질 수 있음을 관찰하자.
$$ \begin{align} &\textcolor{skyblue}0 &+ &\textcolor{limegreen}5 &= 5 \\ &\textcolor{skyblue}{\text{정점 1까지 도달하는 최소거리}} &+ &\textcolor{limegreen}{\text{정점1에서 단 한번의 이동으로 정점3까지 도달하는 거리}} & \end{align} $$
만약 $\tilde{L}_j$ 가 가장 작은 값을 갖는 $k = 3$ 을 택하지 않고 예를들어 $k=2$ 를 택한다면
정점 $2$ 까지 이동하는 최단거리가 $\tilde{L}_2 = 8$ 이라고 확실히 말 할 수 없게 된다.
왜냐하면 더 짧은 다른 곳을 거쳐서 정점 $2$ 로 갈 수 있는 여지가 있기 때문이다.
당장 위 그래프만 봐도 정점 $3$ 을 거쳐서 $2$ 로 가는 것이 $6$ 의 거리로 $\tilde{L}_2 = 8$ 보다 작음을 알 수 있다.
하지만 애초부터 $\tilde{L}_j$ 중 최솟값을 택하면 다른 곳을 거쳐서 더 짧은 거리로 $k$ 까지 도달할 여지가 사라지므로
$\tilde{L}_j$ 는 $k$ 까지 도달하는 확실한 최단거리임이 보장된다.
최단거리가 확실하게 정해졌으므로 $3$ 을 $TL$ 에서 제거하여 $PL$ 에 넣어준다.
$$ PL = \{1, \textcolor{red}{3}\} \quad TL = \{2, 4, 5\} $$
$$\begin{cases} L_1 = 0 \\ \textcolor{red}{L_3 = 5} \\ \\ \tilde{L}_2 = 8 \\ \tilde{L}_4 = 7 \\ \tilde{L}_5 = \infty \end{cases} $$
3번 과정으로 넘어가자.
$\tilde{L}_j$ 들을 업데이트 해주어야 한다.
왜냐하면 기존의 $\tilde{L}_j$ 들은 $PL$ 의 원소의 정점중 하나를 거쳐
단 한 개의 간선 이동으로 도달할 수 있는 최단거리들을 나타내던 값인데
(지금까지는 $PL$ 의 원소가 $1$ 뿐이였기 때문에 이 경우에는 $1$ 을 거쳐 단 한번의 이동으로 도달할 수 있는 최단거리)
$PL$ 에 정점 $3$ 이 추가되었기 때문에 기존의 $PL$ 을 거쳐서 가는 최단거리 vs $3$ 을 거쳐서 가는 최단거리를 비교해서 작은 값을 넣어줘야 $TL$ 의 의미가 유지되기 때문이다.
다음과 같이 모든 $TL$ 정점들의 $\tilde{L}_j$ 값을 업데이트 해주자.
$$ \begin{cases} \textcolor{orange}{\tilde{L}_2} = \min{ (\tilde{L}_2 \textcolor{skyblue}{= 8}, L_3 + l_{32} \textcolor{skyblue}{= 5 + 1}) } = \textcolor{orange}{6} \\ \textcolor{orange}{\tilde{L}_4} = \min{ (\tilde{L}_4 \textcolor{skyblue}{= 7}, L_3 + l_{34} \textcolor{skyblue}{= 5 + \infty}) } = \textcolor{orange}{7} \\ \textcolor{orange}{\tilde{L}_5} = \min{ (\tilde{L}_5 \textcolor{skyblue}{= \infty}, L_3 + l_{35} \textcolor{skyblue}{= 5 + \infty}) } = \textcolor{orange}{\infty} \end{cases} $$
즉, 3번 과정을 거치면 다음과 같이 마무리 된다.
$$ PL = \{1, 3\} \quad TL = \{2, 4, 5\} $$
$$\begin{cases} L_1 = 0 \\ L_3 = 5 \\ \\ \tilde{L}_2 = \textcolor{red}{6} \\ \tilde{L}_4 = 7 \\ \tilde{L}_5 = \infty \end{cases} $$
아직 $TL$ 의 원소가 남아있기 때문에 다시 2번 과정으로 넘어간다.
남은 $TL$ 원소 중 $\tilde{L}_j$ 가 가장 작은 값은 $\tilde{L}_\textcolor{red}{2} = 6$ 이므로 이번엔 $\textcolor{red}{k = 2}$ 이다.
정점 $2$ 를 $PL$ 로 옮겨주면 다음과 같이 마무리 된다.
$$ PL = \{1, \textcolor{red}{2}, 3\} \quad TL = \{4, 5\} $$
$$\begin{cases} L_1 = 0 \\ \textcolor{red}{L_2 = 6} \\ L_3 = 5 \\ \\ \tilde{L}_4 = 7 \\ \tilde{L}_5 = \infty \end{cases} $$
다시 3번 과정으로 넘어왔다.
$PL$ 에 원소가 추가되었으므로 $\tilde{L}_j$ 들을 업데이트 해주어야 한다.
역시나 같은 이유인데, 현재 $\tilde{L}_j$ 값들은 $PL$ 의 원소인 $1$ 또는 $3$ 을 거쳐서
단 하나의 간선 이동으로 도달할 수 있는 최소 거리를 나타내는데,
$PL$ 에 원소가 추가되었으니 새로 비교해야하기 때문이다.
다음과 같이 $\tilde{L}_j$ 들을 업데이트 해주자.
$$ \begin{cases} \textcolor{orange}{\tilde{L}_4} = \min{ (\tilde{L}_4 \textcolor{skyblue}{= 7}, L_2 + l_{24} \textcolor{skyblue}{= 6 + 2}) } = \textcolor{orange}{7} \\ \textcolor{orange}{\tilde{L}_5} = \min{ (\tilde{L}_5 \textcolor{skyblue}{= \infty}, L_2 + l_{25} \textcolor{skyblue}{= 6 + \infty}) } = \textcolor{orange}{\infty} \end{cases} $$
이번 업데이트로 결론적으로 바뀐 값은 없다.
다시 2번 과정을 거치면 결과는 다음과 같다.
$\textcolor{red}{k = 4}$ 이고
$$ PL = \{1, 2, 3, \textcolor{red}{4}\} \quad TL = \{ 5 \} $$
$$\begin{cases} L_1 = 0 \\ L_2 = 6 \\ L_3 = 5 \\ \textcolor{red}{L_4 = 7} \\ \\ \tilde{L}_5 = \infty \end{cases} $$
다음 3번 과정을 진행하자.
$$ \textcolor{orange}{\tilde{L}_5} = \min{ (\tilde{L}_5 \textcolor{skyblue}{= \infty}, L_4 + l_{45} \textcolor{skyblue}{= 7 + 2}) } = \textcolor{orange}{9} $$
따라서 다음과 같이 정리된다.
$$ PL = \{1, 2, 3, 4\} \quad TL = \{ 5 \} $$
$$\begin{cases} L_1 = 0 \\ L_2 = 6 \\ L_3 = 5 \\ L_4 = 7 \\ \\ \tilde{L}_5 = \textcolor{red}{9} \end{cases} $$
다시 2번으로 돌아왔는데, $TL$ 의 원소가 $5$ 하나 밖에 남지 않았다.
이를 $PL$ 로 옮겨주면 $TL$ 이 공집합이 되므로 종료될 것이다.
결과는 다음과 같다.
$$ PL = \{1, 2, 3, 4, \textcolor{red}{5} \} \quad TL = \varnothing $$
$$\begin{cases} L_1 = 0 \\ L_2 = 6 \\ L_3 = 5 \\ L_4 = 7 \\ \textcolor{red}{L_5 = 9} \end{cases} $$
OUTPUT 으로 $L_1$ 부터 $L_5$ 까지 출력하며 알고리즘은 종료된다.
요약
이 알고리즘이 진행되는 양상을 표현하자면, 확실하게 최단거리를 바로 알 수 있는 시작점부터 시작해서
시작점 근처의 점들부터 멀리 있는 점들까지 확실한 최단거리를 정해주는 방식이다.
핵심은 다음과 같다.
정점 $j$ 까지의 최단거리는 현재까지 최단거리라고 여겨지는 값이 $\tilde{L}_j$ 이고
$j$ 까지 도달하기 한 간선 이전의 정점 중 최단거리가 확실하게 계산된 정점을 $i$ 라고 하면,
모든 $i$ 에 대해 $L_i$ 와 $\tilde{L}_j$ 를 비교해서 가장 작은 값을 $L_j$ 로써 택한다는 것이다.
다익스트라 알고리즘을 구현한 코드는 바쁜 사정상 다음에 작성해서 올려볼 것이다.