[질문] 벨만 포드 질문

[익명(221.163)]

왜 N - 1번까지 돌려봐야, 그 이후로 한 번 더 돌려봤을 때 정상적인 그래프(음의 싸이클이 없는)라면 값 갱신이 없다라는 걸 어떻게 앎?

[익명(121.162)]

최단경로의 길이가 N 이상이다 -> 최단경로가 두 번 이상 방문한 정점이 있다 -> 그 정점을 여러번 방문할 때마다 총 길이는 감소한다 -> 음수 사이클이 있다!

[익명(221.163)]

밑에 껄로 이해했음 ㄱㅅ

[캐티(tae826)]

벨만포드는 한 사이클에 최단거리의 경로 중 한 개를 확정하는 느낌이라고 보면 됨. 최단거리의 경로가 N이 넘으면 음수 사이클이 있다는거니까 멈출 수 있는거

[익명(221.163)]

아아 이거구나 ㄱㅅㄱㅅ 사랑해~