질문&답변
다익스트라 알고리즘 질문이 있습니다.
안녕하세요. 빠른 답변 감사드립니다! 적어주신 답변에 대해서는 한참을 보고, 좀 더 찾아보고 다시 글을 적습니다. 그런데도 제가 포인트를 제대로 잡지 못하고 있는것인지.. 완전히 이해가 가지는 않았습니다ㅠ 혹은 제 질문이 조금 잘못 됐을 수도 있을것 같은데요. 일단 정확한 질문은 " 이때까지 발견된 노드 중에 거리가 가장 짧은 노드를 방문한다 "에 대한 의문이 었습니다. 이때까지 발견한 노드 중에 선택을 하는 것은 맞지만 왜 가장 짧은 거리의 노드일까? 라는 것인데요. 사실상 새로운 정점을 방문하면, 혹시 뒤늦게 더 좋은 경로를 발견한게 아닐까? 라는 마음에 나머지 N개의 정점 경로를 다시 다 방문을 해보면서 cost 계산을 다시 해봐야 한다는 말이 되죠. -> 실제로 코드를 보면 이미 최선인 1번을 선택(발견된 노드 중 가장 짧은 거리의 노드) 하고도 1번과 연결된 모든 루트에 대해서 비교 하여 distance를 갱신하는 과정이 진행됩니다. 1번을 선택했다고 하여 3번에 대한 검증을 안하지 않는다는 것이죠. 3번을 선택했다 해도 같은 루틴을 반복할 것이고, 간선이 더 있다고 해도 상황이 달라지지 않을것 같다는 생각이 듭니다. 그래서인지 말씀하신 내용이 잘 와닿지가 않고 있습니다 ㅠ 그래서 제가 생각하는 것은 "이때까지 발견된 노드 중에 가장 짧은 노드를 선택하는 것은 나중에 다시 갱신될 여지가 있지만 가장 짧은 거리의 노드를 선택하는 것이 더 가까운 루트일 확률이 높기 때문" 정도로만 혼자 정리를 한 상태인데.. 제가 잘못 이해하고 있는 포인트가 있다면 조금만 더 자세하게 알려주시면 감사하겠습니다! 가장 짧은 걸 선택하지 않았을 때 느려지는 예를 조금만 더 디테일하게 부탁드리겠습니다.. 강의 제작으로 바쁘실텐데 번거롭게 해드려 죄송합니다.
- 좋아요수
- 0
- 댓글수
- 3
- 조회수
- 394