[중급 알고리즘] 다익스트라 알고리즘

다익스트라 알고리즘은 그래프 이론에서 가장 짧은 경로를 찾는 데 사용되는 알고리즘 중 하나입니다. 주로 가중치 그래프에서 두 정점 사이의 최단 경로를 찾는 데 적용되며, 음의 가중치가 없는 경우에 최적의 결과를 보장합니다. 이 알고리즘은 네트워크 라우팅, GPS 네비게이션, 그래프 데이터베이스 등에서 활용됩니다.

다익스트라 알고리즘은 아래와 같은 단계로 작동합니다.

1. 시작 노드를 선택하고, 시작 노드에서 다른 모든 노드까지의 거리를 무한대로 초기화합니다. 시작 노드까지의 거리는 0으로 설정합니다.
2. 시작 노드와 연결된 모든 인접 노드에 대해 시작 노드로부터의 거리를 갱신합니다. 이때 각 간선의 가중치를 고려하여 거리를 계산합니다.
3. 아직 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택합니다. 이 노드를 현재 노드로 설정하고 방문 처리합니다.
4. 현재 노드와 연결된 노드들에 대해, 현재 노드를 거쳐서 각 노드까지의 거리를 계산하고, 이 거리가 기존 거리보다 짧으면 거리를 갱신합니다.
5. 모든 노드를 방문할 때까지 단계 3과 4를 반복합니다.

이제 예시를 통해 다익스트라 알고리즘을 이해해보겠습니다.

아래 그래프에서 A부터 F까지의 최단 경로를 다익스트라 알고리즘을 사용하여 찾아보겠습니다. 간선의 가중치는 편의상 아래와 같이 표시되어 있습니다.

       2      3
   A ----- B ----- C
   |       |     /
  1|       |4  / 1
   |       | /
   D ----- E
       5

1. A에서 시작합니다. A로부터의 거리는 0, 다른 노드는 무한대로 초기화합니다.
2. A와 연결된 B와 D를 선택합니다. B로 가는 거리는 2, D로 가는 거리는 1로 갱신합니다.
3. 현재 B에서 시작해서 C와 E를 선택합니다. C로 가는 거리는 3, E로 가는 거리는 4로 갱신합니다.
4. 현재 D에서 시작해서 E를 선택합니다. E로 가는 거리는 5로 갱신합니다.
5. 현재 C에서 시작해서 E를 선택합니다. E로 가는 거리는 4로 기존 값보다 짧으므로 갱신합니다.
6. 현재 E에서 시작해서 F를 선택합니다. F로 가는 거리는 5로 갱신합니다.

다익스트라 알고리즘을 마치면 각 노드까지의 최단 거리가 계산됩니다. 위 예시에서 A로부터의 최단 거리는 A(0), B(2), C(3), D(1), E(4), F(5)입니다.

다익스트라 알고리즘의 시간복잡도는 O(V^2)입니다. 하지만 우선순위 큐를 활용하여 O(E log V)로 최적화할 수 있습니다. 이 알고리즘을 이해하면 그래프에서 최단 경로를 찾는 다양한 문제에 활용할 수 있으며, 중급 개발자로서 그래프 이론과 알고리즘의 실제 적용에 대한 이해를 넓힐 수 있습니다.