문제 링크: https://www.acmicpc.net/problem/11657

최단 경로를 찾는 문제입니다. 단, 간선의 가중치가 음수로도 주어집니다.

풀이

최단 경로?

1개의 정점에서 다른 모든 정점으로의 최단 거리를 계산해야 합니다. 다익스트라를 먼저 떠올렸지만, 다익스트라 알고리즘은 음의 간선을 포함하는 경우 최단 경로를 찾을 수 없습니다.

음의 간선을 포함하는 그래프에서 최단 경로를 구하기 위해서는 벨만-포드 알고리즘을 사용해야 합니다.

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

벨만-포드 알고리즘은 다익스트라처럼 한 정점에서 다른 모든 정점으로의 최단 경로를 구합니다. 다만, 다익스트라와 달리 음의 정점을 포함하는 그래프에서도 최단 경로를 보장합니다. 이를 위해, 벨만-포드 알고리즘은 $V-1$개의 정점에 대해 $E$개의 간선을 모두 확인합니다. 다익스트라는 방문하지 않은 정점에 대해서만 확인한 것에 비해 ($O(V \log E)$) 벨만 포드는 상대적으로 느립니다. ($O(VE)$)

다만, 음의 사이클이 있는 경우는 최단 경로를 구할 수 없습니다. 아래 예시와 같이, 음의 사이클을 무한히 반복해 거리를 줄일 수 있기 때문입니다.

따라서, 벨만-포드 알고리즘은 최단 경로를 구하기 위해 많아야 $V-1$개의 간선을 지난다고 가정합니다. $V$개 이상의 간선을 지나는 최단 경로의 경우, 음의 사이클을 포함한다고 간주합니다.

벨만-포드 알고리즘 구현하기

$N-1$개의 정점에 대해, $M$개의 모든 간선을 계속 순회해야 하므로 간선 정보는 1차원 배열의 형태로 입력받습니다. (문제와 같은 표현을 사용하기 위해, 정점의 개수는 $N$, 간선의 개수는 $M$으로 표현했습니다.)

INF = 100_000_001 # 도달할 수 없는 정점과의 거리를 나타내는 상수 값
N, M = map(int, input().split())

# 간선 입력 받기
edges = [None] * (M)
for e in range(M):
    edges[e] = tuple(map(int, input().split()))

이후, 벨만 포드 알고리즘을 작성합니다.

• start는 시작 정점으로, 벨만-포드 알고리즘을 통해 start에서 다른 모든 정점까지의 최단 거리를 계산합니다.
• distance는 시작 정점으로부터 다른 정점들로의 최단 거리를 기록할 1차원 배열입니다.

먼저, $N-1$개의 정점에 대해 $M$개의 모든 간선을 다 확인하며, 다른 정점으로의 거리를 갱신할 수 있는지 확인합니다.

• 이 때, 간선 정보는 다음과 같습니다.
  • s: 간선의 시작 정점
  • e: 간선의 도착 정점
  • c: 간선의 가중치 (경로의 거리), 음수일 수 있습니다.
• 만약 현재 간선의 시작점인 정점 $s$를 방문할 수 없다면 (distance[s] == INF), 이 간선을 통해 최단 거리를 갱신할 수 없습니다. 따라서, 방문 가능한 간선에 대해서만 거리 갱신을 진행해야 합니다.

마지막으로, 1번 더 $M$개의 간선을 확인하며 최단 경로가 갱신되는지 확인합니다. 만약 최단 거리가 갱신된다면, 앞선 전제에 따라 음의 사이클이 있다고 판단합니다.

• 저는 음의 사이클이 있다면 True, 없다면 False를 반환하도록 구현했는데 반대로 하셔도 상관 없습니다 😉

# 벨만 포드 알고리즘
distance = [INF] * (N + 1)
def bellman_ford(start):
    distance[start] = 0
    for v in range(N - 1):
        for e in range(M):
            s, e, c = edges[e]
            new_dist = distance[s] + c
            # s를 현재 방문 가능한 경우에만 이 간선을 통해 최단 거리를 갱신할 수 있다. 
            if distance[s] != INF and distance[e] > new_dist:
                distance[e] = new_dist
    
    # 음의 사이클이 있는지 검사
    for e in range(M):
        s, e, c = edges[e]
        new_dist = distance[s] + c
        if distance[s] != INF and distance[e] > new_dist:
            return True # 음의 사이클 존재
    return False        # 음의 사이클 없음

전체 코드

input = open(0).readline
INF = 100_000_001 # 도달할 수 없는 정점과의 거리를 나타내는 상수 값
N, M = map(int, input().split())

# 간선 입력 받기
edges = [None] * (M)
for e in range(M):
    edges[e] = tuple(map(int, input().split()))

# 벨만 포드 알고리즘
distance = [INF] * (N + 1)
def bellman_ford(start):
    distance[start] = 0
    for v in range(N - 1):
        for e in range(M):
            s, e, c = edges[e]
            new_dist = distance[s] + c
            if distance[s] != INF and distance[e] > new_dist:
                distance[e] = new_dist
    
    # 음의 사이클이 있는지 검사
    for e in range(M):
        s, e, c = edges[e]
        new_dist = distance[s] + c
        if distance[s] != INF and distance[e] > new_dist:
            return True # 음의 사이클 존재
    return False        # 음의 사이클 없음

has_negative_cycle = bellman_ford(1)
if has_negative_cycle:
    print("-1")
else:
    for v in range(2, N + 1):
        print("-1" if distance[v] == INF else distance[v])