다익스트라 강의 관련 질문이 있습니다.

안녕하세요? 답변이 다소 늦어서 죄송합니다! 🙂

우선순위큐에 중복 노드 삽입은 어느 정도 존재할 수는 있으나(나중에 방문한 경로가 최단거리일 수 있기 때문에), 원소를 빼는 과정에서 최적화를 추가해 줄 필요성은 있습니다.

이를테면, 우선순위큐에서 원소를 뺄 때, 해당 원소가 가지고 있는 거리값이 dist에 저장되어 있는 노드의 최단거리보다 크다면 while문을 건너 뛰고 continue 하는 로직을 추가해주는 것입니다. 그렇게 하면 노드가 중복 삽입되더라도 중복 삽입된 노드 중 최단경로일 때만 인접 노드를 재방문하는 for문이 실행될 것입니다.

제공해주신 사진에서는 26 ~ 28번 라인 사이에 비교 로직을 추가하는 것이 좋습니다.

잘못 구현한 다익스트라 알고리즘 저격하기 (infossm.github.io)

상기 글을 참고하시면 도움이 많이 될 것 같습니다 🙂

안녕하세요, 인프런 AI 인턴입니다.

답변 드리기 전에 해당 강의의 ‘수강 전 문의 게시판’을 활용하는 방법을 추천드립니다. 수강 전 문의 게시판을 통해 해당 강의의 지식공유자인 DaBin Han님께 직접 문의를 하실 수 있어요. 수강 전 문의하기 기능이 구성된 강의에 한해서 이용할 수 있으니, 강의 상세 페이지에서 해당 기능이 제공되는지 확인해보시길 바랍니다.

질문 1에 대한 답변:
다익스트라 알고리즘에서는 방문 여부를 확인하는 visit 배열 대신 거리 배열인 dist를 사용하여 최단 거리를 업데이트하는 방식을 통해 구현할 수 있습니다. visit 배열을 사용하지 않은 구현 방식은 간선의 가중치가 모두 양수일 경우, 최소 힙(min heap)을 활용하여 이미 방문한 노드를 걸러낼 수 있기 때문에 visit 배열 없이도 올바르게 동작합니다. 하지만 알고리즘의 판단 직전에 방문 여부를 확인하는 것도 하나의 최적화 방법이 될 수 있습니다.

질문 2에 대한 답변:
우선순위 큐에 노드가 중복으로 삽입되는 경우, 알고리즘은 여전히 정확하게 동작하지만, 큐에 불필요한 요소들이 쌓이면서 성능 저하를 일으킬 수 있습니다. 이는 큐에서 원소를 꺼냈을 때, 이미 방문해 거리가 업데이트된 노드는 무시하게 됨으로써 해결되긴 하지만, 중복된 노드들이 큐에 존재함으로 인해 최악의 경우 시간 복잡도에 영향을 줄 수 있습니다. 그럼에도 불구하고 우선순위 큐를 이용한 구현은 간편하고 가독성이 좋아 많이 사용되는 방식입니다.

알고리즘과 자료구조에 대한 궁금증 해결에 도움이 되셨기를 바라며, 추가적인 궁금한 사항이 있다면 인프런의 ‘문의하기’ 기능을 통해 질문하실 수 있다는 점을 알려드립니다. 알고리즘 학습에 성공하시길 바랍니다.

감사합니다.