Inflearn Community Q&A
asked
다익스트라 알고리즘 강의듣고 질문드립니다.
Resolved
Written on
·
140
0
안녕하세요
다익스트라 알고리즘 강의 듣고 질문드립니다.
다익스트라 알고리즘 코드 파일에서 Algorithm.cpp 파일 52~59번째 줄에
for (auto it = discovered.begin(); it != discovered.end(); it++)
{
if (it->cost < bestCost)
{
bestCost = it->cost;
bestIt = it;
}
}
이런 코드가 있고
이 코드는 각 발견한 Vertex를 순회하면서 제일 좋은 후보를 찾는다고 되어 있는데
왜 최적의 Vertex를 찾아야 되는지 이해가 안되서 질문드립니다.
최적의 Vertex를 찾아도 discoverd가 empty()가 될때까지 모든 연결된 Vertex를 순회해서
최적인지 아닌지를 체크하는데도 미리 최적의 Vertex를 찾는지 궁금합니다.
기술면접
Answer 1
0
rookiss
Instructor
다익스트라 알고리즘이 그렇게 동작하기 때문입니다.
발견한 여러 갈래의 길들 중에 가장 우수한 후보를 뽑아서 가는 것이고
그렇기 때문에 최단거리가 보장이 되는 것입니다.
항상 최적 경로의 Vertex만 선택해서 최적 경로로 거리를 갱신하므로
최단 경로가 보장되네요
이해 되었습니다 답변 감사합니다