bonoxtwo   3년 전

여러 테스트 케이스를 사용해서 테스트 해봐도 뭐가 잘못된지 모르겠네요 ㅠㅠ

plzrun   3년 전

x->y로 갈때
x->a->y, x->b->y 두 경로가 있다고 해볼게요,
그런데 b로 가는 길이 더 짧은데 탐색순서상 a부터 보게된다면,
(즉, x->a가중치가 1이고, a->y가 100000인데,      x->b가 100이고 b->y는 1인 경우죠)

x->a->y하면서 x,a,y모두 visited에 체크가 될거에요. 하지만 그떄의 dist값은 최소가 아님에도 전부 체크가 되어있는 상태죠.
이 상태에서 b->y를 들어가려고 해봐야 visit이 체크되어있으니 들어갈 수가 없어요.. 그럼 갱신되지 않죠.
visited라는 배열이 반드시 최단거리를 업뎃해주고 난다음에 체크가 되어야 할거에요.
그러므로 그냥 반복문을 도는게 아니라 민힙을 써서 가장 작은거리부터 뱉어주게 해야 할것 같네요.
그게 다익스트라의 원리이기도 하구요.

plzrun   3년 전

그리고 이 코드는 x->a->y까지 들어가고 나면 x->b를 더 탐색해볼 수도 없는것 같군요.

bonoxtwo   3년 전

아 정말 그렇네요! 감사합니다!!

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