1753번 - 최단경로
우선순위를 이용하여 다익스트라를 구현할 때 우선순위에 담는 값이 왜 현재 가중치와 이전노드까지의 가중치의 합을 담는지 모르겠습니다.
제가 공부한 다익스트라 개념은 입력된 값을 큐에 넣어야 될듯 싶은데 이러면 시간초과가 나더라구요.. ㅠㅠㅠ
다익스트라는 매번 아직 방문하지 않은 정점들 중 시작점으로부터의 거리가 가장 가까운 정점을 방문하는 알고리즘입니다. 그러므로 간선의 가중치가 아닌 현재까지 찾은 해당 정점의 최단 거리를 큐에 넣는 것이 맞습니다.
@djm03178 님 감사합니다.
이글 올리고 바로 제가 알고 있는 개념이 잘 못 됐다는 것을 알게되었네요. prim 알고리즘이랑 비슷하다고 생각해서 제가 착각하고 있었습니다.
답변해주셔서 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
cdnljw 2년 전
우선순위를 이용하여 다익스트라를 구현할 때 우선순위에 담는 값이 왜 현재 가중치와 이전노드까지의 가중치의 합을 담는지 모르겠습니다.
제가 공부한 다익스트라 개념은 입력된 값을 큐에 넣어야 될듯 싶은데 이러면 시간초과가 나더라구요.. ㅠㅠㅠ