벨만 포드에서 음수 사이클을 체크할 때
마지막에 반복문을 한번 더 돌려서 dist값이 갱신되면 싸이클이 있다고 판단하잖아요
그래프가 음수 싸이클을 가진다고 가정할 때
마지막에 반복문을 한 번 더 돌려서 갱신되지 않은 정점은 음수 싸이클을 지나지 않는다고 판단할 수 있나요?
글을 ㅈㄴ 못쓴거 같긴한데 최대한 정리해봄..
1. 그래프는 음수 싸이클을 가지고 있음
2. 이 그래프에 대해서 벨만 포드 알고리즘을 사용
3. 벨만 포드 알고리즘(V-1번 반복)을 쓰고 나니까 dist[2] ~ dist[5] 값이 순서대로 1,2,3,4 가 나왔음
4. 음수 싸이클을 판별하기 위해 모든 정점에 대해 간선을 방문
5. 4번을 하고 나니까 dist[2] ~ dist[5] 값이 -1,-2-3,4 가 나왔음
6. 이 때 dist값이 변하지 않은 5번 정점에 대해, 1번 정점은 5번 정점으로 가는 최단거리 경로에서 음수 싸이클을 거치지 않는다고 볼 수 있는가?
ㄴㄴ
이해한 사람 있음?
벨만 포드에서 음수 싸이클이 판단 할 때 반복문을 한 번 더 돌려서 dist 배열이 갱신되면 싸이클이 있다고 판단하잖아요. 최단 거리가 음수 싸이클에 의해 새로 바뀌어서.. 그렇다면 반대로 dist 배열에서 갱신 안된 점은 음수 싸이클을 지나지 않는다고 볼 수 있냐는 건데 말로 쓴다는게 너무 어렵네
연결요소 이야기 하는건가
안거치는게 맞을껄
정점 2 3 4 가 연결요소고 정점 5가 다른 연결요소인데, 정점 1에서 { 2 3 4 }, { 5 } 둘다 갈 수 있다는 소리 말하는거지?
네. 1. 2-3-4는 음수 싸이클을 생성 중이다. 2. 정점 1에서는 2,3,4,5를 모두 방문할 수 있다. 3. 정점 1에서 음수 싸이클을 거치지 않고 5까지 가는 최단 경로가 존재한다면, 벨만 포드의 반복문을 한 번 더 돌려도 dist[5]는 갱신되지 않는가? 4. 반대로 벨만 포드의 반복문을 한 번 더 돌려서 dist[5]가 갱신되지 않았다면, 정점 1에서 정점 5로 가는 최단 경로에는 음수 싸이클이 없는가? 여기서 3,4가 둘 다 성립하는지 궁금한거..
3번 정의를 음수 싸이클을 거칠 수 없는 경로만 존재 한다면으로 하면 3, 4 맞는듯?
물어보는게 뭔지 잘 모르겠음. 5로 가는 길에 음수 사이클을 거치는 방법이 없다라는걸 확인하고 싶은건가?
ㅇㅇ 1에서 5로 가는 최단거리 경로에 음수 싸이클이 없는지를 확인하고 싶은듯
ㄴㄴ 음수 사이클과의 거리가 멀어서 갱신 안된 정점이 있을 수도 있어서 벨만포드 자체를 한 번 더 돌려서 확인해야함
ㄴㄴ 사이클 길이가 1보다 긴 부분은 알 수 없지, 존재하는지만 알 수 있음. 최대로 가질 수 있는 사이클 길이만큼 4번을 반복했을 때 갱신된다면 명제가 참이라고 볼 수 있다
아 잠깐 이것도 알 수 없네 사이클 미포함 간선도 갱신되긴하니까.. 어쨌든 요점은 한 번으로는 절대 알 수 없고 갱신이 전파될 때까지는 반복해줘야 알 수 있것지 뭐