[백준 1753번] 최단경로 - 다익스트라(Dijkstra Algorithm)

1753번: 최단경로

import sys
import heapq

input = sys.stdin.readline

v, e = map(int,input().split())

INF = float("inf")

graph = [[] for _ in range(v+1)]
distance = [INF]*(v+1)

start_node = int(input())

for _ in range(e):
    start, end, cost = map(int,input().split())
    graph[start].append((end,cost))

def dijkstra(start):
    
    distance[start] = 0
    
    q = []

    heapq.heappush(q,(0,start))
    
    while q:
        dist, current = heapq.heappop(q)
        
        if distance[current] < dist:
            continue
        
        for node, cost in graph[current]:
            new_cost = dist + cost

            if new_cost < distance[node]:
                distance[node] = new_cost
                heapq.heappush(q,(new_cost,node))

dijkstra(start_node)

for i in range(1,v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

이 문제 또한 다익스트라 알고리즘을 사용하여 '특정 지점에서 특정 지점으로 도착하는 최단 경로 및 최단 거리를 구하는 문제'이다.

 

heapq를 활용하여 보다 적은 시간복잡도로 그래프의 최단 경로 및 거리를 구할 수 있었던 문제였다 :)