들어가기 앞서
위 사진은 당연히 저 아니구 ㅎㅎ
다익스트라 알고리즘의 창시자이신 에츠허르 비버 데이크스트라 (네덜란드어 : Edsger Wybe Dijkstra) 이시다. 원래도 이 알고리즘이 창시자 이름을 따온건 알고 있었는데 조금 찾아보니 다른 알고리즘도 만드시고 업적도 많고 정말 대단하신 분이더라구요. 그래서 사진을 가져와 봤습니다 ㅎㅎ
그리고 다익스트라 개념을 설명하기 위해서 BFS, 그리디, 우선순위 큐, DP 등 다른 개념들이 조금씩 등장하는데 기본적인 사전 지식이 있다는 가정하에 작성하였습니다. ㅎㅎ
다른 개념은 몰라도 이해하는데 크게 문제가 있을 것 같진 않지만 우선순위 큐와 BFS 정도는 미리 알고 보시는게 이해하는데 편할 것 같습니다.
다익스트라 개념
다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단경로를 구하는 알고리즘입니다.
O(V^2)의 시간복잡도를 가지고 있는 기본 모델과 우선순위 큐(Priority Queue)를 사용하는 O((V+E)logV)의 시간복잡도를 가진 모델이 있습니다. 하지만 보통 다익스트라 알고리즘이라고 하면 우선순위 큐(Priority Queue)를 사용하는 후자를 의미합니다.(당연히 더 빠르기 때문에)
음의 가중치를 가지면 안되는 이유는 다익스트라 알고리즘이 기본적으로 그리디 알고리즘이 들어가는데 음의 가중치를 가지면 이 그리디 알고리즘을 적용할 수 없기 때문입니다. 그래서 음의 가중치를 가진 그래프의 경우 O(VE)의 시간복잡도를 가지는 벨만-포드 알고리즘을 사용합니다.
추가로 가중치가 0인 것은 상관 없습니다.
자세한 내용은 아래 알고리즘 설명에 추가로 적어보겠습니다.
그래서 언제 사용하나?
위 설명 그대로 최단경로를 구할 때 자주 사용합니다. 주로 가장 평범한? 상황에 사용한다고 생각하면 됩니다.
가장 범용성이 높다고 할 수 있죠. 이제 다른 알고리즘을 사용하는 평범하지 않은 상황을 나열해보자면 3가지가 있습니다.
- 가중치가 없는 경우 ⇒ BFS
- 음의 가중치를 지니는 경우 ⇒ 벨만-포드
- 음의 가중치도 있고 모든 노드 간의 최단 경로를 전부 구해야 할 때 ⇒ 플로이드-워셜
사실 BFS에서 가중치가 생겼을 경우에 조금 응용한 것이 다익스트라입니다. 구조도 거의 비슷합니다.
“다익스트라 = BFS + 우선순위 큐 + 메모이제이션” 이라고 볼 수 있는거죠.
BFS의 큐 대신에 우선순위 큐를 쓰고 최솟값을 메모이제이션 해서 최적화 한 것이 다익스트라 입니다. 그래서 BFS 개념을 알고있다면 생각보다 쉽습니다.
우선순위 큐도 간단하게 설명하자면,
말 그대로 우선순위가 존재하는 큐로 기존 큐처럼 넣은 순서대로 뽑는게 아니라 우선순위가 높은 순서대로 큐에서 뽑는 것입니다. 다익스트라 알고리즘에서는 비용(cost)이 가장 작은 노드가 먼저 뽑히게 됩니다.
다익스트라 알고리즘
기본적으로 다익스트라는 “최단 경로”를 구하기 위해서 그리디 개념을 사용합니다. 이를 구현하기 위해 우선순위 큐를 사용하고 또 최솟값을 매번 계산하지 않고 최적화 하기 위해서 메모이제이션 기법을 사용합니다.
그래서 “다익스트라 = BFS + 우선순위 큐(그리디) + 메모이제이션” 이라고 할 수 있습니다.
BFS를 생각해보면 시작 노드에서 연결된 노드들을 q에 넣고 하나씩 빼가면서 반복문을 돕니다.
이 구조가 다익스트라도 동일합니다. 시작 노드에서 시작해서 연결된 노드들을 우선순위 큐에 넣고 하나씩 빼가면서 반복문을 돕니다. 구현은 이게 끝입니다. 정말 쉽죠?
추가로 우선순위 큐에 넣을 때는 모조리 다 넣는게 아니라 위에서 말한 메모이제이션을 이용해서 최적화를 진행합니다. 미리 저장해놓은 최단 경로랑 비교해서 더 작은 경우에만 넣어줍니다. 구현적인 부분은 사실 우선순위 큐가 전부 해주는 셈이죠.
그리고 다익스트라 알고리즘에서 정말 중요하게 꼭 알고 있어야 하는 개념이 있는데
우선순위 큐에서 어느 정점이 꺼내 졌다면, 해당 노드까지는 최솟값 갱신이 완료 되었다는 것이 확정이다(그리디 매커니즘).
매커니즘
- 다익스트라 알고리즘은 기본적으로 그리디 알고리즘이자 메모이제이션 기법을 사용한 알고리즘이다.
- 다익스트라 알고리즘은 기본적으로 아래 두 단계를 반복하여 임의의 노드에서 각 모든 노드까지의 최단거리를 구한다. 임의의 노드에서 다른 노드로 가는 값을 비용이라고 한다.
(1) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다(그리디 알고리즘).
(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다(메모이제이션).
예를 들어 아래 그림에서, A노드에서 출발하여 F노드로 가는 최단 경로를 구하는 문제를 다익스트라 알고리즘을 적용하여 생각해보자.
각 단계마다 기준이 필요하기 때문에, 지금부터는 방문하지 않은 노드의 집합을 Before, 방문한 노드의 집합을 After, 현재까지 A노드가 방문한 곳 까지의 최소 비용을 D[대상 노드]라고 정의하도록 하자. 그렇다면 현재 각 집합이 가지고 있는 값은 다음과 같은 것이다.
<초기화 단계>
그렇다면, 이 상태에서 방문하지 않은 노드 중 가장 비용이 적은 대상 노드는 어디일까? A노드에서 다른 간선으로 가는 비용이 0인 간선이 존재하지 않는다면, 당연히 A노드일 것이다. 또한, 그러한 값이 존재한다고 하더라도 첫 번째 단계에서는 'A노드에서 A노드로 가는 지점이 가장 짧다'라고 그냥 정의하고 시작한다. 즉, 첫 번째 단계에서는 가장 비용이 적은 노드를 선택할 기준이 없기 때문에 출발지인 A노드 자신을 초기 선택 노드로 초기화한다.
아직 A노드를 방문하지는 않았지만, A노드에서 A노드로 가는 비용이 가장 적다라고 정의한 상태.
<알고리즘 적용>
초기화가 끝났으니, 이제 앞서 언급한 두 가지 논리를 그냥 반복해서 적용하면 끝이다. 위 상태에서 방문하지 않은 노드 중 가장 비용이 적은 대상 노드는 어디 인가? 당연히 A노드이다. 또한, A노드를 기준으로 갈 수 있는 인접 노드로의 최소 비용은 얼마일까? 결과는 아래와 같을 것이다.
A노드 방문 완료.
다음 단계는 어떨까? 앞선 단계를 그냥 계속 반복하기만 하면 된다. 현재 상태에서 방문하지 않은 노드 중 가장 비용이 적은 노드는 어디 인가? A노드는 방문 하였기 때문에 B노드가 될 것이다. 따라서 B노드를 방문하고, B노드와 인접한 노드들의 최소 비용을 갱신해주면 된다.
B노드에서 C노드로 가는 비용은 9이다. 하지만 이미 C노드로 가는 최소 비용이 5이므로 갱신할 필요가 없다. B노드에서 F노드로 가는 비용은 아직 모르므로, 최초 방문 값인 12로 설정해 주었다.
다음 단계도 마찬가지이다. 이제는 A노드와 B노드를 방문하였기 때문에, 그 중에서 가장 비용이 적은 노드인 D를 선택하고 방문한 뒤 같은 과정을 진행해주면 된다. 이후 과정은 생략하고 그림과 그림 설명으로 대체하도록 하겠다.
D노드를 거쳐 C노드로 가는 비용은 4이고, 현재까지 C노드로 가는 최소 비용이 5였기 때문에, D[C]를 4로 갱신할 수 있다. 이전 단계와 마찬가지로, E노드로가는 비용은 미정이었기 때문에 최초 방문 값인 10으로 설정할 수 있다.
그 다음으로 선택된 노드는 C이고, C노드에서 E노드로 가는 값과 F노드로 가는 값은 각각 기존 E노드나 F노드로 가는 비용보다 모두 작다. 따라서 각 값을 갱신할 수 있다.
그 다음으로 선택된 노드는 E이고, E노드에서 F노드로 가는 비용은 기존 F노드로 가는 비용보다 작다. 따라서 그 값을 갱신해 주었다.
마지막으로 방문해야하는 노드인 F에서는 더 이상 갈 수 있는 노드가 존재하지 않으므로, 방문만 완료하고 알고리즘을 종료해주면 된다.
모든 노드 방문 완료.
따라서, 다익스트라 알고리즘에 의한 A노드부터 F노드까지(혹은 A노드부터 각 모든 정점 까지)의 최소 비용은 위와 같은 값을 가진다.
코드 구현
O(V^2)
- 한 번 방문한 배열은 방문할 수 없으므로 방문 여부를 체크할 배열이 필요할 것이고, 각 노드 까지의 최소 비용을 저장할 배열이 필요할 것이다.
- 구현에서 고려해 주어야 하는 것은, 미방문 지점의 값을 항상 최소의 값으로 갱신하는 것이 목표이기 때문에, 미 방문 지점은 매우 큰 값으로 초기화하여 로직을 처리해주면 된다(구할 수 있다면, 노드가 가질 수 있는 최대 비용을 넣어두어도 된다).
- 최소 비용을 갖는 노드을 선택하는 과정은 앞선 일반적인 구현에서는 최악의 경우 모든 노드을 확인해야 하고, 이것을 V번 반복하기 때문에 O(V^2)의 시간 복잡도를 갖는다.
JAVA 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
sample output
0
2
3
7
INF
*/
// 도착 지점과, 도착지점으로 가는 비용을 의미하는 클래스를 정의한다.
class Node {
int idx;
int cost;
// 생성자
Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
}
public class Dijkstra1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 노드와 간선의 개수
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
// 출발지점
int start = Integer.parseInt(br.readLine());
// 1. 인접리스트를 이용한 그래프 초기화
ArrayList<Node>[] graph = new ArrayList[V+1];
// 노드의 번호가 1부터 시작하므로, 0번 인덱스 부분을 임의로 만들어 놓기만 한다.
for (int i = 0; i < V + 1; i++) {
graph[i] = new ArrayList<>();
}
// 그래프에 값을 넣는다.
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
// a로 부터 b로 가는 값은 cost이다.
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[a].add(new Node(b, cost));
}
// 2. 방문 여부를 확인할 boolean 배열, start 노드부터 end 노드 까지의 최소 거리를 저장할 배열을 만든다.
boolean[] visited = new boolean[V + 1];
int[] dist = new int[V + 1];
// 3. 최소 거리 정보를 담을 배열을 초기화 한다.
for (int i = 0; i < V + 1; i++) {
// 출발 지점 외 나머지 지점까지의 최소 비용은 최대로 지정해둔다.
dist[i] = Integer.MAX_VALUE;
}
// 출발 지점의 비용은 0으로 시작한다.
dist[start] = 0;
// 4. 다익스트라 알고리즘을 진행한다.
// 모든 노드을 방문하면 종료하기 때문에, 노드의 개수 만큼만 반복을 한다.
for (int i = 0; i < V; i++) {
// 4 - 1. 현재 거리 비용 중 최소인 지점을 선택한다.
// 해당 노드가 가지고 있는 현재 비용.
int nodeValue = Integer.MAX_VALUE;
// 해당 노드의 인덱스(번호).
int nodeIdx = 0;
// 인덱스 0은 생각하지 않기 때문에 0부터 반복을 진행한다.
for (int j = 1; j < V + 1; j++) {
// 해당 노드를 방문하지 않았고, 현재 모든 거리비용 중 최솟값을 찾는다.
if (!visited[j] && dist[j] < nodeValue) {
nodeValue = dist[j];
nodeIdx = j;
}
}
// 최종 선택된 노드를 방문처리 한다.
visited[nodeIdx] = true;
// 4 - 2. 해당 지점을 기준으로 인접 노드의 최소 거리 값을 갱신한다.
for (int j = 0; j < graph[nodeIdx].size(); j++) {
// 인접 노드를 선택한다.
Node adjNode = graph[nodeIdx].get(j);
// 인접 노드가 현재 가지는 최소 비용과
// 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신한다.
if (dist[adjNode.idx] > dist[nodeIdx] + adjNode.cost) {
dist[adjNode.idx] = dist[nodeIdx] + adjNode.cost;
}
}
}
// 5. 최종 비용을 출력한다.
for (int i = 1; i < V + 1; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.println("INF");
} else {
System.out.println(dist[i]);
}
}
}
}O((V+E)logV)
- 기본적으로 다익스트라 알고리즘은 최소 비용을 갖는 노드를 선택하고, 주변 노드의 값을 갱신하였다. 그렇다면, 비용을 나타내는 배열에서 갱신된 노드를 제외하고는 여전히 INF의 값을 갖기 때문에 굳이 고려해줄 필요가 없음을 알게 된다. 즉, 갱신하는 주변 노드의 값에 대해서만 다음 최소 비용을 갖는 노드를 선택해주면 된다는 것이 우선순위큐를 이용하는 것의 핵심이다.
- 우선 순위큐에 들어가는 노드의 수 = 갱신해야하는 주변 노드의 수라고 하였다. 이 말을 다르게하면, 갱신해야하는 주변 노드의 수 = 갱신해야 하는 주변 노드로의 간선의 수를 말한다. 즉, 우선 순위 큐에 삽입하는 최대 횟수는 간선의 개수이다. 따라서, 모든 간선에 대하여 삽입 연산이 발생하기 때문에 최대 O(ElogE)의 시간이 걸릴 것이다. 그런데, 희소 그래프의 경우 E <= V^2이므로, 최대 O(ElogV)의 시간이 걸린다고도 볼 수 있다. 각 노드들을 우선순위큐에 추출해주는 연산에대해서는 최대 V개의 노드에 대하여 우선순위큐에서 추출할 것이므로 최대 O(VlogV)의 시간이 걸릴 것이고 따라서 최대 모든 노드, 간선에대하여 우선 순위큐를 계산해줘야 하므로 O((V+E)logV)의 시간이 걸릴 것이다.
※주의할 점
- 우선순위 큐에 넣는 다음 노드는 최소 비용으로 선택된 노드의 주변 노드라고 하였다. 그런데, 이 주변 노드를 무차별적으로 우선순위큐에 넣고 무차별적으로 검사를 한다면 문제가 발생한다. 즉, 최소 비용으로 뽑은 노드의 방문 체크를 하지 않는 경우와 갱신이 이루어 지지 않는 노드까지 우선 순위큐에 넣는 경우 모두 중복된 노드를 재방문 하게 되는 문제가 발생한다. 자세한 내용은 아래 코드의 주석을 참고하자.
- 시간 복잡도의 핵심은 poll() 연산(최소 비용을 뽑는 연산)과 offer() 연산(최소 비용 후보를 우선 순위큐에 넣는 연산)이다. 만일, 중복 노드를 무차별적으로 큐에 넣는다면 위에서 결과적으로 말한 최대 V개의 노드에서 우선순위큐를 추출하는 O(VlogV)가 보장되지 못한다. 따라서, 중복 노드 방문을 두 가지 조건을 기반으로 방지한다.
JAVA 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
sample output
[2147483647, 0, 2, 3, 7, 2147483647]
*/
public class Dijkstra2 {
static int V, E, start;
static ArrayList<Node>[] graph;
static int[] dist;
static class Node {// 다음 노드의 인덱스와, 그 노드로 가는데 필요한 비용을 담고 있다.
int idx, cost;
Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
}
public static void main(String[] args) throws IOException {
// 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine());
graph = new ArrayList[V+1];
for (int i = 0; i < V + 1; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
// a로 부터 b로 가는 값은 cost이다.
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 문제에서는 유향 그래프에서의 다익스트라 알고리즘(이 조건도 문제에 따라 중요하다!).
graph[a].add(new Node(b, c));
}
// 다익스트라 알고리즘 초기화
dist = new int[V + 1]; // 최소 비용을 저장할 배열
for (int i = 0; i < V + 1; i++) {
dist[i] = Integer.MAX_VALUE;
}
dijkstra();
// 결과 출력
System.out.println(Arrays.toString(dist));
}
private static void dijkstra() {
// 주의점 1. 다익스트라 알고리즘의 최소비용을 기준으로 추출해야 한다.
PriorityQueue<Node> q = new PriorityQueue<Node>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
// 시작 노드에서, 시작 노드로 가는 값이 초기에 가장 짧은 비용을 갖는 노드이다.
// 즉, 도착 정점은 start, 비용은 0인 노드를 가장 먼저 선택할 것이다.
q.offer(new Node(start, 0));
// 해당 노드를 선택한 것이나 마찬가지 이므로, dist[start] = 0으로 갱신.
dist[start] = 0;
while (!q.isEmpty()) {
Node curNode = q.poll();
// ***목표 정점이 꺼내 졌다면, 해당 노드까지는 최솟값 갱신이 완료 되었다는 것이 확정이다(다익스트라 알고리즘).***
// 따라서, 반복문을 종료해도 되지만, 해당 코드는 시작 정점에 대하여 모든 정점으로의 최단 경로를 구하는 것을 가정한다.
// 아래 주석된 코드는 목표 정점이 구해졌다면 빠르게 탈출할 수 있는 조건이다.
// if (curNode.idx == end) {
// System.out.println(dist[curNode.idx]);
// return;
// }
// 꺼낸 노드 = 현재 최소 비용을 갖는 노드.
// 즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다 크다면 고려할 필요가 없으므로 스킵한다.
// dist 배열이 중복을 방지해줘서 visited 배열은 따로 필요없다.
// 주의점 2 : 중복노드 방지1 : 만일, 이 코드를 생략한다면, 언급한 내용대로 이미 방문한 정점을 '중복하여 방문'하게 된다.
// 만일 그렇다면, 큐에 있는 모든 다음 노드에대하여 인접노드에 대한 탐색을 다시 진행하게 된다.
// 그래프 입력이 만일 완전 그래프의 형태로 주어진다면, 이 조건을 생략한 것 만으로 시간 복잡도가 E^2에 수렴할 가능성이 생긴다.
if (dist[curNode.idx] < curNode.cost) {
continue;
}
// 선택된 노드의 모든 주변 노드를 고려한다.
for (int i = 0; i < graph[curNode.idx].size(); i++) {
Node nxtNode = graph[curNode.idx].get(i);
// 만일, 주변 노드까지의 현재 dist값(비용)과 현재 선택된 노드로부터 주변 노드로 가는 비용을 비교하고, 더 작은 값을 선택한다.
// 주의점 3 : 중복노드 방지 2 : 만일, 조건문 없이 조건문의 내용을 수행한다면 역시 중복 노드가 발생한다.
// 간선에 연결된 노드를 모두 넣어준다면 앞서 언급한 정점의 시간 복잡도 VlogV를 보장할 수 없다.
// 마찬가지로 E^2에 수렴할 가능성이 생긴다. 따라서 이 조건 안에서 로직을 진행해야만 한다.
if (dist[nxtNode.idx] > curNode.cost + nxtNode.cost) {
dist[nxtNode.idx] = curNode.cost + nxtNode.cost;
// 갱신된 경우에만 큐에 넣는다.
q.offer(new Node(nxtNode.idx, dist[nxtNode.idx]));
}
}
}
}
}Reference
