사부작사부작해요

O(E)는 O(V^2)때문에 무시할 수 있다. 그래서 O(V^2)로 나타낸다. 목차 다익스트라 최단 경로 알고리즘 예시 시간 복잡도 1. 다익스트라 최단 경로 알고리즘 특정 노드에서 다른 각각의 노드까지 최단 경로를 구하는 알고리즘이다. 단, 간선은 음이 아닌 가중치를 가져야 한다. 단순하게, 최단 경로의 거리를 구하는 방법을 살펴보자. 시작 노드에서 각 노드들까지의 최단 거리를 저장하는 테이블에서, 최소의 최단 거리를 가진 노드를 방문했다고 표시한다. 방문하는 노드와 연결된 다른 노드까지의 거리와, 그 노드를 거치지 않은 거리를 비교하여 최솟값으로 최단 거리 테이블을 업데이트한다. 이 과정을 모든 노드에 대해 최단 경로 거리를 구할 때 까지 반복한다. 이 때 방문한 노드는 더이상 방문하지 않고 거리를 ..