js0304   1년 전

안녕하세요,

간선의 가중치가 1이어도 음의 사이클이 존재하지 않지만 v-1번째 탐색까지 업데이트가 이루어지는 경우가 아닌가요? 제가 놓치는 부분이 있는지 여쭤봅니다.

dolchaelatte   1년 전

정확히 무엇을 물어보시는지 모르겠지만 설명드리자면, 

밸만포드 알고리즘의 기본 아이디어는 

최단 거리 이동은 무조건 (정점 개수 - 1)번 만에 일어난 다는 것에서 시작합니다.

그래서 음의 사이클 판별은 v-1번 이후에서 값의 update가 있다 없다고 판별되는 것이죠.

말씀하신 것처럼 가중치가 1이라면

음의 사이클이 없는 그래프라면 v-1번의 update 안에 이미 그것을 포함시켰을 겁니다.

쉽게 생각하시면 v-1번의 update 이후에는 무조건 모든 점의 최단거리는 setting되어있고 (음의 사이클이 없다면 )

그래서 한 번 더 update를 시도해보고 update가 이루어진다면 음의 사이클이 존재한다고 판단하는 거죠.


제가 댓글 의미를 정확히 파악하지 못하겠어서  이 글을 읽어보시고 다시 질문해주신다면 답변드리겠습니다.

dolchaelatte   1년 전

아 제가 문제를 완벽히 이해하지 못하고 답변드렸네요. 그래도 제가 말씀드린 부분은 다 맞는 말이니 참고하세용.

추가해서 답변드리면, 

이 문제는

(기본 Bellman-Ford )

( v-1 번의 탐색 ) + ( 사이클 확인용 1번 ) -> 총 v번 탐색

( 지구이 ver. Bellman-Ford )

( v-2 번의 탐색 ) + (사이클 확인용 1번 ) -> 총 v-1 번 탐색

이로 인한 오류를 지구이에게 일깨워 줄 수 있는 반례를 만들으라는 문제인데요

문제 설명에 있는 것처럼 음수 사이클이 있다면 

지구이 버전의 밸만 포드도 같은 결과를 내기 때문에 

논리로 혼내줄 수 없습니다.

따라서, 지구이를 혼내주려면 음수 사이클이 없으면서

최단거리가 v-1번째 탐색에서 update가 되는 경우를 찾아야 됩니다.

아마 이 부분을 댓글에 물어보신 것 같은데, 네 그런 경우의 수를 찾는 문제가 맞습니다.

dolchaelatte   1년 전

문제 풀이에 대해 글 하나 남겼으니 참고하세요

js0304   1년 전

친절한 설명 감사합니다.

다만 제가 의문을 가졌던 점은, 예시 들어주신 정답은 모든 간선의 가중치가 -1인 경우입니다. 그런데 그 가중치가 1인 경우에도 순차적으로 업데이트 되어 v-1번째 탐색에서 업데이트가 발생하지 않나 하는 의문이 듭니다.

제 오답 코드입니다.

dolchaelatte   1년 전

아 이해했어요

바로 말씀드리자면 지구이의 코드 때문입니다.

지구이 코드를 보면 

fill(dis + 1, dis + N + 1, 0);

이렇게 거리를 0으로 같은 값으로 초기화하고,

if (dis[e] > dis[s] + cost) {
      dis[e] = dis[s] + cost;
}

이런 식으로  update를 시도합니다.

같은 값으로 초기화한 뒤, cost를 1로 해주면  어디에서도 update가 되지 않아요

그래서 이 문제에서 틀린 겁니다.


( 왜 이 문제만 그런지 부가 설명 해드릴게요. ㅎㅎ )

원래의 밸만 포드면

한 정점에서 모든 정점으로 가는 최단거리를 구하는 거기 때문에

dis[시작점]=0;

dis[나머지]=1e9; 로 setting 해놓고서

모든 간선을 v번 돌리는 식으로 구현을 합니다.

그래서 이때는 양수 가중치여도 아직 도달하지 못했으면 1e9가 저장되어있어 update가 될 수 있어요.


하지만 이 문제는 지구이가 틀린 거만 집어내는 과정이므로

음수 사이클이 있는지 없는 지 여부만 묻고 시작점을 따로 setting하지 않으니 그래프 전체를 다 탐색해줘야 해요.

그래서  모든 dis 값이 같은 값으로 초기화 되어있기 때문에 음수 가중치만이 update를 시킬 수 있습니다.

js0304   1년 전

아하 제시된 코드에 대한 이해가 부족해서 발생한 오답이었네요.

감사합니다 덕분에 이해에 많은 도움이 되었습니다!

dolchaelatte   1년 전

덕분에 저도 매우 깊이 생각해보게 되었네요 :)

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