1번 점에서 N번 점까지 가는 최단 경로에 속하는 점 i가 있습니다.
그러면 i번 점을 지나는 최단 경로는 i번 점을 기준으로 최단 경로를 두 구간 1~i, i~N으로 나눌 수 있을텐데 여기서
어떤 점 j가 i~N 구간에 속하면, j가 1~i 구간에 속할 가능성은 없는지요? 제 생각에는 가능성이 없을 것 같은데 증명을 못하겠습니다.
혹시 가능하다면 가능한 경우를 알려주시면 감사하겠습니다.
모든 간선가중치가 양수이며 양방향그래프라면 없습니다.
D라는 배열이 있어서 D[i] = 1번점에서 i번까지 가는 최단거리를 저장하고 있다고 생각해보죠.
이 때 D[j] > D[i]임이 자명합니다. 이유는, D[j] <= D[i]라면 i를 거쳐서 j를 찍고 N번 점으로 가는 경로가 최단이 될 수 없기 떄문입니다. i를 가지 않고 바로 j를 찍고 N으로 가면 되겠죠.
고로 D[j] > D[i]인데, 이 경우 j란 점이 1 ~ i사이의 경로에 있으면 모순입니다.
i와 j를 생각하기 전에 일반적으로 양의 가중치를 가진 그래프에 대해 같은 정점을 두 번 방문하는 최단 경로가 존재할 수 없습니다. 같은 정점으로 되돌아오는 부분경로를 제거해도 올바른 경로인데 더 짧으니 모순입니다. 조금 더 확장하면 음이 아닌 가중치에 대해서도 성립합니다.
sonnet
1번 점에서 N번 점까지 가는 최단 경로에 속하는 점 i가 있습니다.
그러면 i번 점을 지나는 최단 경로는 i번 점을 기준으로 최단 경로를 두 구간 1~i, i~N으로 나눌 수 있을텐데 여기서
어떤 점 j가 i~N 구간에 속하면, j가 1~i 구간에 속할 가능성은 없는지요? 제 생각에는 가능성이 없을 것 같은데 증명을 못하겠습니다.
혹시 가능하다면 가능한 경우를 알려주시면 감사하겠습니다.
9년 전