Dijkstra 알고리즘에 관하여

최단 거리를 빠르게 계산해주는 알고리즘이다.

Negative cycle이 없어야만 정당하게 돌아간다. 일반적으로 모든 간선의 거리가 0 이상일 때 사용한다.

시작 정점에서부터 임의의 정점까지 도달하는데 필요한 거리 배열을 구한다.

 

처음 배웠을 때 굉장히 어려웠던 알고리즘으로 기억한다.

알고리즘이 작동하는 방식보다도 수학적인 매커니즘이나 직관을 잡는데 시간이 오래 걸렸다. 개인적으로 탐욕법과 관련된 모든 것들이 처음 습득하기가 다 어려운 것 같다..

확실히 응용 문제를 많이 다루면서 개념이 점점 잡힌다.

 

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

다익스트라 알고리즘이 제대로 돌아가는지 확인할 수 있는 문제이다.

 

 

https://www.acmicpc.net/problem/2982

2982번: 국왕의 방문

가중치가 실시간으로 바뀌는 다익스트라.

직관적으로 알고리즘을 세우기는 간단하다.

정당성 증명을 귀납법+귀류법으로 시도해보면 다익스트라의 증명과 공통되는 부분이 많다.

오히려 구현이 더 까다로울 수 있는 문제.

 

 

https://www.acmicpc.net/problem/16311

16311번: Harry the Hamster

문제 설명:

햄스터는 가중치(거리)가 있는 방향 그래프를 간선을 따라 이동한다. 초기 위치와 도착점의 위치가 노드 번호로 주어진다. 햄스터는 이중자아가 있는데, 한 자아는 최대한 늦게 도착점에 가고싶어하고, 다른 자아는 최대한 빨리 도착점에 가고싶어한다. 간선을 이동하는데 걸리는 시간은 간선의 거리와 같으며, 이동 간선 하나당 이 두 자아를 1회씩 번갈아가면서 사용한다.(처음에는 늦게 도착점에 가고자하는 자아를 먼저 사용한다.) 두 자아가 각각 합리적으로 선택할 때 도착점으로 가는데 걸리는 시간을 구하는 문제이다.

 

첫 번째 자아가 잘 선택하면 무한 루프를 돌 수도 있다. 이 때는 "infinity"를 출력한다.

 

점화식을 세워보자.

$$ Mn[a] = \min \{ w + Mx[b] \} $$

$$ Mx[a] = \max \{ w + Mn[b] \} $$

 

트리가 아니므로 minimax로 접근하는 것은 좋은 생각이 아니다.

도착점에서 위 두 배열 값이 잘 정의된다는 점에서 간선을 반대방향으로 뒤집은 그래프를 생각하면 된다는 것을 알 수 있다.

 

$Mn$ 배열의 원소값으로부터 주변의 $Mx$ 값을 계산하고, $Mx$ 배열의 원소값으로부터 주변의 $Mn$ 값을 계산하자. 하지만 $Mn$ 값은 점점 작아지고 $Mx$ 값은 커지므로 우선순위큐를 무작정 사용하면 안 된다.

 

$Mx$ 배열의 경우 주변의 $Mn$ 값들이 모두 계산되어야 값이 고정될 수가 있다. 그 전에는 절대 큐에서 빼서 경로 업데이트를 해주면 안 된다.

또한 주변 $Mx$ 배열을 업데이트해주는 상황에서는 최소 힙을 사용하여 $Mn$ 값이 가장 작은 값을 우선적으로 골라야 한다. 이 때 pop 된 노드의 $Mn$ 값은 다익스트라 알고리즘과 같은 원리로 앞으로 더 증가하지 않는다.

 

생각보다 어려운 문제였다.. 스스로 다익스트라 알고리즘 증명을 제대로 이해하고 응용할 수 있는지 확인하고 싶다면 이 문제가 정말 좋은 것 같다.

 

 

https://www.acmicpc.net/problem/15292

15292번: Journey from Petersburg to Moscow

문제 설명:

가중치(거리)가 있는 방향 그래프가 주어진다.(노드와 간선의 수가 최대 3000개밖에 안 된다! <- 어려운 문제라는 뜻) 시작점과 도착점과 한 자연수 $K$가 주어진다. 시작점에서 도착점으로 가는 경로의 비용은 아래와 같다.

• 만약 $K$개 이하의 간선들만 통해 도착한다면 경로 상에 위치한 간선의 거리의 합이 곧 비용이다.
• 만약 $K$개 이상의 간선들을 통해 도착한다면. 지나온 간선의 거리를 정렬하여 $c_1 \geq c_2 \geq c_3 \geq \cdots \geq c_l$ 이라고 하자. $\sum_{i=1}^K c_i$ 가 바로 비용이다. 즉 비싼 거리 $K$개의 합만 비용으로 치겠다는 것이다.

이 때 시작점에서 도착점으로 가는 최소 비용을 구하여라.

 

문제를 보고 바로 들었던 생각은 '왜 간선의 수도 똑같이 작을까?' 였다. 각 간선에 대한 정보를 이용하여 다익스트라 알고리즘을 여러 번 돌리면 될 것 같았다.

경로에서 순환을 없애는 것으로는 절대 손해를 보지 않는다. 단순 경로만 구하면 되므로 다익스트라 알고리즘이 정당하다.

 

가중치가 $w_i$인 간선 $e_i = (a_i, b_i)$를 고르자. $e_i$가 딱 $K$ 번째로 가중치가 큰 간선이 되도록 경로를 찾을 수 있을까?

그래프의 모든 간선의 가중치를 $w_j \Rightarrow \max(w_j - w_i, 0)$ 으로 바꾼다면 어떻게 될까? 바뀐 그래프에서 다익스트라 알고리즘을 통해 시작점에서 도착점으로 가는 최소 비용을 구하고, 그 값에 $Kw_i$를 더한 값을 $T_i$ 라고 하자.

마치 최단 경로를 찾아 $K$번째로 거리가 먼 간선까지 가중치를 원상복구시켜는 효과를 주는 것이다.

 

여기서 구한 $T_i$ 값이 문제에서 주어진 최소비용보다 항상 크거나 같음은 case work를 통해 증명할 수 있다.

또한 만약 간선 $e_i$가 딱 $K$번째가 되도록 하는 최단 경로가 존재한다면,  $T_i$ 값은 그 최단 경로의 비용과 완전히 같다.

길이 $K$ 만큼 굳이 사용하지 않아도 더 빠르게 도착하는 경로가 존재할 수 있다. 원래 그래프에서 다익스트라를 돌려 나온 최단 거리도 후보로 넣어주자.

 

 

간선을 조작하는 문제는 경로 문제에서 한 번씩은 생각해 볼 만하다.(다익스트라, 벨만포드(Karp 알고리즘), MST)

특히 정확히 'K'개의 경로'만' 어떻게 해라고 하는 문제에서는 필수적으로 떠올릴만한 사항인 것 같다.

 

옛날 학교 알고리즘 과제로 나왔던 TSP 문제에서 가중치를 모두 $a$ 씩 더하면 어떻게 되는가?에 대한 문제가 기억난다. 정확히는 이것을 이용하여 TSP의 특이한 경우의 해를 빠르게 구하는 알고리즘을 찾는 문제였는데.. 자세히는 기억 안 난다. TSP 경로는 항상 간선을 $N-1$개 지나므로 가중치를 더해도 해가 여전히 유지된다는 점을 이용했던 것 같다. MST도 마찬가지고 말이다.

 

 

누구나 만만하게 사용하는 다익스트라.. 하지만 내부를 완벽히 이해하는데는 시간이 걸리고 그만큼 매력적인 알고리즘인 것 같다.