Dijkstra 알고리즘

컨테이너·2025년 11월 16일

알고리즘

목록 보기

9/10

Dijkstra Algorithm (다익스트라 알고리즘)

1. 정의

Dijkstra 알고리즘은 가중치가 있는 그래프에서, 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다.
모든 간선의 가중치가 0 이상(음수 가중치 없음) 이라는 조건에서 정확하게 동작한다.

다익스트라는 Greedy 전략을 기반으로 움직이며,
현재까지 발견된 거리 중 가장 짧은 정점을 먼저 선택해 확정시켜 나간다.

2. 핵심 아이디어

개념	설명
최단 거리 확정	시작점에서 가장 가까운 정점을 먼저 선택하고 그 거리를 최단 거리로 확정한다.
Greedy 선택	방문하지 않은 정점 중 현재까지의 거리가 가장 짧은 정점을 선택한다.
거리 갱신(Relaxation)	선택된 정점을 거쳐서 다른 정점으로 이동하는 경로가 더 짧다면 거리 값을 갱신한다.

핵심은 "이미 확정된 노드는 더 이상 최단 거리 값이 변하지 않는다" 는 점이다.

3. 작동 원리

다익스트라의 작동 과정을 단계별로 정리하면 다음과 같다.

시작 정점의 거리는 0, 나머지 정점의 거리는 무한대로 초기화한다.
아직 방문하지 않은 정점 중 거리 값이 가장 작은 정점을 선택한다.
해당 정점을 "최단 거리 확정" 처리한다.
그 정점과 연결된 이웃 정점들의 거리 값을 검사한다.
- 만약 현재거리 + 간선가중치 < 기존거리 이면 거리 값을 갱신한다.
모든 정점이 확정될 때까지 2~4를 반복한다.

4. 예시(간략 예시)

예를 들어 다음과 같은 그래프가 있다고 하자.

A에서 시작한다고 가정.
간선에는 모두 양의 가중치가 적혀 있다.

초기:

A의 거리 = 0
나머지 정점의 거리 = 무한대

1단계: A가 가장 가깝기 때문에 확정
그 이웃들의 거리 갱신
2단계: 갱신된 거리들 중 가장 가까운 정점을 선택
해당 정점 기준으로 또 이웃 거리 갱신
…
이 과정을 반복하면 모든 정점의 최단 거리가 계산된다.

5. 핵심 요소: 우선순위 큐 사용

정점을 선택할 때 “현재까지의 거리 값이 가장 작은 정점”을 빠르게 조회하기 위해
우선순위 큐(Priority Queue, Min Heap)을 사용하면 효율적으로 구현할 수 있다.

이를 통해 시간 복잡도는
O((V + E) log V)
정도로 안정된다.

6. 의사코드

function Dijkstra(Graph, start):
    dist[] ← 모든 값을 무한대로 초기화
    dist[start] ← 0

    우선순위 큐 PQ ← (0, start) 삽입

    while PQ가 비어있지 않음:
        (현재거리, u) ← PQ에서 거리 가장 작은 정점 추출
        if 현재거리 > dist[u]:
            continue

        for u와 연결된 모든 정점 v:
            새로운거리 = dist[u] + w(u, v)
            if 새로운거리 < dist[v]:
                dist[v] = 새로운거리
                PQ에 (dist[v], v) 삽입

    return dist

7. 특징 정리

특징	설명
Greedy 기반	항상 현재 가장 짧다고 알려진 경로를 먼저 확정한다.
음수 가중치 불가능	음수 간선이 있으면 Greedy 선택이 깨져 오답이 된다.
단일 출발 최단 경로	하나의 시작 정점에서 모든 정점까지의 최단 거리 계산.
우선순위 큐 사용 시 효율적	E가 많은 그래프에서도 빠르게 작동한다.

8. 장단점

항목	설명
장점	정확하고 빠르다. MST나 BFS보다 더 일반적인 상황에서 사용 가능.
단점	음수 가중치가 있으면 사용할 수 없다.

9. 관련 알고리즘과 비교

알고리즘	설명
BFS	간선 가중치가 모두 동일할 때 다익스트라와 동일한 결과.
Bellman-Ford	음수 가중치가 있을 때 사용 가능하지만 더 느림.
Floyd-Warshall	모든 정점에서 모든 정점까지의 최단 거리 계산.