Algorithem/알고리즘 이론
Dijkstra 다익스트라 : 고정된 출발지에서 다른 노드들까지의 최단거리찾기
1. 힙 없이 완전 탐색 1. 출발지에서 다른 노드들까지의 거리를 저장한다. (각 노드까지의 최단거리를 갱신해가는 과정) 직접 연결되지 않은 노드들은 거리를 무한대로 놓는다. 출발지를 들렀다고 표시한다. 2. 들르지 않은 노드 가운데 가장 가까운 노드를 선택한다. 3. 선택한 노드를 거쳐서 직접 연결된 다른 노드까지 도달하는 거리가 이미 저장된 거리보다 짧다면 최단 거리를 갱신한다. 4. 2~3을 모든 노드를 방문할때가지 반복한다. 모든 노드를 들르면서 위의 과정을 진행하기 때문에 O(N) 의 연산이 필요하다. 거기에 2번을 완탐으로 탐색하게 되면 매번 O(N)이 걸리므로 총 O(N^2) 이 필요한 알고리즘이다. 2. 최소힙 사용 2. '기장 가까운 노드 찾기'를 더 빠르게 수행하기 위해 최소힙을 사용해..
