다익스트라 알고리즘은 어떤 그래프 내에서 출발노드를 지정하여, 출발 노드에서 모든 노드로의 최소비용을 구하는 알고리즘이다.
다익스트라 알고리즘은 다음과 같은 순서로 진행된다.
- 출발 노드를 정한다.
- 출발 노드로부터 갈 수 있는 모든 노드들에 대해 최소비용을 갱신한다.
- 방문하지 않은 노드중 최소비용의 노드를 선택한다.
- 선택된 노드로 부터 갈 수 있는 노드들에 대해 최소비용을 갱신한다.
- 3 ~ 4를 반복한다.
이 루틴을 구현해 보면 정상적으로 실행된다는 결과는 얻을 수 있었지만,
3번, 왜 방문하지 않은 노드 중 최소값을 선택하는지 개념적으로 이해하지 못했다.
이를 이해하기 위해 먼저 아래 그림에서 1번노드를 출발노드로 실행되는 과정을 살펴 보았다.
아래 그림에서 출발노드인 1번 노드에서 갈 수 있는 노드는 2, 4노드 둘이다.
알고리즘의 실행 순서에 따라 최소비용의 노드인 2번 노드를 선택한다.
이 이유는 출발노드인 1번 노드에서 2번으로가는 모든 경로 중 가장 작은 비용을 가지기 때문에
2번으로의 최소비용이 고정되기 때문이였다!!!!!!! (다른 노드를 경유하는 비용은 모두 2번 비용보다 크고, 앞으로 더 커질 것이므로!!)
다음으로, 2번에서 노드들로의 비용을 갱신함으로써 3번으로의 최소비용이 갱신되었다.
이제, 방문하지 않은 노드중 최소비용의 노드( 4번 노드 )를 선택한다.
이는 1번에서 4번으로 갈 수 있는 모든 경우에 대해 비용 60이 최소비용임을 알았음으로, 선택하는 것이다.
위와 같은 과정이 반복됨으로서 출발지로부터 모든 노드로의 최솟값이 결정되게 된다.
질문있으면 답글 달아주시면 성실히 답변하겠습니다.