다익스트라 알고리즘으로 최단 경로 찾기: 실전 예제
다익스트라 알고리즘으로 최단 경로 찾기: 실전 예제
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프 이론에서 가장 널리 사용되는 최단 경로 알고리즘 중 하나입니다. 이 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 정점으로 가는 최단 경로를 찾는 문제를 해결합니다. 다음 예제를 통해 이 알고리즘의 원리와 작동 방식을 자세히 살펴봅시다.
다익스트라 알고리즘의 개요
다익스트라 알고리즘은 한 정점을 시작점으로 하여 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘의 주요 아이디어는 다음과 같습니다:
- 최소 비용을 가진 정점 선택: 시작점에서 비용이 가장 적게 드는 정점을 선택합니다.
- 경로 비용 업데이트: 선택한 정점과 인접한 정점들의 경로 비용을 현재 경로 비용을 기준으로 업데이트합니다.
- 반복: 모든 정점을 처리할 때까지 위의 단계를 반복합니다.
알고리즘의 세부 단계
다음 단계는 다익스트라 알고리즘의 세부 작동 방식입니다:
- 초기화: 시작점에서 모든 정점까지의 거리를 무한대로 설정하고, 시작점의 거리는 0으로 설정합니다. 또한, 시작점을 포함한 집합과 포함되지 않은 집합을 나눕니다.
- 정점 선택: 포함되지 않은 집합에서 가장 작은 경로 비용을 가진 정점을 선택하여 포함된 집합에 추가합니다.
- 경로 업데이트: 선택한 정점의 인접한 정점들의 경로 비용을 업데이트합니다. 이때, 새로운 경로 비용이 기존 경로 비용보다 작으면 업데이트합니다.
- 반복: 모든 정점이 포함된 집합에 추가될 때까지 2번과 3번 단계를 반복합니다.
실전 예제
다음은 간단한 그래프 예제입니다. 이 그래프에서 다익스트라 알고리즘을 실행하여 최단 경로를 찾는 과정을 단계별로 설명하겠습니다:
예제 그래프
A
/ \
1/ \4
/ \
B C
| \ |
3| \2 |2
| \ |
D------ E
3- A에서 B로 가는 경로의 비용은 1입니다.
- A에서 C로 가는 경로의 비용은 4입니다.
- B에서 D로 가는 경로의 비용은 3입니다.
- B에서 E로 가는 경로의 비용은 2입니다.
- C에서 E로 가는 경로의 비용은 2입니다.
- D에서 E로 가는 경로의 비용은 3입니다.
단계 1: 초기화
모든 정점의 초기 거리를 무한대로 설정하고, 시작점 A의 거리를 0으로 설정합니다:
- A: 0
- B: ∞
- C: ∞
- D: ∞
- E: ∞
단계 2: 최소 비용 정점 선택
현재 최소 거리 정점은 A입니다 (0). A를 선택하여 포함된 집합에 추가합니다.
단계 3: 경로 업데이트
A의 인접한 정점인 B와 C의 거리를 업데이트합니다. A에서 B는 1, A에서 C는 4로 업데이트됩니다:
- A: 0
- B: 1
- C: 4
- D: ∞
- E: ∞
단계 4: 반복
최소 비용의 정점 B를 선택하여 포함된 집합에 추가합니다. B의 인접한 정점의 경로를 업데이트합니다. B에서 D는 1+3=4, B에서 E는 1+2=3으로 업데이트됩니다:
- A: 0
- B: 1
- C: 4
- D: 4
- E: 3
다음으로, 최소 거리 정점 E를 선택하여 포함된 집합에 추가합니다. E에서 D는 3+3=6, E에서 C는 3+2=5만큼의 경로를 업데이트합니다. 하지만 C의 기존 경로가 더 적으므로 업데이트하지 않습니다.
단계 반복
이제, D와 C의 경로가 4로 동일하지만, 먼저 추가된 D를 사용하여 C를 추가합니다. 업데이틉 시도 여부를 확인 해줍니다.
최종 상태:
- A: 0
- B: 1
- C: 4
- D: 4
- E: 3
최종 결과
다익스트라 알고리즘을 통해 최단 경로는 아래와 같습니다:
- A → B: 1
- A → B → E : 3
- A → C: 4
- A → B → D: 4
결론
다익스트라 알고리즘은 그래프에서 최단 경로를 찾는데 매우 유용합니다. 초기화, 최소 비용 정점 선택, 경로 업데이트, 반복이라는 단계를 통해 더 효율적으로 문제를 해결할 수 있습니다. 이 알고리즘의 실제 적용과 개선 방법을 학습하면, 다양한 실전 문제에서도 유용하게 활용할 수 있습니다.