다익스트라 알고리즘(Dijkstra's Algorithm)

목차

1. 다익스트라 알고리즘이란?
2. 알고리즘 사용 예시
3. 시간 복잡도

1. 다익스트라 알고리즘이란?

기본적으로 두 정점사이의 최소 거리를 구하는 알고리즘입니다.
활용성이 좋은 알고리즘으로서 변형되는 경우가 많습니다.
가장 많은 방법으로 사용되는 경우는 한 특정 정점에서 각 정점의 거리를 구하는 방법입니다.
즉, DP를 사용하는 최단 경로를 구하는 알고리즘입니다.

이번 시간에는 한가지 그래프를 예시로 들어 다익스트라 알고리즘을 사용해 최단 경로 거리를 산출해 보겠습니다.

2. 그래프 최단 거리 산출

다음의 그래프에서 1번 정점에 대한 최소 거리들을 구해 보겠습니다.

우선 1번 정점에 연결된 정점에 연결된 선의 가중치를 저장합니다.
연결되지 않은 정점에는 무한대를 입력합니다.

여기서 1번 정점을 제외하고 저장한 가중치가 가장 작은 정점을 선택합니다.
위 예시의 경우 2번 정점이 선택됩니다.
이 때 2번 정점과 연결된 정점들(4, 5)을 주목해주세요.
연결된 정점 중 하나를 i라고 표현한다면 다음의 두가지 값을 비교해야 합니다.

i정접에 저장된 가중치
2번 정점의 가중치 + 2번 정점에서 i정점까지의 가충치

둘 중 낮은 값을 다시 i번째의 가중치로 저장합니다.
2번 정점이 선택된 후의 과정을 저장하면 다음과 같이 됩니다.

선택되지 않은 정점들 중 가장 낮은 가중치를 가진 정점을 선택하고 이를 연결된 정점들을 살펴보는 과정을 모든 정점이 선택될 때까지 반복합니다.

2번 정점을 선택했을 때와는 달리 3번, 5번 정점의 가중치는 변하지 않았습니다.
이는 기존에 저장되었던 가중치가 더 낮았기 때문입니다.

이 과정을 끝까지 반복하면 아래와 같은 모습이 됩니다.

이 결과로 얻게된 배열이 1번 정점에 대한 각 정점의 최소 거리입니다.

3. 시간 복잡도

정점의 갯수가 N이라면 엣지의 갯수는 최대 (N (N - 1))/2입니다.
엣지에 방향까지 있다면 최대 (N (N - 1))까지 됩니다.
심지어 위 엣지의 갯수를 M이라 할 경우 앞서 설명한 알고리즘을 이중 배열의 형태로 저장해 연산할 경우 O(M ^ 2)늘어납니다.
M의 최대값의 경우를 생각하면 무시할 수 없게 됩니다.
그렇기 때문에 힙과 같은 구조를 사용하여 각 엣지에 대한 가중치를 저장하여 시간복잡도를 O(N * log N)까지 줄일 수 있습니다.