[백준] 1753(파이썬) - 최단경로

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

1753번: 최단경로

• 이 문제는 제목 그대로 최단경로, 즉 알고리즘 분류 중 다익스트라로 풀어내는 문제이다.
• 최단경로 문제는 다익스트라와 플로이드 워셜 정도가 있지만 둘이 차이는 아래와 같다.
  
  • 다익스트라 : 시작점으로 부터 나머지 정점까지 최단거리를 구할 때
  • 플로이드 워셜 : 각 정점간 최단경로를 구할 때
• 위를 고려해서 문제를 풀어주면 된다. 가장 기본적인 다익스트라 함수를 구현해서 문제를 풀어주었다.
• 각 인덱스(노드번호)마다 연결되어있는 노드와 경로 값을 넣어주고, 하나씩 heappop 해주면서 heappop으로 뽑아낸 노드가 가진 경로 값과 다른 경로를 통해 해당 노드로 이동할 때의 경로 값을 비교해줘서 작은 값을 distance [현재 노드]에 갱신해주는 방식으로 구현했다.

import sys
import heapq
input = sys.stdin.readline
INF = 100000000

V,e = map(int, input().split())
start = int(input())
data = [[] for _ in range(V+1)]
for _ in range(e):
    u, v, w = map(int, input().split())
    data[u].append((v, w))

distance = [INF]*(V+1)

q = []
def dijkstra(start):
    distance[start] = 0 
    heapq.heappush(q,(0,start))
    while q:
        # print(q)
        # print(data)
        # print(distance)
        dist, now_node = heapq.heappop(q)
        for n_n, weight in data[now_node]:
            cost = dist + weight
            if cost < distance[n_n]:
                distance[n_n] = cost
                heapq.heappush(q,(cost,n_n))

dijkstra(start)
for i in distance[1:]:
    if i != INF:
        print(i)
    else:
        print("INF")