시카로의 공부방

다익스트라 알고리즘은 하나의 정점에서 다른 정점으로 갈 때, 최단 경로를 알려주는 알고리즘이다. 여러개의 정점이 존재하는 그래프에서, 간선에 다음 노드로 가는 거리가 표시된다. 그 이후, 각 상황마다 갈 수 있는 짧은 경로를 선택한 뒤, 전에 있던 경로와 비교 갱신하여 최단 거리를 찾는다. 정확한 순서는 다음과 같다. 1. 출발 노드 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장(위에서는 P와 U. 나머지는 inf 처리하는데 그냥 충분히 높은 값을 주면 된다.) 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택(여기서는 P) 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신(즉, P에서는 X,Q로 갈 수 있는데 X로 가는 방식이 3+1과 2+4가 있..