-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
안녕 하세요
22.10.04 20:03 작성 조회수 176
0
방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택해야 하는 이유가 무엇일까요?
가장 짧은 노드를 선택하는 이유가 짧은 노드 일 수록 더 정답에 가깝기 때문일까요?
짧은 노드로 선택하지 않더라도 문제는 해결이 될 것 같아서요
더 긴 경로가 있다고 전제할 때 짧은 경로로 미리 연산을 해놓았다고 한다면 더 긴경로는 구지 연산을 하지 않아도 되는 비용이기 때문일까요??
답변을 작성해보세요.
0
김태원
지식공유자2022.10.07
안녕하세요^^
가장 짧은 노드는 출발지점에서 해당 노드까지의 최단거리가 이미 확정된 노드이고 가장 짧은 노드에서 퍼져나가야 최단거리를 구하는 알고리즘에 맞는 것 같습니다.
보인이 생각한 아이디어가 있으면 그 방식으로 코드로 짜보고 반례가 있는지 에지케이스를 만들어보세요. 실력향상에 정말 도움이 됩니다.
답변 1