728x90
가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
단, 모든 간선의 가중치는 0 이상
핵심 이론
- 인접 리스트로 그래프 구현
- 최단 거리 배열 초기화
- 값이 가장 작은 노드 선택
- 최단 거리 배열 업데이트
- 3, 4 반복하여 최단 거리 배열 완성
1. 인접리스트로 그래프 구현
인접 행렬로 구현해도 좋으나 시간 복잡도 측면에서 N크기가 클 것을 대비해 인접 리스트로 구현하는 게 나음
그래프의 연결을 표현하기 위해 배열의 자료형은 `(노드, 가중치)` 형태로 선언하여 연결
2. 최단 거리 배열 초기화
출발 노드는 0, 나머지 노드는 무한으로 초기화
이때 무한은 적당히 큰 값을 사용
3. 값이 가장 작은 노드 구하기
최단 거리 배열에서 현재 값이 가장 작은 노드 선택, 처음에는 출발 노드를 선택하면 됨
4. 최단 거리 배열 업데이트
- 선택된 노드에 연결된 가중치 값을 바탕으로 다른 노드의 값 없데이트
- 1단계에서 저장해 둔 연결 리스트를 이용해 현재 선택된 노드의 간선 탐색 & 업데이트
- 연결 노드의 최단 거리는 두 값 중 더 작은 값 선택
👉 `Min (선택 노드의 D[N] 값 + 가중치, 연결 노드의 D[N] 값)`
5. 3 ~ 4 반복하여 최단 거리 배열 완성
선택 노드가 될 때마다, 다시 선택되지 않도록 방문처리 및 모든 노드가 방문될 때까지 반복하면
최단거리 배열 완성!
정리
다익스트라는 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이고, 간선은 항상 양수여야 함
출발 노드와 도착 노드 간의 최단 거리가 아닌, 출발 노드와 그외 모든 노드 간의 최단 거리를 표현함
관련 문제
[백준, 최단경로] https://www.acmicpc.net/problem/1753
[백준, 최소비용 구하기] https://www.acmicpc.net/problem/1916
[백준, K번째 최단경로 찾기] https://www.acmicpc.net/problem/1854
728x90