다익스트라 알고리즘

Question

제가 이해한 것이 맞는지 궁금해서 질문드립니다. pq에서 poll이 됐다는 것은 poll이 된 해당 정점은 dis 배열에서 최소 비용이 확정됐다는 것이죠? 만약 3번 정점의 비용이 4로 최소비용 확정이 되었는데 이것은 1 -> 3으로 갔을 때인 거잖아요. 그럼 1이 아닌 다른 정점에서 3번으로 가는 경우도 pq에서 poll이 될텐데 이미 확정이 났기 때문에 수행속도를 줄이기 위해 if continue 문을 쓰신건가요?

김태원 · Answer

안녕하세요^^ 잘 이해하고 계십니다. 그래도 안전을 위해서 if 조건을 만족할 때 continue 하도록 코드를 짜시기 바랍니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. rlgus4531님! 다익스트라 알고리즘에 대한 질문을 해주셨군요. 다익스트라 알고리즘은 모든 정점의 최단 거리를 계산하는 데 아주 유용한데요, 이해하시기 쉽게 설명드리겠습니다. pq에서 poll이 됐다는 의미 : pq 는 우선순위 큐(Priority Queue)를 의미하며, 이는 가장 작은 값(최소 비용)을 가진 정점을 먼저 처리하도록 하는 자료구조입니다. poll() 되었을 때 해당 정점의 최소 비용이 확정되었다는 뜻입니다. 즉, 우선순위 큐에서 꺼낸 정점은 그때까지의 경로 중 가장 비용이 낮은 상태로 해당 정점에 도달한 것이므로, 그 정점에 대한 최단 거리가 확정됩니다. 이미 확정된 정점과 if continue : 특정 정점(예: 3번 정점)에 대한 최단 거리가 확정되었다면, 이후에 다른 경로를 통해 같은 정점에 도달하더라도, 그 비용은 항상 이상일 수밖에 없습니다. 따라서 if 문 등을 사용하여 이미 확정된 정점은 더 이상 처리하지 않도록 합니다. 이는 불필요한 처리를 줄이고 실행 효율성을 높여줍니다. 이 내용을 이해하셨다면, 다익스트라가 어떻게 최단 경로를 효율적으로 계산하는지를 이해하신 것입니다. 각 정점을 한 번만 확정하고 나중에 중복 체크를 하지 않도록 하는 것이 이 알고리즘의 핵심 중 하나입니다. 더 자세한 이해를 돕기 위해 유사한 질문의 답변을 참고해 보시길 바랍니다. 특히, 다익스트라 알고리즘 질문드립니다. 게시글이 도움될 수 있습니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.