글 읽기 - 벨만-포드 알고리즘 왜 틀렸는지 궁금합니다.

hhj732 3년 전 0

안녕하세요. 벨만-포드 알고리즘으로 풀었는데, 출력초과가 나옵니다. 음수 사이클이 있는 경우에 2부터 n-1까지 출력해서 그런 것일텐데요 ㅠ_ㅠ

예제에 나온 테스트 케이스는 모두 맞고 질문 게시판에서 여러 분들이 올려주신 반례도 모두 정답을 출력합니다. 어느 부분에서 논리적으로 잘못되었는지 알고싶습니다. ㅠㅠ 도와주세요

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_11657 {

	static class Edge {
		int to;
		int weight;
		
		Edge(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}
	}
	
	static int n, m;
	static ArrayList<Edge>[] adj;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(stk.nextToken());
		m = Integer.parseInt(stk.nextToken());
		
		// init
		adj = new ArrayList[n+1];
		for(int i=0; i<adj.length; i++) {
			adj[i] = new ArrayList<>();
		}
		
		for(int i=0; i<m; i++) {
			stk = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stk.nextToken());
			int b = Integer.parseInt(stk.nextToken());
			int c = Integer.parseInt(stk.nextToken());
			
			adj[a].add(new Edge(b, c));
		}
		
		int[] upper = bellmanFord(1);
		
		// 무한히 오래전으로 되돌릴 수 있다.
		if(upper[1] == Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		// 그렇지 않아.
		else {
			for(int i=2; i<=n; i++) {
				System.out.println(upper[i] == Integer.MAX_VALUE ? -1 : upper[i]);
			}
		}
	}
	
	public static int[] bellmanFord(int start) {
		int[] upper = new int[n+1];
		
		// 초기화
		Arrays.fill(upper, Integer.MAX_VALUE);
		upper[start] = 0;
		
		boolean updated = false;
		
		// v번 순회한다. -> v번째도 완화했다면 음수 사이클이 있는 것
		for(int i=0; i<n; i++) {
			updated = false;
			
			// 모든 정점에 대해서 검사
			for(int here=1; here<=n; here++) {
				for(int j=0; j<adj[here].size(); j++) {
					int there = adj[here].get(j).to;
					int weight = adj[here].get(j).weight;
					
					// 완화를 시도
					if(upper[here] != Integer.MAX_VALUE && upper[there] > upper[here] + weight) {
						upper[there] = upper[here] + weight;
						updated = true;
					}
				}
			}
			
			// 완화를 실패하면 나오면 됨
			if(!updated) {
				break;
			}
		}
		
		// 만약 v번쨰도 완화 했다면, 음수 사이클이 있는 것임.
		if(updated) {
			Arrays.fill(upper, Integer.MAX_VALUE);
		}
		
		return upper;
	}

}

sait2000 3년 전 1

https://www.acmicpc.net/board/...

반례 데이터를 생성하는 코드가 저 게시글에 있습니다.

그래프가 대략 아래처럼 생겼는데, 질문자님 코드는 아래 그래프에서 500바퀴를 돌기 전에 거리가 음의 방향으로 오버플로우가 납니다.

1 --(-10000)--> 2 --(-10000)--> ... --(-10000)--> 500
^                                                  |
 \-------------------(-10000)---------------------/

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

벨만-포드 알고리즘 왜 틀렸는지 궁금합니다.

hhj732 3년 전 0

sait2000 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말