언제 쓰지?

• 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘
• 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있음

소스 코드

from sys import stdin, maxsize

input = stdin.readline

N = int(input())
M = int(input())
edge_list = [list(map(int, input().split())) for _ in range(M)]
start, end = map(int, input().split())
cost_list = [maxsize for _ in range(N + 1)]
cost_list[start] = 0

for _ in range(N - 1):
    for edge in edge_list:
        edge_start, edge_end, edge_cost = edge

        if cost_list[edge_start] == maxsize:
            continue

        cost_list[edge_end] = min(
            cost_list[edge_end], cost_list[edge_start] + edge_cost
        )

print(cost_list[end])

Reference

[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘