kyy627   2달 전

visited를 체크해주면 오히려 틀렸습니다가 나옵니다.

아래 소스에서 왜 visited를 체크하지 않아도 정답이 나오는 건지, 

visited를 추가하면 왜 오답이 나오는 건지 궁금합니다.

sksdong1   2달 전

visit 체크를 하면 나중에 발견된 경로가 더 짧더라도 무시되겠죠

gallopsys   2달 전

간단하게 예를 들어드리는 게 빠르겠네요. 일단 해당 문제의 예제 테스트 케이스를 약간만 변형해봅시다.

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 1

이라는 그래프가 있다고 가정해봅시다. 일단 정점 1부터 시작한 그래프는 visited로 체크해가며 최단경로를 계산한다고 해봅시다.


정점 1에서 출발하면 다익스트라 알고리즘에 의해 정점 2, 3을 방문하여 최단거리를 갱신하게 되고 이는 각각 2, 3인 비용을 갖습니다. 그리고 우선순위 큐의 동작에 따라 방문 거리가 최소점인 정점을 방문하게 됩니다. 다음 방문 정점은 2가 되겠죠.

정점 2로 갔는데, 방문할 수 있는 노드가 3과 4지만, 3은 이미 visited처리 되었기 때문에 방문할 필요가 없습니다. (이는 어디까지나 visited를 넣어 처리한 결과임을 알려드립니다.) 4는 한번도 방문한 적이 없기 때문에 정점 2의 최소비용인 2와 정점 2에서 정점 4로 가기 위한 비용인 5를 더해 7로 갱신했습니다.

정점 5는 방문할 수 없기 때문에 무한대의 값을 가지게 되지만, visited로 체크한 결과, 더 이상 방문할 정점이 없기 때문에 탐색할 필요가 없습니다. 하지만 항상 옳은 결과를 내놓을까요?


아닙니다. 위에서 변형된 테스트 케이스로 보면 정점 1에서 출발하여 정점 3, 정점 4를 거치게 되면 3 + 1로 비용 4를 갖게 되므로 정점 1에서 출발하여 정점 2, 4를 거친 비용인 7보다 더 최단거리를 가짐을 알 수 있습니다.

그러므로 다익스트라 알고리즘에서 visited를 두면 이러한 경우를 체크하지 못하게 되고 논리적 오류가 발생할 수도 있는 것이지요.

댓글을 작성하려면 로그인해야 합니다.