알고리즘 스터디 - 백준 1753번 : 최단 경로

문제 해석

• 방향 그래프 내 시작점과 다른 모든 정점 사이의 최단 경로 구하기
• 간선의 가중치는 10 이하의 자연수

어떤 알고리즘을 써야할까?

1. 정점의 개수 v, 간선의 개수 e
2. 시작 정점의 번호 k
3. (u, v, w) : (u에서 v로 가는 가중치 w)가 총 간선의 개수만큼 입력

다익스트라 알고리즘을 사용하여 최단 경로를 구할 수 있다.

주의할 점

1. 그래프의 간선이 양방향이 아닌 일방향임을 명심하기
2. 무한대를 생성할 때 임의의 숫자가 아닌 진짜 무한대를 사용하기

알고리즘 코드

import heapq
import math

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

k = int(input())

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

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start, distance):
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (distance[start], start))
    
    while queue:
        dist, node = heapq.heappop(queue)

        if distance[node] < dist:
            continue

        for next in graph[node]:
            weighted_distance = dist + next[1]
            if weighted_distance < distance[next[0]]:
                distance[next[0]] = weighted_distance
                heapq.heappush(queue, (weighted_distance, next[0]))

INF = float('inf')

distances = [INF] * (v+1)

dijkstra(start=k, distance=distances)

for i in range(1, v+1):
    if math.isinf(distances[i]):
        print("INF")
    else:
        print(distances[i])