벨만포드 예제 - 타임머신

 

 

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

예제 입력 1 복사

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

예제 출력 1 복사

4
3

예제 입력 2 복사

3 4
1 2 4
1 3 3
2 3 -4
3 1 -2

예제 출력 2 복사

-1

예제 입력 3 복사

3 2
1 2 4
1 2 3

예제 출력 3 복사

3
-1

 

 

이 문제는 벨만포드 알고리즘을 쓰는 예시 문제이다.

 

음의 간선이 있기 때문에 다익스트라를 쓰지 못한다. 

 

다익스트라는 기본적으로 지금까지 찾은 경로가 최적의 경로다 라는 가정을 가지고 작동을 한다. 

 

하지만 음수의 간선 사이클을 가진다면 가정이 깨지게 되기 때문에 최적의 경로를 찾지 못하게 된다. 

 

따라서 벨만포드를 사용해야 한다. 

 

벨만포드는 모든 간선을 방문하며 현재까지의 측정된 경로가 최적의 경로인지 매번 검사를 한다. 

 

노드의 개수 +1 만큼 간선의 거리를 업데이트하여 최적의 경로를 구하는데 

 

i번반복 횟수에서도 간선이 업데이트 된다면 음의 사이클이 있는 것이다. 

 

좀 더 쉽게 말하자면 다익스트라는 음의 간선 사이클이 있는 부분에서 양의 간선에 진입하면 최적값이 아니라고

판단하여 중간에 빠져버린다. -> 음의 간선에서는 사용 못하는 이유

 

벨만포드는 모든 간선을 사용하여 최적 거리를 업데이트하기 때문에 음의 간선에서도 사용할 수 있는 것임. 

 

N번째에서도 작동을 한다는 것은 N-1개의 간선을 거쳐 모든 경우의 수가 업데이트 되었는데도 최적의 간선이 아니라는

이야기이기 때문에 음의 사이클이 존재한다는 것이다!

 

구현은 생각보다 간단하다. 

 

-> N, M을 사용하여 이중 for문을 구현하고 dist를 계속해서 비교해주면 된다. 

 

dist[now] + cost < dist[next] 라면 dist[next] = dist[now] + cost

 

---

구현 코드

INF = 1e10
N, M = map(int, input().split())
graph = []
dist = [INF] * (N+1)


for _ in range(M):
    graph.append(tuple(map(int, input().split())))

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

    for i in range(N+1):
        for j in range(M):
            new, next, cost = graph[j][0], graph[j][1], graph[j][2]
            if dist[new] != INF and dist[new] + cost < dist[next]:
                dist[next] = dist[new] + cost
                if i == N:
                    return True

    return False

negative = bellman_ford(1)

if negative:
    print(-1)
else:
    for i in range(2, N+1):
        print(dist[i] if dist[i] != INF else -1)