helios789789   3년 전

벨만포드 기반으로 최단경로를 구현할때, 싸이클 관련해서 유의해야 할 점이 있습니다.

그래프 내의 최단 경로 상에 싸이클이 생겼다고 해서, 무조건 적으로 시간이 과거로 계속 돌아가는 것이 아닙니다.

시작점에서 싸이클 까지 도달 경로가 존재해야만 시간이 과거로 계속 돌아가게 됩니다.

즉, 벨만포드 구현 상 에서 싸이클이 생겼더라도, 시작점에서 그 싸이클 까지 가는 경로가 존재하지 않는다면, -1 를 출력하고 종료하면 안됩니다.

밑의 구현을 참고하시면, BFS 로 시작점에서 도달 가능한 정점을 우선 탐색한 후,

벨만포드 구현 시 싸이클이 발생한 경우에 대해서, 시작점에서 그 싸이클 까지 도달 가능한  경우만 -1 를 출력하고 종료합니다.

그 외의 경우는, 싸이클이 존재하지만 어차피 시작점에서 그 싸이클 까지 못가는 경우 입니다.

따라서 시작점을 제외한 정점에 대해서, 도달 가능하다면 그 정점까지의 거리를, 도달 불가능 하다면 -1 를 출력하면 됩니다.

종만북 30장, 최단경로 알고리즘-벨만포드 부분을 보면 위의 케이스에 대해서 정확하게 설명이 적혀있으니 참고하시기 바랍니다.

parkpkww   3년 전

안녕하십니까. 써주신 글 잘 보았습니다.

써주신 글에 대해 의문점이 있어 답글 답니다.

벨만포드를 구현시 

'dist[x] : 시작점에서 x지점까지 최단거리' 라고 설정 후,

시작점에서 시작점까지 거리 = 0 으로 놓고, 시작점에서 나머지 지점까지 거리 = Infinite 로 놓고 시작하는데요,

cycle이 생겼을 시 시작점에서 해당 cycle 까지 도달 가능한지 체크하라는 말씀이 이해가 되지 않아서요....

애초에 시작점을 제외한 나머지 지점까지 최단 거리를 infinite로 설정하고 밸만포드를 구현하므로,

밸만포드 구현 과정에서 cycle이 생겼다는 말은, 시작점에서 해당 지점 (혹은 cycle)로 도달 가능하다는 말과 같은거 아닌가요...?


실제로 제가 음의 cycle이 생기면 -1을 출력하는 밸만포드를 구현하였고, ac를 받아서 여쭤봅니다.

( 시작점에서 각 지점까지 도달 가능한지 BFS 로 확인하지 않았습니다. )

pjh6792   3년 전

@parkpkww

벨만 포드 알고리즘이 시작점에서 연결이 된 간선만 체크하는게 아니라, 모든 간선을 매번 확인하므로 

아래와 같은 Input처럼 시작점에서 음의 cycle이 연결되지 않아도 cycle이 존재한다고 판단이 되는 것 아닌가요?

시작점에서 도달할 수 없는 경우이므로 결과 또한 -1이 아니라, N-1개의 output을 출력해야 하는 것 같습니다. 

단순히 음의 cycle의 존재 확인만으로 어떻게 AC를 받으셨는지 궁금하네요...

(저도 아직 AC를 받지 못한 상황입니다 ㅠ)

pjh6792   3년 전

방금 막 AC를 받고 오는 길입니다...ㅎ

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

위 게시글을 참고했는데, 시작점과 음의 cycle이 연결되어 있는지를 판단하기 위해서는 굳이 BFS를 이용해서

도달 가능한 정점을 탐색할 필요 없이, 벨만 포드 알고리즘의 두번째 for문에서 현재의 upper가 INF에서 바뀌지 않았는지를 체크하면 되네요. 

어찌 됐든 반복문 구조가 시작점에 연결된 간선들부터 시작하기 때문에 두번째 정점부터 탐색하게 될 때, 

시작점과 연결되지 않은 정점들은 upper가 여전히 INF로 남아있게 됩니다. 

따라서 그런 정점들은 continue (무시) 하게 되면 됩니다. 

코드의 일부분만 첨부하도록 하겠습니다. 

*그리고 upper 배열의 범위를 꼭 long long으로 해주셔야 합니다! 

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

위 링크의 데이터를 통해서는 INT의 범위를 초과하게 됩니다. 

helios789789   3년 전

@pjh6792, @parkpkww

Upper[dst] == MAX 는 예외케이스가 있어서, 정점 도달 가능 여부를 따로 체크해줘야 합니다!

예를들어 A, B, C 정점으로 이루어진 유향 그래프 에서 A 가 시작지점이고,

A  B <-> C 와같이 A는 아무 정점과 연결되어 있지 않고, B 와 C 만 서로 -1 가중치로 연결되어 있을때,

벨만포드를 실행하면 B <-> C 에 음수 싸이클이 생겨 Upper[C] 가 MAX - 1 처럼 시작정점과 연결되어 있지 않은데도, 그 Upper 값이 줄어들 수 있습니다.

벨만포드에서 음수싸이클 과 정점도달여부 에 관해서는 종만북을 꼭 참조하길 바랍니다!!

pjh6792   3년 전

@helios789789

1이 시작지점이고, for(int j = 1; j<=N; j++) 구문을 반복하기 때문에 항상 시작지점 (j == 1)부터 체크를 하게 됩니다.

따라서 시작지점과 연결이 되어 있지 않은 지점이면 처음 j==1 인 경우에서 upper가 갱신이 되지 않으므로, 그냥 continue 됩니다. 

물론 이 문제와 같이 시작지점이 1이어서, 항상 시작지점부터 반복문을 돌면서 check가 가능한 경우에 대해서만 이와 같은 방법을 이용할 수 있는 것 같습니다.

정확한 풀이를 위해서는 종만북에 나와있는 방식대로 시작점으로 부터 해당 점까지 도달할 수 있는지를 구해주는 것이 맞습니다!

parkpkww   3년 전

helios789789, pjh6792

pjh6792 님이 말씀하신 것과 같이 출발점이 정해져 있기 때문에, for구문을 반복해 줄 때 upper가 갱신 되는지 여부로 check가 가능합니다.

하지만 벨만포드는 애초에 시작점이 정해져 있을 때 사용할 수 있는 알고리즘으로 알고 있습니다.

이에 따라 어떤 문제든 벨만포드를 통해 문제를 풀이한다면, for구문을 반복해주면서 check해줄 수 있다고 생각됩니다.

helios789789님이 말씀해주신 A B<->C 예제 역시 같은 방법으로 생각 가능할 것 같습니다.

A가 시작점이라고 생각한다면, B<->C 의 음의 cycle이 존재는 하지만,

for구문을 반복해 줄 때 시작점인 A에서 갱신되는 지점이 없으므로 upper가 갱신되지 않습니다.

즉 upper가 줄어들 수 없습니다. 따라서 음의 cycle이 존재 하지 않는다고 판단하게 됩니다.

따라서 upper[dst] = MAX 의 풀이는 예외가 없다고 생각됩니다.

parkpkww   3년 전

@pjh6792, @helios789789

따라서 정점 도달 가능 여부를 따로 체크해주지 않아도 풀이가능합니다.

ilbul2   3년 전

출력초과 뜨는건 long long 때문인것 같네요 어차피 INF상태에서 갈 수 있는 거리라면 갱신되고 못가면 INF 상태를 유지할텐데 굳이 체크할 필요는 없다고보네용.

int-> long long 변환하면 출력초과 사라지네용

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