백준 1753 - 최단경로 파이썬

문제

1753번: 최단경로

 

다익스트라 개념(동빈나 강의 참고)

다익스트라 알고리즘은 한 지점에서 다른 모든 지점까지의 최단 경로를 계산하는 알고리즘이다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3번과 4번을 반복한다. 

데이크스트라 이론을 만든 데이크스트라님......

코드 

import sys
import heapq

input = sys.stdin.readline
INF = sys.maxsize
num_of_vertices, num_of_edges = map(int, input().split())
start_vertex = int(input())
distance = [INF] * (num_of_vertices + 1)  # 가중치 테이블 dp
heap = []  # 최소 힙
graph = [[] for _ in range(num_of_vertices + 1)]  # 그래프 정보를 담는 리스트

def dijkstra(start):
    distance[start] = 0
    heapq.heappush(heap, (0, start))

    while heap:
        weight, current_vertex = heapq.heappop(heap)

        if distance[current_vertex] < weight:
            continue

        for w, next_vertex in graph[current_vertex]:
            next_weight = w + weight
            if next_weight < distance[next_vertex]:
                distance[next_vertex] = next_weight
                heapq.heappush(heap, (next_weight, next_vertex))

for _ in range(num_of_edges):
    u, v, w = map(int, input().split())
    graph[u].append((w, v))  # (가중치, 목적지 노드) 형태로 그래프 정보 저장

dijkstra(start_vertex)  # 다익스트라 알고리즘 실행

for i in range(1, num_of_vertices + 1):
    print("INF" if distance[i] == INF else distance[i])  # 최단거리 출력