안녕하십니까. 써주신 글 잘 보았습니다.
써주신 글에 대해 의문점이 있어 답글 답니다.
벨만포드를 구현시
'dist[x] : 시작점에서 x지점까지 최단거리' 라고 설정 후,
시작점에서 시작점까지 거리 = 0 으로 놓고, 시작점에서 나머지 지점까지 거리 = Infinite 로 놓고 시작하는데요,
cycle이 생겼을 시 시작점에서 해당 cycle 까지 도달 가능한지 체크하라는 말씀이 이해가 되지 않아서요....
애초에 시작점을 제외한 나머지 지점까지 최단 거리를 infinite로 설정하고 밸만포드를 구현하므로,
밸만포드 구현 과정에서 cycle이 생겼다는 말은, 시작점에서 해당 지점 (혹은 cycle)로 도달 가능하다는 말과 같은거 아닌가요...?
실제로 제가 음의 cycle이 생기면 -1을 출력하는 밸만포드를 구현하였고, ac를 받아서 여쭤봅니다.
( 시작점에서 각 지점까지 도달 가능한지 BFS 로 확인하지 않았습니다. )
helios789789 3년 전
벨만포드 기반으로 최단경로를 구현할때, 싸이클 관련해서 유의해야 할 점이 있습니다.
그래프 내의 최단 경로 상에 싸이클이 생겼다고 해서, 무조건 적으로 시간이 과거로 계속 돌아가는 것이 아닙니다.
시작점에서 싸이클 까지 도달 경로가 존재해야만 시간이 과거로 계속 돌아가게 됩니다.
즉, 벨만포드 구현 상 에서 싸이클이 생겼더라도, 시작점에서 그 싸이클 까지 가는 경로가 존재하지 않는다면, -1 를 출력하고 종료하면 안됩니다.
밑의 구현을 참고하시면, BFS 로 시작점에서 도달 가능한 정점을 우선 탐색한 후,
벨만포드 구현 시 싸이클이 발생한 경우에 대해서, 시작점에서 그 싸이클 까지 도달 가능한 경우만 -1 를 출력하고 종료합니다.
그 외의 경우는, 싸이클이 존재하지만 어차피 시작점에서 그 싸이클 까지 못가는 경우 입니다.
따라서 시작점을 제외한 정점에 대해서, 도달 가능하다면 그 정점까지의 거리를, 도달 불가능 하다면 -1 를 출력하면 됩니다.
종만북 30장, 최단경로 알고리즘-벨만포드 부분을 보면 위의 케이스에 대해서 정확하게 설명이 적혀있으니 참고하시기 바랍니다.