bright2013   4달 전

위키 보고 작성한 다익스트라 알고리즘입니다.

STL 의 priority_queue 를 이용해 min_heap 만들었고,

다른 문제가 될만한 부분이 보이질 않네요. 예제 코드도 통과하는데

틀린 케이스를 못 찾겠습니다.

노드 수가 2만개에 에지 weight 도 10을 넘지를 않으니 인트 범위 넘어가서 그런 것도 아닌데..

도와주세요 ㅠㅠ

yukariko   4달 전

다익스트라 구현이 잘못되었습니다.

일단 prev_node는 필요없어 보입니다.

그리고 다익스트라는 dist값이 작은 순으로 추출되어야 하는데,

위 코드는 source를 제외한 나머지 모든 정점이 INF로 동일해서

dist의 변경이 반영되지 않습니다.

참고로 위키의 pseudo 코드는 pq를 사용하는 경우에는 적합하지 않습니다.


bright2013   4달 전

감사합니다~~^^

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