Dijkstra
정의
-
하나의 정점에서 나머지 모든 정점까지의 최단 거리를 찾는 알고리즘 이다.
-
모든 정점의 최단 거리를 구하는 플로이드 워셜 알고리즘과 다른 알고리즘 이다.
예제
출처 : https://www.acmicpc.net/problem/1753
예제의 입력을 그래프로 표현한 것 입니다.
시작점 1에서 다른 정점들 까지의 거리 중 최단거리에 있는 정점을 찾는 문제입니다.
풀이
1. 시작점 1번에서 직접 갈 수 있는 정점은 2번과 3번입니다. 그리고 문제의 조건에서 시작점 자신은 0으로 출력하라고 했으니 고려하여 테이블을 작성해보았습니다.
2. 현재 테이블 기준으로 자기 자신을 제외한 가장 가따운 정점을 선택하여 테이블을 갱신하는 알고리즘을 수행합니다.
2-1. 현재 테이블에서 가장 가까운(가중치가 적은) 정점을 선택합니다. (2번 선택)
2-2. 2-1)번에서 선택한 정점에서 갈 수 있는 정점을 조사합니다.
1. 해당 정점에서 갈 수 있는 경우를 조사합니다.
(2→3의 가중치 : 4 , 2→4의 가중치 : 5에 관한 데이터를 최소 힙에 넣어줍니다.)
2. 최소 힙에서 가장 가중치가 적은 노드를 선택합니다. (2→3의 가중치 : 4 선택)
시작점에서 해당 노드까지의 최소 거리를 확인 후 테이블을 갱신합니다.
(1→3의 가중치 : 3 , 1→2→3의 가중치 : 6(=2+4) 이므로, 현재 테이블을 유지합니다.)
(2→4의 가중치 : 5 선택)
(1→2→4의 가중치 : 7(=2+5)이고 현재 테이블의 값(INF)보다 작기 때문에, 테이블의 값을 7로 업데이트 합니다.)
(이어서 탐색할 필요가 있는 노드라고 판단하여 최소 힙에 넣어 줍니다.)2-3. 2-1 ~ 2-2의 과정을 최소 힙이 비어질 때까지 반복한다.
코드
import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize
# 정점의 개수 V, 간선의 개수 E
V, E = map(int, input().split())
# 시작점 K
K = int(input())
# 가중치 테이블
dp = [INF] * (V + 1)
# 최소 힙
heap = []
# 그래프
graph = [[] for _ in range(V + 1)]
# Dijkstra Algorithm
def Dijkstra(start):
# 가중치 테이블에서 시작 정점에 해당하는 가중치를 0으로 초기화
dp[start] = 0
# 최소 힙에 (가중치, 시작 정점)를 넣어줍니다.
heapq.heappush(heap, (0, start))
# 최소 힙에 원소가 없을 때 까지 반복
while heap:
# 최소 힙에서 가장 가중치가 적은 노드를 선택합니다.
weight, now = heapq.heappop(heap)
# 현재 테이블과 비교하여 불필요한(더 가중치가 큰) 튜플이면 무시.
if dp[now] < weight:
continue
# now 가 시작 지점인 모든 간선을 확인합니다.
for w, next_node in graph[now]:
# 현재 정점 까지의 최소 가중치 weight + 현재 정점에서 다음 정점(next_node)까지의 가중치 w
# = 다음 노드까지의 가중치 (next_weight)
next_weight = weight + w
# 다음 노드까지의 가중치(next_weight)가 현재 테이블(dp)에 기록된 값 보다 작으면
if next_weight < dp[next_node]:
# 계산했던 다음 노드의 가중치(next_weight)로 테이블(dp)을 갱신합니다.
dp[next_node] = next_weight
# 다음 정점 까지의 가중치와 다음 정점에 대한 정보를 최소 힙에 넣어줍니다.
heapq.heappush(heap, (next_weight, next_node))
# 초기화
for _ in range(E):
# u에서 v로 가는 가중치 w인 간선
u, v, w = map(int, input().split())
# (가중치, 목적지 노드) 형태로 저장
graph[u].append((w, v))
# Dijkstra Algorithm 수행
Dijkstra(K)
# 출력
for i in range(1, V+1):
if dp[i] == INF:
print("INF")
else:
print(dp[i])
https://github.com/yuseogi0218