목적지로 가는 최단경로가 특정 경로를 포함하는 경로와 포함하지 않는 경로 모두가 있을 수 있습니다. 간단한 예시를 들자면 a에서 d로 가는 최단경로를 알고 싶은데, <a, b>, <b, d>, <a, c>, <c, d> 이렇게 4개의 edge가 모두 가중치 1로 존재한다고 해봅시다. 이때 특정 경로 <a, c>를 지나는지를 알고 싶은데, 다익스트라 알고리즘에 의해 선택된 경로가 a -> b -> d라면, 경로의 길이가 같은 a -> c -> d가 있음에도 불구하고 최단경로로 간다면 <a, c>를 지나갈 수 없다는 결과가 나오게 될 겁니다. 작성하신 알고리즘에선 특정 경로의 길이를 일반 경로보다 더 길다고 설정하셨기 때문에 최단경로가 여러개일 경우 항상 특정 경로를 포함하는 최단 경로는 존재하지 않는다는 결과를 낳게 될 것입니다.
lobwidu 2년 전 1
아래와 같이 풀이 접근 방법으로 했는데
33%에서 계속 틀린다고 뜨네요..
애드혹 스타일의 아이디어를 요구하는 간단한 다익스트라 문제라 생각했는데,,
변수 초기화 문제 인지..
혹시 어느 부분이 잘 못 되었는지 도움 주실 분 계실까요?