인프런 커뮤니티 질문&답변
작성한 질문수
다익스트라 final 노드 도착후에 바로 종료하지 않는 이유가 궁금합니다.
해결된 질문
작성
·
333
답변 2
1
안녕하세요 기석님
질문하신대로 이 문제에서는, 제가 제시해드린 코드로 봤을 떈 목적지 도달 후 바로 리턴하는게 '실행시간'상에서 이득이 있습니다. 따라서 실행시간 최적화를 위해 그렇게 코드를 작성하시는게 좋을 수 있습니다.
하지만 이 강의에서는 다익스트라 자체에 대한 코드 템플릿과 이를 이해시켜드리는게 가장 큰 목적이였기 떄문에 그렇게 하지 않았을 뿐입니다.
기석님이 생각하신대로 최적화를 해나가시면 더 좋은 코드들을 구현하실 수 있을 것 같아요!
더 궁금한점 있으시면 언제든 질문주세요~
0
안녕하세요, 인프런 AI 인턴이에요.
다익스트라 알고리즘은 목적지에 도착한 이후에도 우선순위 큐를 계속해서 탐색하는 이유가 있어요. 다익스트라 알고리즘은 최단 경로를 찾는 알고리즘이기 때문에, 목적지에 도착한 이후에도 아직 탐색되지 않은 노드들을 탐색해 나가야 합니다. 이렇게 함으로써 목적지에 도달하기 전까지의 모든 노드들에 대한 최단 경로를 구할 수 있게 됩니다.
그리고 다익스트라 알고리즘에서 우선순위 큐를 이용하는 이유는, 우선순위 큐를 통해 현재까지의 최단 경로 값을 갖는 노드들을 빠르게 추출하여 탐색하는 것이 시간 복잡도를 줄일 수 있기 때문입니다. 따라서, 목적지에 도달한 이후에도 우선순위 큐를 비우고 탐색을 계속하는 것은 최단 경로를 구하기 위한 필수적인 과정이 되는 것이죠.
결론적으로, 다익스트라 알고리즘에서는 목적지에 도착한 이후에도 우선순위 큐를 비우고 탐색하는 이유는 최단 경로를 구하기 위해서입니다. 이러한 동작을 통해 목적지에 도달하기 전까지의 모든 노드들에 대한 최단 경로를 구할 수 있습니다.