그래프상에서 가장 짧은 경로를 찾는 알고리즘
한 지점(시작)
에서 다른 모든 지점까지의 최단 경로를 계산
- 출발 노드 설정
- 최단거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 3-4 반복
우선순위 큐
를 사용하여 시간복잡도를 O(V^2)에서
O(ElogV)
(V: 노드개수, E: 간선개수)로 줄일 수 있다.
import sys
input=sys.stdin.readline
V, E = map(int, input().split())
K = int(input())
INF = int(1e9)
graph = [[] for _ in range(V+1)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append([v, w])
dist = [INF]*(V+1)
visited = [False]*(V+1)
# 인접한 노드 중 최단거리를 가지는 노드 반환
def get_smallest():
min_value = (0, INF)
for i in range(1, V+1):
if not visited[i] and dist[i] < min_value[1]:
min_value = (i, dist[i])
return min_value[0]
def Dijkstra(start):
dist[start] = 0
visited[start] = True
for (adj_node, weight) in graph[start]:
# 같은 노드간 여러 간선이 존재할 수 있으므로 if 문을 써준다
if dist[adj_node] > weight:
dist[adj_node] = weight
# 시작 노드를 제외한 다른 모든 노드를 순회
for _ in range(V-1):
# 인접 노드 중 최단거리 노드를 방문
now = get_smallest()
visited[now] = True
# 기존의 최단거리(시작-인접node) > 현재 방문한 노드를 거친 최단거리(시작-now + now-인접node)
# 일 경우 최단거리 테이블 갱신
for (adj_node, weight) in graph[now]:
cost = dist[now] + weight
if cost < dist[adj_node]:
dist[adj_node] = cost
Dijkstra(K)
for i in range(1,V+1):
print(dist[i] if dist[i] < INF else 'INF')
import sys
import heapq
sys.stdin = open('input.txt')
input=sys.stdin.readline
# 노드 개수, 간선 개수
V, E = map(int, input().split())
# 시작 노드 번호
K = int(input())
INF = int(1e9)
# 노드 연결 정보
graph = [[] for _ in range(V+1)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u].append([v, w])
# 최단거리 테이블
dist = [INF]*(V+1)
def Dijkstra(start):
q = []
# (거리, 노드번호)로 heapq에 넣어 거리순으로 정렬되도록 함
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
# now 노드에 오기까지 최단거리, 현재 노드번호
# heapq를 사용하여 최소힙으로 최단거리 부터 정렬됨
current_d, now = heapq.heappop(q)
# 최소힙을 사용하여
# visited를 사용하지 않아도 최단거리보다 클 경우 continue 하므로
# 이미 계산됨을 확인할 수 있음
if dist[now] < current_d:
continue
# now 노드와 인접한 노드확인
for (adj_node, weight) in graph[now]:
# now 노드까지의 최단거리 + 인접노드 까지 거리
total_d = current_d + weight
# 이전 측정한 인접노드까지의 최단거리 > 새로 측정한 최단거리
# -> 인접노드까지의 최단거리 테이블 갱신
if total_d < dist[adj_node]:
dist[adj_node] = total_d
heapq.heappush(q, (total_d, adj_node))
Dijkstra(K)
for i in range(1,V+1):
print(dist[i] if dist[i] < INF else 'INF')