다익스트라

• 백준 1753 다익스트라 알고리즘

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

최단 경로를 찾아가는 다익스트라 알고리즘 문제. 확실히 책으로 다익스트라, heapq를 공부하던 것을 직접 구현하는 것은 조금의 차이가 있었다.

heapq(우선순위 q)를 통해 푸는 문제로 각 노드로 가는 최단 거리를 확인하는 문제

math.inf를 통해 없는 거리는 양의 무한대를 입력

아래는 다익스트라를 구현

import math
import heapq
import sys

input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())  # 시작점
dist = [math.inf] * (v + 1)  # 거리 테이블
heap = []
graph = [[] for _ in range(v + 1)]

for _ in range(e):  # 그래프 초기하
    start, end, w = map(int, input().split())
    graph[start].append((w, end))


def dijkstra(start):
    dist[start] = 0  # 시작 가중치 = 0
    heapq.heappush(heap, (dist[start], start))  # 시작점 우선순위 큐에 넣음 (가중치가 맨앞으로)

    while heap:  # 큐에 아무것도 없을때 까지
        current_weight, current = heapq.heappop(heap)  # 큐에서 가장 작은 거리 pop

        if dist[current] < current_weight:  # pop한 노드의 가중치가 이미 저장된 가중치보다 크면 패스
            continue

        for graph_next_weight, next in graph[current]:
            next_weight = current_weight + graph_next_weight  # 이전 노드에서 다음 노드로 가느 가중치

            if next_weight < dist[next]:  # 계산된 가중치 < 다음 노드의 가중치
                dist[next] = next_weight
                heapq.heappush(heap, (next_weight, next))  # 큐에 다음 노드랑 게산된 가중치 넣음


dijkstra(k)
for i in range(1, v + 1):
    if dist[i] == math.inf:
        print("INF")
    else:
        print(dist[i])