: 한 노드에서 다른 노드로 가는 각각의 최단경로 구하기
간선의 가중치는 양수여야 한다.
그리디로 분류된다.
→ 매번 가장 비용이 적은 노드 선택
최단 거리 테이블 : 각 노드에 대한 현재까지의 최단 거리 정보 저장 → 계속 갱신
"방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택"을 반복하기
출발 노드 : 1
→ 모든 최단 거리를 무한(1e9)으로 초기화
→ 출발노드~출발노드는 0이므로 1번 노드 선택
현재 노드인 1번 노드를 거쳐 다른 노드로 가는 비용 계산
4번 노드를 거쳐 다른 노드로 가는 비용 계산
→ 최종 최단 거리 테이블
: 1번 노드에서 출발했을때, 2번까지 2, 3번까지 3, 4번까지 1, 5번까지 2, 6번까지 4라는 의미
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split()) #노드 개수, 간선 개수
start = int(input()) #시작 노드
graph = [[] for _ in range(n+1)] #노드 연결 정보
visited = [False]*(n+1) #방문 여부 체크 배열
distance = [INF]*(n+1) #최단 거리 테이블
for _ in range(m):
a,b,c = map(int, input().split()) #a->b의 비용 c
graph[a].append((b,c))
#방문하지 않은 노드 중, 최단거리가 가장 짧은 노드 찾기
def get_smallest_node():
min_val = INF
index = 0
for i in range(1, n+1):
if distance[i] < min_val and not visited[i]:
min_val = distance[i]
index = i
return index
def dijkstra(start):
#시작 노드 처리
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
for i in range(1, n-1):
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]:
distance[j[0]] = cost
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
→ 우선순위 큐에 더 짧은 경로를 찾은 노드 넣고, 꺼낼때는 해당 노드를 방문한 적이 있으면 무시, 아니면 처리해주면 된다.
→ Heap이란? [Python] Heap을 참고
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split()) #노드 개수, 간선 개수
start = int(input()) #시작 노드
graph = [[] for _ in range(n+1)] #노드 연결 정보
distance = [INF]*(n+1) #최단 거리 테이블
for _ in range(m):
a,b,c = map(int, input().split()) #a->b의 비용 c
graph[a].append((b,c))
def dijkstra(start):
#시작 노드 처리
pq = []
heapq.heappush(pq, (0, start))
distance[start] = 0
while pq:
dist, now = heapq.heappop(pq)
#현재 노드가 이미 처리된 적 있는 노드면,
if distance[now] < dist:
continue
#아니면,
for i in graph[now]:
cost = distance[now] + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(pq, (cost, i[0]))
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print("INF")
else:
print(distance[i])
나동빈님의 이것이 취업을 위한 코딩테스트다