다익스트라 최단거리, 왜 O(V^2+E)가 아닌가?

O(E)는 O(V^2)때문에 무시할 수 있다. 그래서 O(V^2)로 나타낸다.

목차

1. 다익스트라 최단 경로 알고리즘
2. 예시
3. 시간 복잡도

1. 다익스트라 최단 경로 알고리즘

특정 노드에서 다른 각각의 노드까지 최단 경로를 구하는 알고리즘이다.
단, 간선은 음이 아닌 가중치를 가져야 한다.

단순하게, 최단 경로의 거리를 구하는 방법을 살펴보자.
시작 노드에서 각 노드들까지의 최단 거리를 저장하는 테이블에서, 최소의 최단 거리를 가진 노드를 방문했다고 표시한다. 방문하는 노드와 연결된 다른 노드까지의 거리와, 그 노드를 거치지 않은 거리를 비교하여 최솟값으로 최단 거리 테이블을 업데이트한다. 이 과정을 모든 노드에 대해 최단 경로 거리를 구할 때 까지 반복한다.

이 때 방문한 노드는 더이상 방문하지 않고 거리를 계산하지 않는다.
간선의 가중치는 음이 아니며, 해당 노드를 방문할 때 거리는 이미 그 상황에서 다른 경로들 중 가장 작은 거리값이었다. 따라서 방문한 노드에 대해 다시 방문하거나 경로를 계산하는 것은, 그 결과가 무조건 최단 거리 이상의 값이기 때문에 불필요하다.

2. 예시

다음과 같은 그래프가 있다. 시작 노드가 1번 노드일때, 각 노드까지의 최단 경로의 거리를 구해보자. 최단 거리 테이블은 시작 노드는 0, 나머지는 무한대로 초기화한다.

1번 노드 방문

현재 최단 거리가 가장 작은 1번 노드를 방문한다.
1번과 연결된 노드는 2번, 4번, 5번노드이다.
세 노드 모두 1번노드를 거쳐 갈 때 거리가 짧아지므로, 최단 거리 테이블을 업데이트한다.

2번 노드 방문

현재 최단 거리가 가장 작은 2번 노드를 방문한다.
2번과 연결된 노드는 3번, 4번 노드이다.
두 노드 모두 2번을 거쳐 갈 때 거리가 짧아지므로, 2번의 최단 경로에 각각의 간선 가중치를 더한 값을 업데이트한다.

4번 노드 방문

현재 최단 거리가 가장 작은 4, 5번 노드중 번호가 먼저인 4번 노드를 방문한다.
4번과 연결된 노드는 3번 노드이다.
4번 노드를 거쳐가는 경우, 이전보다 거리가 더 길어지므로 값을 업데이트하지 않는다.

5번 노드 방문

현재 최단 거리가 가장 작은 5번 노드를 방문한다.
5번 노드와 연결된 노드는 4번 노드이다.
4번 노드는 이미 방문한노드이므로 최단 거리를 계산하지 않는다.

3번 노드 방문

현재 최단 거리가 가장 작은 3번 노드를 방문한다.
3번 노드와 연결된 노드는 4번 노드이다.
4번 노드는 이미 방문한노드이므로 최단 거리를 계산하지 않는다.

더이상 방문할 수 있는 노드가 없다.
최단 경로 거리를 계산을 완료했다.

3. 시간 복잡도

다익스트라 알고리즘은 다음과 같은 과정으로 수행된다.

1. 최단 거리 테이블에서 가장 최단 거리가 작은 노드를 찾는다.
2. 찾은 노드에서, 연결된 각각의 노드에 대해 경로를 계산한다. 만약 계산 결과가 최단 거리 테이블에 저장된 값보다 작다면, 테이블을 업데이트한다.
3. 위 과정을 모든 노드를 방문할 때 까지 반복한다.

노드의 개수를 V, 간선의 개수를 E라고 하자.

1번 과정은 V만큼 반복된다. 모든 노드를 방문할 때 까지 반복하기 때문이다.

1번과정에서 최단 거리가 가장 작은 노드를 찾기 위해서는 최단 거리 테이블을 순차 탐색(선형 탐색)해야 한다. 따라서 1번 과정을 수행할 때 마다 V만큼의 시간이 소요된다.

2번 과정은 총 E번 수행된다. 방문한 노드는 재방문하지 않기에 모든 간선이 1번씩 이용되기 때문이다.

그래서 총 시간 복잡도는 이렇게 표현할 수 있다.

$${O(V)*O(V)}+O(E) = O(V^2+E)$$

최악의 경우는 모든 노드는 서로 연결되어 있는 것이다. 이 때 간선의 개수 E는,

$$E = V*(V-1) = V^2-V$$

이다. 이제 O(E)를 다시 나타낼 수 있다.

$${O(V)*O(V)}+O(E) = {O(V)*O(V)}+O(V^2-V) = O(2V^2-V) = O(V^2)$$