다익스트라 알고리즘은 가중치가 있는 그래프에서 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 '그리디' 알고리즘으로 분류되며, 매 단계마다 가장 가까운 정점을 선택하여 최단 경로를 갱신합니다.
다익스트라 알고리즘의 동작 과정을 살펴보겠습니다. 다음은 예시 그래프입니다.
```
A--4--B--2--E
/ \ | |
2 5 1 3
/ \ | |
S--3--D--6--C--T
```
우리의 목표는 출발점 S로부터 모든 정점까지의 최단 경로를 찾는 것입니다. 다익스트라 알고리즘은 다음과 같은 단계로 동작합니다.
1. 출발점 S를 선택하고, S의 최단 경로를 0으로 초기화합니다. 다른 정점의 최단 경로는 무한대로 설정합니다.
2. 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점을 선택합니다. 이를 현재 정점으로 설정합니다.
- 초기 단계에서는 S를 선택합니다.
3. 현재 정점과 인접한 정점들의 최단 경로를 갱신합니다. 인접한 정점들의 최단 경로가 현재 경로보다 더 짧을 경우, 해당 경로를 갱신합니다.
4. 모든 정점을 방문할 때까지 2-3 단계를 반복합니다.
위 그래프에 다익스트라 알고리즘을 적용해보겠습니다.
1단계: 출발점 S를 선택하고, S의 최단 경로를 0으로 초기화합니다. 다른 정점의 최단 경로는 무한대로 설정합니다.
- S: 0, A: ∞, B: ∞, C: ∞, D: ∞, E: ∞, T: ∞
2단계: 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점 A를 선택합니다.
- S: 0, A: 4, B: ∞, C: ∞, D: ∞, E: ∞, T: ∞
3단계: A와 인접한 정점들의 최단 경로를 갱신합니다.
- S: 0, A: 4, B: 6, C: ∞, D: ∞, E: ∞, T: ∞
4단계: 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점 B를 선택합니다.
- S: 0, A: 4, B: 6, C: ∞, D: ∞, E: ∞, T: ∞
5단계: B와 인접한 정점들의 최단 경로를 갱신합니다.
- S: 0, A: 4, B: 6, C: 8, D: ∞, E: ∞, T: ∞
6단계: 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점 C를 선택합니다.
- S: 0, A: 4, B: 6, C: 8, D: ∞, E: ∞, T: ∞
7단계: C와 인접한 정점들의 최단 경로를 갱신합니다.
- S: 0, A: 4, B: 6, C: 8, D: ∞, E: 9, T: ∞
8단계: 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점 D를 선택합니다.
- S: 0, A: 4, B: 6, C: 8, D: 11, E: 9, T: ∞
9단계: D와 인접한 정점들의 최단 경로를 갱신합니다.
- S: 0, A: 4, B: 6, C: 8, D: 11, E: 9, T: ∞
10단계: 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점 E를 선택합니다.
- S: 0, A: 4, B: 6, C: 8, D: 11, E: 9, T: ∞
11단계: E와 인접한 정점들의 최단 경로를 갱신합니다.
- S: 0, A: 4, B: 6, C: 8, D: 11, E: 9, T: 12
12단계: 아직 방문하지 않은 정점 중에서 최단 경로가 가장 짧은 정점 T를 선택합니다.
- S: 0, A: 4, B: 6, C: 8, D: 11, E: 9, T: 12
최종 결과로, 출발점 S로부터 각 정점까지의 최단 경로를 찾았습니다. 결과는 다음과 같습니다.
- S에서 A까지의 최단 경로: [S, A], 거리: 4
- S에서 B까지의 최단 경로: [S, A, B], 거리: 6
- S에서 C까지의 최단 경로: [S, A, B, C], 거리: 8
- S에서 D까지의 최단 경로: [S, A, B, C, D], 거리: 11
- S에서 E까지의 최단 경로: [S, A, B, E], 거리: 9
- S에서 T까지의 최단 경로: [S, A, B, E, T], 거리: 12
이와 같이 다익스트라 알고리즘을 통해 출발점으로부터 각 정점까지의 최단 경로와 거리를 찾을 수 있습니다.
다익스트라 알고리즘의 시간 복잡도는 일반적으로 정점의 수를 V, 간선의 수를 E라고 할 때 O((V+E)logV)입니다. 이는 우선순위 큐를 사용하여 최단 경로를 찾는 과정에서 logV의 시간이 소요되기 때문입니다.
다익스트라 알고리즘은 최단 경로 탐색에 많이 활용되며, 네트워크 라우팅, GPS 기반 경로 탐색 등 다양한 응용 분야에서 활용됩니다.
댓글