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라는 배열이 반드시 최단거리를 업뎃해주고 난다음에 체크가 되어야 할거에요.
그러므로 그냥 반복문을 도는게 아니라 민힙을 써서 가장 작은거리부터 뱉어주게 해야 할것 같네요.
그게 다익스트라의 원리이기도 하구요.
bonoxtwo 7년 전
여러 테스트 케이스를 사용해서 테스트 해봐도 뭐가 잘못된지 모르겠네요 ㅠㅠ