[Python] 1753 최단경로

👉 1753 최단경로

[정답 코드]

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

def dijkstra(graph, h, visited, distance):
    while h:
        node = heapq.heappop(h)  # node[0] == weight, node[1] == vertex
        if visited[node[1]] != 1:
            visited[node[1]] = 1
            if graph.get(node[1]):
                for v, w in graph[node[1]]:
                    if distance[v] > distance[node[1]] + w:
                        distance[v] = distance[node[1]] + w
                    heapq.heappush(h, (distance[v], v))
                

v, e = map(int, input().split())
start = int(input())
graph = {}
visited = [-1] * (v + 1)
distance = [INF] * (v + 1)
h = [] # min heap
for i in range(e):
    u, v, w = map(int, input().split())
    if graph.get(u):
        graph[u].append((v, w))
    else:
        graph[u] = [(v, w)]
visited[start] = 1
distance[start] = 0
for v, w in graph[start]:
    if distance[v] > w:
        distance[v] = w
    heapq.heappush(h, (w, v))
dijkstra(graph, h, visited, distance)


for i in range(1, len(distance)):
    if distance[i] == 9999999:
        print('INF')
    else:
        print(distance[i])

[풀이]
우선순위 큐를 사용한 다익스트라 알고리즘으로 구현하였다. (python heapq 모듈은 tuple을 push할 경우 첫 번째 인자를 우선순위에 고려하기 때문에, (weight, vertex) 형식으로 heappush하였다.)

[적용 자료구조 및 알고리즘]

• Graph
• Dynamic Programming(Dijkstra Algorithm)