백준(baekjoon) 1753번: 최단 경로(골드 4, 파이썬 PYTHON) - 최단 경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

import sys
import heapq

V,E=map(int,sys.stdin.readline().split())
K=int(sys.stdin.readline())
answer=[float('inf') for _ in range(V+1)]
graph=[[]for _ in range(V+1)]
queue=[]
answer[K]=0

for _ in range(E):
  u,v,w=map(int,sys.stdin.readline().split())
  graph[u].append([v,w])

heapq.heappush(queue,[0,K])

while queue:
  current_cost,current_point=heapq.heappop(queue)
  for x in graph[current_point]:
    cost=current_cost+x[1]
    if(cost>=answer[x[0]]):
      continue
    else:
      answer[x[0]]=cost
      heapq.heappush(queue,[cost,x[0]])

for x in range(1,V+1):
  if(answer[x]==float('inf')):
    print("INF")
  else:
    print(answer[x])

 

※ 최단 경로

 

 

● 현재 지점까지 오는 최소 거리와 현재 지점에서부터 가장 가까운 지점까지의 거리의 합을 cost 라는 변수에 저장한다. 이 cost 값이 현재 지점에서부터 가장 가까운 지점에 저장되어 있는 최소 거리보다 크거나 같으면 굳이 갱신해 줄 필요가 없으므로 넘어간다. 만약 cost 값이 더 작으면 현재 지점에서부터 가장 가까운 지점에 저장되어 있는 최소 거리를 cost로 갱신해 준 후, cost 와 이 지점 번호를 최소 힙에 저장한다. 매 단계마다 최소 힙에서 그때 저장했던 cost 값이 작은 순서대로 불러내게 된다.

 

● 모든 단계가 끝나고 각 지점까지의 최소 거리를 출력해주면 답을 구할 수 있다.

 

 

 

♣ 다익스트라 알고리즘

-> https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 알고리즘 - 나무위키