cdnljw   5달 전

우선순위를 이용하여 다익스트라를 구현할 때 우선순위에 담는 값이 왜 현재 가중치와 이전노드까지의 가중치의 합을 담는지 모르겠습니다.

제가 공부한 다익스트라 개념은 입력된 값을 큐에 넣어야 될듯 싶은데 이러면 시간초과가 나더라구요.. ㅠㅠㅠ

djm03178   5달 전

다익스트라는 매번 아직 방문하지 않은 정점들 중 시작점으로부터의 거리가 가장 가까운 정점을 방문하는 알고리즘입니다. 그러므로 간선의 가중치가 아닌 현재까지 찾은 해당 정점의 최단 거리를 큐에 넣는 것이 맞습니다.

cdnljw   5달 전

@djm03178 님 감사합니다.

이글 올리고 바로 제가 알고 있는 개념이 잘 못 됐다는 것을 알게되었네요. prim 알고리즘이랑 비슷하다고 생각해서 제가 착각하고 있었습니다.

답변해주셔서 감사합니다.

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