[Algorithm] Dijkstra (다익스트라 알고리즘) 이론 설명

다익스트라 알고리즘

Overview

그래프 최단 경로를 찾는 알고리즘으로서, 특정한 하나의 정점 노드에서 다른 모든 정점 노드로 가는 최단 경로를 구하는 알고리즘입니다. ( 시간복잡도: $O(V^{2}$) )

다익스트라 알고리즘은 그리디와 동적 프로그래밍 알고리즘 모두로 보고 있습니다. 
왜 둘다로 여기는지는 참고 사이트와 아래 Introduce를 확인해주세요.

* 다익스트라 알고리즘은 음의 간선이 존재하지 않는 경우 사용할 수 있습니다.

Introduce

카카오나 네이버 맵 등에서 출발지부터 도착지까지 가장 빠른 경로를 어떻게 찾아서 알려줄까요?
이럴 때 다익스트라 알고리즘을 사용합니다.

다익스트라 알고리즘은 컴퓨터 과학자인 Edsger W.Dijkstra로부터 1956년에 만들어진 그래프에서 단일 최단 경로를 찾는 알고리즘입니다. 이는 특정 정점으로부터 연결된 모든 정점의 최단 경로를 찾는 알고리즘이란 뜻입니다. 이 과정에서 도착 정점 뿐만 아니라 다른 모든 정점의 최단 경로까지 찾습니다. 

즉, 매번 최단 경로의 정점을 선택해 탐색 반복하며(그리디 알고리즘 성격), 정점과 정점 사이 경로 갱신을 위해 이전에 구했던 경로 값을 사용합니다. (다이나믹 알고리즘 성격) 

다익스트라 알고리즘은 유방향(directed)과 무방향(undirected)에서 양의 간선인 경우 동작 가능합니다.

• 유방향 (directed): 방향이 있는 간선을 가지는 그래프 (간선은 단방향 관계를 나타냄)
• 무방향 (undirected): 방향이 없는 간선을 가지는 그래프 (간선은 양방향 관계를 나타냄)

Algorithm

1. 출발 정점 설정 (출발 정점 최소 비용은 0으로 설정, 자기자신으로 이동하는 비용이기 때문)

2. 정점 방문 여부를 체크하는 리스트 생성 (visited list)

3. 최단 거리 리스트 생성 (dijkstra list)

4. 선택된 정점의 인접한 정점들 중, 아직 방문하지 않았고 비용이 가장 적은 정점 선택

5. 4번에서 선택한 정점의 인접한 정점을 거쳐 이동하는 비용과 최단 거리 리스트의 비용 중 더 작은 비용으로 갱신

6. 해당 정점 방문 완료 표시 (visited[vertex] = 1)

7. 모든 정점을 방문할 때까지 위 4-6 과정 반복

8. 출발 정점부터 도착 정점의 최소 비용 추출

* 최단 거리 리스트: 1차원 배열로 N개의 정점 이동에 필요한 최소 비용 저장 리스트
* 정점 방문 여부 리스트: 이미 방문한 정점인지 아닌지 확인하기 위한 리스트 (0으로 초기값 설정)

Example

무방향(undirected) 그래프로 설명합니다.

위 그래프에서 다익스트라 알고리즘 동작을 알아보겠습니다.

Algorithm 파트에서 알아본 2번과 3번을 각각 dist, visited로 가정하여 설명이 진행됩니다.
다익스트라는 최소 경로를 찾는 목적의 알고리즘이기 때문에 dist 리스트의 초기값은 가장 큰 값을 가지는 inf(무한대)로 초기화합니다.
방문 여부를 나타내는 리스트는 아직 방문을 한 적이 없기 때문에 모두 0으로 초기화합니다.

출발 정점으로 1번을 선택합니다.

1번 정점에서 1번 정점으로 이동하는 비용은 없기 때문에 dist 리스트는 0으로 설정합니다.

1번 정점을 방문했기 때문에 1번 정점의 방문 리스트는 1로 설정합니다. 

이후 1번 정점과 연결된 인접 정점들을 탐색하고 최소 비용으로 갱신하는 작업을 진행합니다.

Algorithm 파트 4번에서 6번 진행

1번 정점과 인접한 2번, 3번 5번 정점의 이동 비용과 기존 dist 리스트에 이동 비용 중 더 작은 값으로 갱신합니다.

이후 인접한 정점들 중 아직 방문하지 않았으며 가장 낮은 이동 비용을 가지는 정점을 선택합니다. (3번 정점 선택)

3번 정점의 방문 리스트를 1로 설정합니다.

이후 3번 정점과 연결된 인접 정점들을 탐색하고 최소 비용으로 갱신하는 작업을 진행합니다.

Algorithm 파트 7번 (3번에서 6번 반복)

3번 정점과 인접한 2번, 5번 정점의 이동 비용과 기존 dist 리스트에 이동 비용 중 더 작은 값으로 갱신합니다.

"출발 정점을 기준"으로 이동 비용을 구하고 있으니 (1번 -> 2번 정점으로 움직이는 12의 비용)과 ( (1번 -> 3번 정점의 5 비용) + (3번 -> 2번 정점의 6 비용) ) 중 작은 비용을 구하여 갱신합니다. (5번도 동일하게 진행)

이후 인접한 정점들 중 아직 방문하지 않았고 가장 낮은 이동 비용을 가지는 정점을 선택합니다. (2번 정점 선택)

2번 정점의 방문 리스트를 1로 설정합니다.

이후 2번 정점과 연결된 인접 정점들을 탐색하고 최소 비용으로 갱신하는 작업을 진행합니다.

2번 정점과 인접한 정점인 1번, 3번은 이미 방문을 했던 정점입니다.

2번 정점에선 더 이상 최소 비용을 계산할 정점이 없기 때문에, 2번 정점 다음으로 낮은 이동 비용을 가지는 정점을 탐색합니다. (5번 정점 선택)

5번 정점과 인접한 4번 정점의 이동 비용과 기존 dist 리스트에 이동 비용 중 더 작은 값으로 갱신합니다.

"출발 정점 기준"으로 이동 비용을 구하고 있으니 (1번 -> 4번 정점으로 움직이는 inf(무한대) 비용)과 ( (1번 -> 3번 -> 5번 정점의 12 비용) + (5번 -> 4번 정점의 10 비용) ) 중 작은 비용을 구하여 갱신합니다.

이후 인접한 정점들 중 아직 방문하지 않았고 가장 낮은 이동 비용을 가지는 정점을 선택합니다. (4번 정점 선택)

4번 정점에선 더 이상 방문 가능한 정점이 존재하지 않기 때문에 알고리즘이 종료됩니다.

즉, 1번 정점에서 4번 정점까지 가기 위한 최단 경로는 22임을 알 수 있습니다. (1번 -> 3번 -> 5번 -> 4번 경로)

만약, 예시로 들었던 정점과 간선의 이동 비용을 지하철 정류장과 각 정류장 별 걸리는 소요시간이라고 가정한다면 최단 시간인 22분으로 1번역부터 4번역까지 가는 길을 안내할 수 있습니다.

Time Complexity

다익스트라 알고리즘의 시간복잡도는 $O(V^{2}$)입니다. (V는 그래프 정점의 수)

1. 방문하지 않은 가장 작은 비용 경로를 찾기 위해 정점을 탐색해야 합니다. 이를 위해선 인접한 모든 정점을 방문해야하기 때문에 O(V)의 복잡도가 필요합니다. (가장 작은 비용 경로를 탐색하며 모든 정점 방문)
2. 인접 정점을 이용한 이동 비용과 기존 정점의 이동 비용 사이 최소 비용을 계산하여 최단 거리 리스트에 갱신합니다. 이는 O(1)
3. 각 정점에 다른 모든 정점들이 연결된 경우 V-1의 간선이 생깁니다. (정점이 5개면 각 정점마다 4개의 간선이 각 정점마다 연결) V-1개의 정점의 최소 비용을 모두 갱신하는데에는 O(V-1) * O(1) = O(V)의 시간복잡도가 필요합니다. (V-1은 V로 계산)

즉, 위 조건을 정리하면 다음과 같습니다.

• 모든 그래프 정점을 방문하는데 O(V), 위 1번
• 하나의 정점에서 인접한 정점을 탐색하고 갱신하는데 O(V), 위 2-3번
• 모든 정점을 방문하며 각 정점마다 인접한 정점을 탐색하고 갱신하는데 O(V) * O(V) = $O(V^{2}$)

따라서 다익스트라 알고리즘은 $O(V^{2}$)의 시간복잡도를 가집니다.

하지만 다익스트라 알고리즘은 인접 리스트와 최소힙을 이용하여 방문하지 않은 정점을 관리하면 시간 복잡도를 O((V+E)logV)로 줄일 수 있습니다.(V는 그래프 정점의 수, E는 그래프 간선의 수)

1. 인접 리스트 생성과 인접한 정점(간선)을 방문하는데 O(V+E) (모든 정점 V에 대해 인접한 정점의 최대 V-1를 방문함, 이 때 V-1의 정점은 그래프 간선의 수 E로 볼 수 있음)
2. 최소힙에서 최소값을 찾는데 O(logV)
3. 모든 정점을 방문하며 인접 정점의 최소 비용을 탐색하고 갱신하는데 O(V+E)*O(logV) = O((V+E)logV)

*	O(V+E)가 제대로 이해되지 않는 분들은 최소힙 + 우선순위큐로 구현된 코드를 참고 부탁드립니다. 모든 정점에 대해 heapify하고 (O(V)) 이후 인접 정점들을 탐색 (그래프 간선으로 볼 수 있음, O(E))하기 때문에 O(V+E)로 계산됩니다.

참고문헌

[1]	https://stackoverflow.com/questions/14038011/dijkstras-algorithm-a-greedy-or-dynamic-programming-algorithm

[2]	https://www.scaler.com/topics/data-structures/dijkstra-algorithm/
[3]	https://iq.opengenus.org/time-and-space-complexity-of-dijkstra-algorithm/