[11657] 타임머신 in python

> 벨만포드 알고리즘

 

 

다익 스트라 

: 모든 간선의 비용이 양수일 때 최단 경로를 구할 수 있다.

심지어 음수간선이 포함되어 있더라도 해당 간선이 순환되는 구간이 없으면 된다.

 

https://youtu.be/Ppimbaxm8d8

 

 

그러나 음수 간선이 순환되는 경우에는

다익스트라는 사용할 수 없고,

벨만 포드 알고리즘을 사용해야한다.

 

 

< 벨만 포드 알고리즘 > 

1. 출발 도시 설정

2. 최단 거리 테이블 무한으로 초기화

3. 벨만 포드 알고리즘 시행

     3.1. 다음 과정을 n-1번 반복한다.

     3.2. 만약 dist[a]의 값이 무한이 아니고, 

          dist[b]의 값이 dist[a]+c값보다 크면?

          dist[b]에 dist[a]+c, 최단경로를 넣어준다.

     3.3 만약 현재 i가 n인데도 갱신이 이뤄졌다면?

          -> 음수 간선 순환이 존재하는 것이므로 True를 반환함. 

 

 

import sys
input = sys.stdin.readline
INF = int(1e9)


def bellman_ford(start):
    dist[start] = 0

    # n번의 라운드를 반복
    for i in range(1, n + 1):
        # 매 라운드마다 모든 간선을 확인
        for j in range(m):
            now, next, cost = edges[j][0], edges[j][1], edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if dist[now] != INF and dist[next] > dist[now] + cost:
                dist[next] = dist[now] + cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환 존재
                if i == n:
                    return True

    return False


n, m = map(int, input().split())
edges = []
dist = [INF] * (n + 1)

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))

negative_cycle = bellman_ford(1)

if negative_cycle:
    print(-1)
else:
    for i in range(2, n + 1):
        # 도달할 수 없는 경우
        if dist[i] == INF:
            print(-1)
        # 도달 가능한 경우
        else:
            print(dist[i])