MST 가 아닌 다익스트라로 정점번호 1을 제외한 각 정점들로부터 1까지 가는 최단거리 경로를 메모해서 중복 없이 출력하면 된다고 알고 있었는데,
그래프가
4 5
1 2 1
1 3 2
1 4 3
2 3 1
3 4 1
이렇게 되어있을때,
위 그래프에서 정점 번호 1에서 3까지 가는 최단거리 경로가 두개 존재하고(1-2-3, 1-3) 복구할 최단거리 경로를 (1-3)이 아닌 2를 거쳐 가는 경로(1-2, 2-3)를 선택해 추가했을 때, 1에서 4로 가는 남은 최단거리 경로를 (1-4)가 아닌 (1-3-4)로 선택하는 가정을 해 봤습니다. 이렇게 하면 1이 아닌 모든 정점에서 다익스트라 경로를 거꾸로 출력할 때 나올수 있는 상황이면서, (1-2, 1-3, 1-4) 3개면 충분할 간선의 개수가 4개로 나올 수 있을 것 같아서요. 제가 혹시 문제나 알고리즘을 잘못 이해했다면 지적 부탁드리겠습니다.
sang8481 6년 전
MST 가 아닌 다익스트라로 정점번호 1을 제외한 각 정점들로부터 1까지 가는 최단거리 경로를 메모해서 중복 없이 출력하면 된다고 알고 있었는데,
그래프가
4 5
1 2 1
1 3 2
1 4 3
2 3 1
3 4 1
이렇게 되어있을때,
위 그래프에서 정점 번호 1에서 3까지 가는 최단거리 경로가 두개 존재하고(1-2-3, 1-3) 복구할 최단거리 경로를 (1-3)이 아닌 2를 거쳐 가는 경로(1-2, 2-3)를 선택해 추가했을 때, 1에서 4로 가는 남은 최단거리 경로를 (1-4)가 아닌 (1-3-4)로 선택하는 가정을 해 봤습니다. 이렇게 하면 1이 아닌 모든 정점에서 다익스트라 경로를 거꾸로 출력할 때 나올수 있는 상황이면서, (1-2, 1-3, 1-4) 3개면 충분할 간선의 개수가 4개로 나올 수 있을 것 같아서요. 제가 혹시 문제나 알고리즘을 잘못 이해했다면 지적 부탁드리겠습니다.