다익스트라 최단 경로 알고리즘

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘입니다.

단, 모든 간선의 가중치가 0 이상이어야 합니다. 음수 가중치가 있으면 다익스트라 알고리즘을 사용할 수 없습니다.

핵심 아이디어

현재까지 가장 가까운 정점을 하나씩 선택하고, 그 정점을 거쳐 가는 경로가 더 짧은지 확인합니다.

즉,

“현재 가장 가까운 정점은 최단 거리가 확정되었다고 보고, 그 정점을 이용해 주변 정점의 거리를 개선한다.”

이 과정을 반복합니다.

예시 그래프

       2
   A ------ B
   |        |
  5|        |1
   |        |
   C ------ D
       2

시작 정점을 A라고 하겠습니다.

• A → B: 2
• A → C: 5
• B → D: 1
• C → D: 2

A에서 D로 가는 방법은 두 가지입니다.

• A → B → D = 2 + 1 = 3
• A → C → D = 5 + 2 = 7

따라서 최단 거리는 A → B → D, 거리 3입니다.

알고리즘 진행 과정

시작점 A의 거리를 0으로 설정하고, 나머지는 무한대로 설정합니다.

1단계: A 선택

A에서 갈 수 있는 정점을 확인합니다.

• B까지 거리: 2
• C까지 거리: 5

2단계: 가장 가까운 B 선택

아직 처리하지 않은 정점 중 B의 거리가 가장 작습니다.

B에서 D로 갈 수 있으므로 거리를 계산합니다.

A → B → D = 2 + 1 = 3

기존 D의 거리보다 작으므로 D의 거리를 3으로 바꿉니다.

3단계: 가장 가까운 D 선택

D의 거리는 3입니다. D에서 더 짧은 경로가 만들어지는지 확인하지만, 새로운 최단 경로는 없습니다.

4단계: C 확인

C의 거리는 5입니다. C를 거쳐 D로 가면 다음과 같습니다.

A → C → D = 5 + 2 = 7

현재 D의 거리 3보다 크므로 바꾸지 않습니다.

최종 결과는 다음과 같습니다.

A에서 A까지: 0
A에서 B까지: 2
A에서 C까지: 5
A에서 D까지: 3

일반적인 수행 절차

1. 시작 정점의 거리를 0으로 설정합니다.
2. 나머지 정점의 거리를 무한대로 설정합니다.
3. 아직 처리하지 않은 정점 중 현재 거리가 가장 작은 정점을 선택합니다.
4. 선택한 정점과 연결된 모든 정점을 확인합니다.
5. 더 짧은 경로를 발견하면 거리를 갱신합니다.
6. 모든 정점을 처리할 때까지 반복합니다.

거리를 갱신하는 과정은 다음과 같이 표현할 수 있습니다.

새로운 거리 = 현재 정점까지의 거리 + 간선의 가중치

새로운 거리가 기존 거리보다 작으면 값을 바꿉니다.

의사 코드

거리[start] = 0
다른 모든 정점의 거리 = 무한대

반복:
    아직 방문하지 않은 정점 중
    거리가 가장 작은 정점 u를 선택

    u를 방문 처리

    u와 연결된 각 정점 v에 대해:
        새로운 거리 = 거리[u] + u에서 v까지의 가중치

        새로운 거리가 더 작다면:
            거리[v] = 새로운 거리

실제 구현에서는 가장 가까운 정점을 빠르게 찾기 위해 보통 우선순위 큐를 사용합니다.

시간 복잡도

정점의 개수를 V, 간선의 개수를 E라고 하면:

• 단순 배열 사용: O(V²)
• 우선순위 큐 사용: O((V + E) log V)

일반적으로 그래프가 크다면 우선순위 큐를 사용하는 방법이 효율적입니다.

주의할 점

다익스트라 알고리즘은 간선의 가중치가 음수이면 사용할 수 없습니다.

예를 들어 다음과 같은 간선이 있다면:

A → B의 비용 = -3

다익스트라 알고리즘 대신 벨만-포드 알고리즘을 사용해야 합니다.

한 문장 요약

다익스트라 알고리즘은 현재 가장 가까운 정점을 차례로 확정하면서, 그 정점을 거치는 더 짧은 경로가 있는지 확인하는 최단 경로 알고리즘입니다.