문제 39
벨만-포드
$1$번부터 $N$번까지 번호가 붙은 정점과 $M$개의 가중치 방향 간선으로 이루어진 그래프가 있다.
시작 정점 $S$로부터 각 정점까지의 최단 거리를 구하라.
시작 정점 $S$에서 도달할 수 있는 음수 사이클이 있다면 NEGATIVE CYCLE을 출력한다.
입력
첫 번째 줄에 세 정수 $N$, $M$, $S$가 공백으로 구분되어 주어진다. $(1 \le N \le 1\,000; 0 \le M \le 5\,000; 1 \le S \le N)$
두 번째 줄부터 $M$개의 줄에 걸쳐 각 방향 간선의 시작 정점의 번호, 도착 정점의 번호, 가중치를 의미하는 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \neq v; -10^9 \le w \le 10^9)$
같은 방향 간선은 두 번 이상 주어지지 않는다.
출력
시작 정점 $S$에서 도달할 수 있는 음수 사이클이 있다면 NEGATIVE CYCLE을 출력한다.
그렇지 않다면 $1$번 정점부터 $N$번 정점까지 시작 정점 $S$로부터의 최단 거리를 한 줄에 하나씩 출력한다.
시작 정점에서 도달할 수 없는 정점이라면 INF를 출력한다.
예제 입력 1
5 7 1 1 2 4 1 3 2 3 2 -1 2 4 2 3 4 5 4 5 -3 2 5 6
예제 출력 1
0 1 2 3 0
예제 입력 2
4 4 1 1 2 1 2 3 -2 3 2 -2 3 4 1
예제 출력 2
NEGATIVE CYCLE
예제 입력 3
4 2 1 1 2 -1 3 4 -5
예제 출력 3
0 -1 INF INF
공식 해설
정점이 최대 $1\,000$개, 간선이 최대 $5\,000$개이므로 간선 전체를 정점 수만큼 확인하는 $O(NM)$ 방법을 사용할 수 있다.
음수 간선이 있으므로 거리가 작은 정점부터 확정할 수 없다. 대신 모든 간선을 반복해서 완화하는 벨만–포드 알고리즘을 사용한다.
간선을 $(u,v,w)$의 목록으로 저장하고, 시작점의 거리만 $0$, 나머지는 무한대로 둔다. 목록 전체를 순회하며 $u$에 도달할 수 있고 $d_u+w<d_v$이면 $d_v$를 갱신한다.
도달 가능한 음수 사이클이 없다면 최단 경로에서 정점을 반복할 필요가 없으므로 간선 수는 최대 $N-1$이다. 전체 간선을 한 번 순회할 때마다 적어도 한 간선만큼 더 긴 경로까지 반영되므로 $N-1$번이면 최단 거리가 구해진다.
이후 한 번 더 순회했는데 거리가 줄어들면 도달 가능한 음수 사이클이 있다. NEGATIVE CYCLE을 출력한다. 갱신이 없다면 최단 거리들을 출력하고 무한대인 정점에는 INF를 출력한다. 중간 반복에서 갱신이 전혀 없으면 바로 종료해도 된다.
무한대인 정점에서 완화하면 시작점과 무관한 음수 사이클을 잘못 검출할 수 있으므로 반드시 건너뛴다. 음수 사이클을 검사하는 동안에도 거리가 계속 줄어들 수 있으므로, 최종 거리뿐 아니라 완화 과정의 합도 정확히 계산해야 한다.
간선 목록을 직접 순회하면 시간복잡도는 $O(N+NM)$, 공간복잡도는 $O(N+M)$이다.
구현 · 언어별 풀이
C++ 구현
간선을 시작점·도착점·가중치를 가진 구조체의 vector에 저장한다. 거리는 long long, 무한대는 1LL << 60처럼 충분히 큰 값으로 둔다. 무한대인 출발점의 간선은 덧셈 전에 제외하고, 한 순회에서 갱신이 있었는지 따로 기록한다.
C 구현
간선의 u,v와 long long 가중치를 배열에 저장한다. 시작점에서 도달한 u만 완화한다. N-1회 뒤 추가 완화 여부로 음수 사이클을 검사하며, INF에 음수 가중치를 더하지 않는다.
Python 구현
(u,v,w) 간선 리스트와 거리 배열을 사용한다. 도달 가능한 출발점만 완화하고 한 번도 바뀌지 않으면 반복을 끝낼 수 있다. 추가 완화 검사는 여전히 시작점에서 도달 가능한 간선에 한정한다.
Java 구현
long[] dist와 간선 배열을 사용한다. 음수 사이클을 검사할 때도 INF인 출발점을 제외한다. 가중치와 거리의 합은 int에 넣지 않는다.
Rust 구현
간선을 (usize,usize,i64) 튜플로 저장한다. dist[u]가 도달 불가능 표시가 아닐 때만 덧셈한다. N번째 완화가 가능한지 확인하여 다른 연결 요소의 음수 사이클을 잘못 보고하지 않는다.
JavaScript 구현
거리에는 Number와 도달 불가능 표식 Infinity를 사용한다. 최대 $N$회의 각 간선 순회에서 한 번씩 완화하므로 음수 사이클이 있어도 유한하게 수행하는 중간 덧셈은 절댓값 $NM\cdot10^9\le5\cdot10^{15}$ 범위이다. 따라서 이 문제에서는 안전 정수 범위 안이고 BigInt는 필요 없다.
dist[u] !== Infinity인 간선만 완화한다. $N-1$회 뒤 추가 순회에서 갱신 가능 여부를 확인하고 NEGATIVE CYCLE을 출력한다. 그 외에는 Infinity를 INF로 바꿔 출력한다. 도달 불가능한 음수 사이클을 시작점의 사이클로 오인하지 않는다.