다익스트라 알고리즘 관련 문제를 풀게되면서 다익스트라의 동작 방식이 이해가 안 가는 부분이 생겼다. 다익스트라 알고리즘은 간단하게 X를 거쳐 갈 수 있는 노드들에 대한 최단 거리를 갱신해준다. 또한 음의 간선은 허용하지 않고, 최단 경로를 구하는데 이때 중요한 규칙은 X를 거쳐갈 수 있는 노드 중 가장 짧은 거리의 노드를 먼저 선택해준다.
왜 가장 짧은 거리의 노드 먼저 선택하는걸까? 그냥 인접한 노드 중 아무거나 선택하면 어떻게 될까? 이 부분에 대해 공부해보았다.
먼저 다익스트라 알고리즘에 대해 간단히 정리하고 이유를 알아보자.
다익스트라 알고리즘
다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구할 수 있는 알고리즘이다. 음의 간선이 없을 때 사용하고, 매번 현재 알려진 가장 짧은 거리의 노드를 선택하는 그리디 방식을 사용한다.
1. 노드들의 최단 거리를 기록할 테이블을 초기화한다.
| 정점 | A | B | C | D |
|---|---|---|---|---|
| 최단거리 | 0 | ∞ | ∞ | ∞ |
그래프에 존재하는 정점이 A, B, C, D가 있고 처음 초기화를 할 때는 최단 거리를 무한으로 ㅊ포기화해준다. 이때 시작 노드가 A라면 A에 대한 값은 0으로 초기화해준다.
2. 노드 선택하고 거리 업데이트를 한다.
- 우선순위 큐에서 가장 거리가 짧은 노드를 선택해야한다.
- 이때 시작 노드는 A이므로 선택할 노드는 A가 된다.
- A를 거쳐 갈 수 있는 노드를 찾아본다.
- A를 거쳐갈 수 있는 노드는 B와 C가 있다.
- B와 C 중 거리가 더 짧은 간선은 B로 가는 간선이다.
- 그렇다면 A에서 B로 가는 거리는 최단 거리이므로 B까지 거리가 현재 무한이므로, 가는 거리인 2가 더 짧으므로 2로 업데이트해준다.
- 갱신된 정보인 B와 거리를 우선순위 큐에 넣어준다.
- 다음 큐에 저장된 C를 꺼내 최단 거리를 갱신해주고 C와 거리를 우선순위 큐에 넣어준다.
X를 거쳐갈 수 있는 노드에 대해 최단 경로라면 갱신해주고, 우선순위 큐에 넣어준다. 즉 큐에서 꺼내는 값이 X라면 X를 거쳐갈 수 있는 노드를 탐색해주고 탐색한 인접노드는 우선순위 큐에 넣어준다.
3. 큐가 빌 때까지 위 과정을 반복한다.
다익스트라 알고리즘 간단하게 정리하기
- 시작 노드에 대한 최단 경로는 0으로, 나머지 노드에 대해서는 ∞로 기록한다.
- 시작 노드를 우선순위 큐에 넣는다. (우선순위 큐는 항상 거리가 짧은 노드를 선택한다.)
- 시작 노드를 거쳐갈 수 있는 노드를 큐에 넣는다.
- 큐에서 노드를 꺼낸다. (시작 노드와 인접하면서 가장 짧은 노드 먼저 선택한다.)
- 선택된 노드를 X라 부르면 X를 거쳐갈 수 있는 노드들에 대해 거리를 저장해주고 큐에 넣는다.
- 위 과정을 계속해서 반복하며 큐가 빌 때까지 처리해준다.
- 최종적으로 큐가 빌 때까지 반복하게 되면 모든 노드까지의 최단 경로가 테이블에 저장된다.
시간복잡도는 어떻게 될까?
간선의 개수가 E이고, 정점의 개수가 V라면 시간복잡도는 O(ElogV)가 된다.
- 우선순위 큐를 사용하게 되면 삽입하고 삭제하는데 걸리는 시간복잡도는 O(logV)가 된다.
- 각 간선은 최대 한번 씩만 사용하게 된다. (여러번 간선을 사용하면 최단 경로를 구할 수 없다.) 모든 간선에 대해 우선순위 큐 연산을 수행한다.
- 즉, E*logV가 된다.
왜 다익스트라는 현재까지 알려진 최단 거리가 가장 짧은 노드를 택해야할까?
다익스트라 알고리즘의 다음 탐색 노드는 알려진 최단 거리가 가장 짧은 노드여야한다. 그렇다면 왜 그렇게 선택해야할까? 아무거나 인접한 노드를 선택하면 안되는걸까?
예를 들어 다음과 같은 그래프가 있다.
| 출발 | 도착 | 거리 |
|---|---|---|
| A | B | 2 |
| A | C | 5 |
| B | C | 2 |
| B | D | 4 |
| C | D | 1 |
출발을 A에서부터 한다고 가정한다.
- A에서 시작하면 B까지의 거리는 2, C까지의 거리는 5이다.
- 그렇다면 다익스트라 알고리즘에 따르면 다음 탐색은 C가 아닌 B가 되어야한다. 이 경우 큐에 탐색할 순서대로 B, C를 넣어준다.
B를 먼저 탐색하는 경우를 알아보자.
- B를 거쳐 갈 수 있는 곳은 C, D가 있다.
- 이때 B에서 C로 가는 거리가 2이기 때문에 A→C로 가는 거리는 C까지 가는 거리는 처음에 무한으로 저장되어있으므로 2(A→B)+2(B→C)=4로 갱신된다.
- 마찬가지로 D에도 처음 무한으로 그대로 저장되어 있는데 B를 거쳐 D로 가게 되면 2+4=6으로 갱신된다.
- 위에서 방문한 노드는 큐에 넣어두고(이후 이 노드를 거쳐 갈 수 있는 곳을 방문), C를 탐색한다. 그러나 A에서 C까지 거리는 4로 저장되어있어서 바로 가는 거리인 5가 더 크므로 갱신되지 않는다.
이 단계까지는 최단 경로 테이블은 아래와 같이 업데이트된다.
| 정점 | A | B | C | D |
|---|---|---|---|---|
| 최단거리 | 0 | 2 | 4 | 6 |
- B와 인접한 노드는 모두 거쳤으므로, B도 방문 표시를 해준다.
- 그 다음 C, D 중 작은 값인 4를 가지고 있는 C를 거쳐 갈 수 있는 곳을 탐색한다. C를 갈 수 있는 곳은 D 밖에 없으므로 D는 C를 거쳐 4+1=5로 갱신된다.
- 그렇다면 그 다음으로 탐색할 노드는 C에서 인접한 노드인 D 밖에 없다. D에서는 아무 곳도 갈 수 없으므로 탐색이 끝이난다. (D를 거쳐서 갈 수 있는 곳은 없다.)
위 과정을 살펴보면 A에서 C로 가는 길이 있음에도 탐색하지 않는다.
C를 먼저 탐색하게 되면 어떻게 될까?
| 정점 | A | B | C | D |
|---|---|---|---|---|
| 최단거리 | 0 | ∞ | 5 | ∞ |
- A를 거쳐 갈 수 있는 노드는 B, C가 있지만 C부터 방문할 것이므로 큐에는 [C, B]로 저장해준다.
- A를 거쳐 C로 가게되면 최단 거리는 5로 업데이트된다.
- C를 거쳐갈 수 있는 곳은 D 밖에 없으므로 A→C→D 값인 6으로 업데이트해주고, D를 저장해준다. 큐에는 [B, D]가 남아있다.
- B를 거쳐 갈 수 있는 곳은 C와 D인데, C는 이미 방문 표시를 했기 때문에 C를 방문할 수 없고, D만 방문할 수 있다. B를 거쳐 D를 가게되면 2+4=6으로 기존에 저장해둔 값인 6과 같아서 갱신되지는 않는다.
특정 노드 X를 거쳐 갈 수 있는 노드 중 거리가 짧은 노드를 먼저 선택하지 않으면 최단거리를 찾을 수 없게 된다.
X를 거쳐갈 수 있는 노드들에 대해 짧은 거리인 노드를 선택하지 않고 긴 노드를 먼저 선택해서 방문 처리를 하면 짧은 거리를 이용해 갈 수 있는지 탐색할 기회를 잃게 된다. 이미 방문 표시를 해버리기 때문에 탐색하지 않게 되는 것이다.
📌 항상 짧은 거리의 노드부터 선택하게 되면 그 노드까지의 거리는 이미 최단 거리인 것이 보장된다.
A와 인접한 노드 중 가장 짧은 거리 B를 먼저 선택하게 되는데, A에서 B까지의 거리는 최단 거리임을 보장할 수 있다. 왜냐하면 A에서 갈 수 있는 모든 노드 중 가장 짧은 거리라 다른 노드를 거쳐서 B로 가는건 항상 최단 거리가 아님을 보장한다. (다익스트라는 음의 간선을 취급하지 않기 때문이다.)
그래서 이 짧은 노드인 B를 거쳐 C를 가는 것을 확인해볼 수 있고 거치지 않고 A에서 C로 가는 것은 추후 또 확인할 수 있으므로 최단 경로를 찾을 수 있다. 반면 A에서 바로 C로 가는 것을 방문하게 되면 C를 거쳐 가는 D를 검사하게 되고 B를 거쳐 C를 가는 경로는 탐색할 기회가 사라진다.
다익스트라는 왜 음의 간선이 있으면 사용이 안될까?
위와 같은 그래프가 있고, 시작 노드를 A라고 한다.
그렇다면 다익스트라 알고리즘은 A를 거쳐 갈 수 있는 노드인 B 밖에 없으므로 A를 거쳐갈 수 있는 B의 최단 경로는 2로 갱신된다.
| 정점 | A | B | C | D |
|---|---|---|---|---|
| 최단거리 | 0 | 2 | ∞ | ∞ |
그렇다면 큐에는 B를 넣어주고 [B, 2]를 꺼내서 B를 거쳐갈 수 있는 노드인 C, E를 큐에 넣어준다. 큐의 상태는 [[C, 3], [E, 5]]이고 가장 짧은 값인 C를 선택해준다.
C를 거쳐갈 수 있는 건 D로 D까지의 거리는 4가 되고 이를 큐에 넣어준다.
큐의 현재 상태는 [[E, 5], [D, 4]]가 된다.
큐에서 [E, 5]를 꺼내주고 E를 거쳐갈 수 있는 곳은 없으므로 종료한다.
마지막으로 큐에서 D를 꺼내면 D로 갈 수 있는 곳은 B가 있지만 B는 이미 방문 표시를 해서 갈 수 없다. 음의 간선 -3으로 B로 가게되면 4-3으로 B까지의 거리는 1이 되어 최단 경로인데 이미 방문 표시를 해서 갱신될 수 없다.
그렇다면 A에서 B까지의 거리 2가 최단 경로라고 전제했기 때문에 B를 방문 표시해서 더 이상 방문하지 않아도 된다고 표시했는데 음의 간선이 있으므로 이 전제가 깨진 것이다.
또한 방문 표시를 없애고 보면 사이클이 생겨 여러 번 D를 거쳐 B로 가게 되면 음의 무한대로 최단 경로가 갱신되는 문제도 있다.
📌 음의 간선이 있다면 이미 처리한 노드의 거리가 나중에 더 짧아질 수 있어서 다익스트라에서 한 번 선택된 노드는 최단 거리로 확정되는 전제가 깨지게 된다. 다익스트라에서는 X를 거쳐갈 수 있는 노드 중 가장 짧은 거리의 노드는 최단 경로로 확정 지을 수 있다.
왜냐하면 X를 거쳐 갈 수 있는 노드가 여러 개인데 그 중 가장 짧은 노드가 Y라면, 다른 노드는 X→Y로 가는 값(a)보다 더 큰 값을 가진다. 그렇다면 다른 노드 Z를 거쳐 X→Z→Y로 가게 되면 이미 X→Z는 a보다 크기 때문에 Z를 거쳐 Y로 가는 경로는 최단 경로가 될 수 없다.
후훗. .