BaekJoon 11657번 : 타임머신 (python)

BaekJoon 11657번 : 타임머신 (G4 25.010%)

기본 다익스트라 알고리즘 문제에서 가중치가 -가 있을 경우 음수 간선의 순환이 발생할 수 있다.
음수 간선의 순환이란 가중치에 음수가 섞여있을 때 최단 거리가 음의 무한인 노드가 발생하는 상황을 의미한다.
이렇게 될 경우 최소 비용이 어디든지 -무한대가 될 수 있는 상황이 발생하게 된다.

그래서 최단 경로, 최소 비용을 구하는 문제에 음수가 섞여 있고 음수 간선의 순환이 발생할 수 있을 경우 우리는 벨만 포드 알고리즘을 사용해야 한다.

• 벨만 포드 최단 경로 알고리즘
  - 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 순환을 감지할 수 있다.

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 다음의 과정을 N-1번 반복한다.

   1. 전체 간선 E개를 하나씩 환인한다.
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

   - 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다.
   - 이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

• 다익스트라 알고리즘
  - 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  • 음수 간선이 없다면 최적의 해를 찾을 수 있다.
• 벨만 포드 알고리즘
  - 매번 모든 간선을 전부 확인한다.
  - 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.
  • 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 간선 순환을 탐지할 수 있다.

벨만 포드 알고리즘은 노드를 탐색하는 것이 아닌 주어진 전체 간선 E개를 하나씩 확인 한다는 점이 다익스트라 알고리즘과 다른 점이고 음수 간선 순환이 발생하는지에 대한 체크 과정이 N-1번 반복 한 이후에도 간선에 대한 최단 경로가 업데이트 되는지 안되는지에 대한 여부 확인이라는 점이 중요한 부분이다.

import sys
input = sys.stdin.readline
INF = int(1e10)
def bfs(start) :
    distance[start] = 0
    for i in range(N) :
        for j in range(M) :
            now = edges[j][0]
            next = edges[j][1]
            dist = edges[j][2] + distance[now]
            if distance[now] != INF and distance[next] > dist :
                distance[next] = dist
                if i == N-1 :
                    return True
    return False

N, M = map(int,input().split())
edges = list()
distance = [INF]*(N+1)

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

check = bfs(1)
if check :
    print(-1)
else :
    for i in range(2, N+1) :
        if distance[i] == INF :
            print(-1)
        else :
            print(distance[i])