Algorithm: 다익스트라 (Dijkstra)

출처

다익스트라 (Dijkstra)

• 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로(Shortest Path)를 찾는 대표적인 알고리즘.

• 특징

  • BFS 개념을 확장하여 가중치가 있는 그래프의 최단 경로를 계산.

  • 음수 가중치가 있으면 사용할 수 없음.

  • DFS/BFS는 가중치 최단 경로 계산에 한계가 있으므로 다익스트라가 고안됨.

동작 원리

1. Distance 배열 초기화

   • 시작 정점에서 각 정점까지의 최단 거리를 저장.

   • 직접 연결되지 않은 정점은 무한대(∞) 로 설정.

2. 집합 S

   • 최단 거리가 확정된 정점들의 집합.

3. 반복 과정

   • S에 포함되지 않은 정점 중 Distance 값이 가장 작은 정점을 선택하여 S에 추가.

   • 선택한 정점을 거쳐 다른 정점으로 가는 경로가 더 짧으면 Distance 값 갱신.

4. 종료 조건

   • 모든 정점이 S에 포함될 때까지 반복.

예시 진행 흐름

• 시작: 정점 0 기준으로 거리 배열 설정.

• 최소 거리 정점 선택 → S에 추가 → 다른 정점들의 거리 갱신.

• 최소 거리 정점 반복 선택 및 갱신.

• 모든 정점이 선택되면 종료.

음수 가중치 불가

• 이유: 다익스트라는 “정점을 거칠수록 가중치가 증가한다”는 전제를 둠.

• 음수 가중치가 있으면, 이미 확정된 최단 거리가 뒤집힐 수 있어 알고리즘이 성립하지 않음.

• 대안: 벨만-포드(Bellman-Ford) 알고리즘은 음수 가중치도 처리 가능.

우선순위 큐 사용 이유

• 목적: 속도 최적화.

• 일반 큐 사용 시 결과는 같지만, 우선순위 큐를 쓰면

• 최소 거리 정점을 더 빠르게 선택 가능.

• 갱신 횟수와 추출 속도 모두 향상.

• 시간 복잡도

  • 일반 배열: O(V²)

  • 우선순위 큐(힙): O(E log V)

1. [백준] 최단경로

https://www.acmicpc.net/problem/1753