08-4 다익스트라
- 다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
- 기능: 출발 노드와 모든 노드 간 최단 거리 탐색
- 특징: 에지는 모두 양수
- 시간 복잡도(노드 수: V, 에지 수: E): O(ElogV)
- 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때, 다익스트라 알고리즘을 사용하면 해결할 수 있다.
[다익스트라 알고리즘 핵심 이론]
1. 인접 리스트로 그래프 구현하기
다익스트라 알고리즘은 시간 복잡도 측면에서 인접 리스트를 선택하는 것이 좋다. 그래프 연결을 표현하기 위해 인접 리스트에 연결한 input 데이터 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결한다.
2. 최단 거리 리스트 초기화하기
최단 거리 리스트를 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다. 이때 무한은 적당히 큰 값을 사용하면 된다.
3. 값이 가장 작은 노드 고르기
최단 거리 리스트에서 현재 값이 가장 작은 노드를 고른다. 현재는 값이 0인 출발 노드에서 시작하면 된다.
4. 최단 거리 리스트 업데이트하기
선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다. 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트한다.
5. 3~4번 과정을 반복해 최단 거리 리스트 완성하기
모든 노드가 처리될 때까지 3~4번 과정을 반복한다. 4번 과정에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 리스트를 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 리스트가 완성된다.
📌 문제 056) 최단 경로 구하기
시간 제한 1초, 골드 V, 백준 1753번
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
5 6 # 노드 개수, 에지 개수 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
0 2 3 7 INF
1단계 문제 분석
- 시작점과 다른 노드와 관련된 최단 거리를 구하는 문제로, 다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지 묻고 있다.
- 인접 리스트에 노드를 저장하고 거리 리스트를 초기화한다. 거리 리스트는 앞에서 설명했듯이 출발 노드는 0, 나머지는 무한으로 초기화한다.
- 최초 시작점은 우선순위 큐에 삽입하고, 다음 과정에 따라 다익스트라 알고리즘을 수행한다.
[다익스트라 알고리즘 수행 과정]
(1) 거리 리스트에서 아직 바문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다. 즉, 우선순위 큐에서 데이터를 뽑아온다.
(2) 해당 노드와 연결된 노드들의 최단 거릿값을 다음 공식을 이용해 업데이트한다.
- [연결 노드 거리 리스트 값]보다 [선택 노드의 거리 리스트 값 + 에지 가중치]가 더 작은 경우 업데이트 수행
- 업데이트가 수행되는 경우 연결 노드를 우선순위 큐에 삽입
(3) 큐가 빌 때까지 (1)~(2)를 반복한다.
- 완성된 거리 리스트의 값을 출력한다.
2단계 슈도 코드
V(노드 개수), E(에지 개수)
K(출발 노드)
distance(거리 저장 리스트) # 충분히 큰 수로 초기화
visited(방문 여부 저장 리스트)
myList(에지 데이터 저장 인접 리스트)
q(다익스트라를 위한 우선순위 큐)
for 에지 개수만큼 반복:
인접 리스트에 에지 정보 저장
# 다익스트라 수행
출발 노드는 우선순위 큐에 넣고 시작 # 자동으로 거리가 최소인 노드를 선택
거리 리스트에 출발 노드의 값을 0으로 설정
while 큐가 빌 때까지:
우선순위 큐에서 노드 가져오기
현재 선택된 노드를 방문한 적이 있는지 확인
현재 노드를 방문 노드로 업데이트
for 현재 선택 노드의 에지 개수:
if 연결 노드 방문 전 and 현재 선택 노드 최단 거리 + 비용 < 연결 노드의 최단 거리:
연결 노드 최단 거리 업데이트
우선순위 큐에 연결 노드 추가
완성된 거리 리스트를 탐색해 출력3단계 코드 구현
import sys
input = sys.stdin.readline
from queue import PriorityQueue
V, E = map(int, input().split())
K = int(input())
distance = [sys.maxsize] * (V + 1)
visited = [False] * (V + 1)
myList = [[] for _ in range(V + 1)]
q = PriorityQueue()
for _ in range(E):
u, v, w = map(int, input().split()) # 가중치가 있는 인접 리스트 저장
myList[u].append((v, w))
q.put((0, K)) # K를 시작점으로 설정
distance[K] = 0
while q.qsize() > 0:
current = q.get()
c_v = current[1]
if visited[c_v]:
continue
visited[c_v] = True
for tmp in myList[c_v]:
next = tmp[0]
value = tmp[1]
if distance[next] > distance[c_v] + value: # 최소 거리로 업데이트
distance[next] = distance[c_v] + value
# 가중치가 정렬 기준이므로 순서를 가중치, 목표 노드 순으로 우선순위 큐 설정
q.put((distance[next], next))
for i in range(1, V + 1):
if visited[i]:
print(distance[i])
else:
print("INF")