알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 56. 최단 경로 구하기

문제

에지의 가중치가 10이하의 자연수인 방향 그래프가 있다. 이 그래프의 시작점에서 다른 모든 노드로의 최단 경로를 구하시오.

 

시작점과 다른 노드와 관련된 최단 거리를 묻는 문제 풀이 방법

1. 다익스트라 (에지가 양수일때)

2. 벨만 포드

 

 

코드

import heapq
import sys 

input = sys.stdin.readline

n, e = map(int, input().split())
start = int(input())

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

# 인접리스트로 그래프 구현
for _ in range(e):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

# 거리 리스트 초기화
dist = [float('inf')] * (v + 1)
dist[start] = 0

# 자동으로 거리를 기준으로 정렬되도록 하기 위해 (dist, node)로
queue = [(0, start)]

while queue:
    current_dist, node = heapq.heappop(queue)
    
    if current_dist > dist[node]:
        continue
    
    if node in graph:
        for next_node, weight in graph[node]:
            distance = current_dist + weight
            if distance < dist[next_node]:
                dist[next_node] = distance
                heapq.heappush(queue, (distance, next_node))

# 결과 출력
for i in range(1, n + 1):
    if dist[i] == INF:
        print(dist[i])
    else:
        print('INF')