1. 다익스트라 (dijkstra)
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다.
특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다.
다익스트라 알고리즘의 핵심 이론
1. 인접 리스트로 그래프 구현한다.
먼저 다음과 같이 주어진 그래프를 인접 리스트로 구현한다.
다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다. 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언한다.
2. 최단 거리 배열을 초기화 한다.
최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다. 이때 무한은 적당히 큰 값을 사용하면 된다.
3. 값이 가장 작은 노드 고르기
최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작하면 된다.
4. 최단 거리 배열을 업데이트한다.
선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다. 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트한다.
5. 과정 3~4를 반복해 최단 거리 배열을 완성한다.
모든 노드가 처리될 때까지 과정 3~4를 반복한다. 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성된다.
마지막으로 다시 한번 정리하면 다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이고, 에지는 항상 양수이어야 한다는 제약 조건이 있다. 많은 사람들이 다익스트라 알고리즘이 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이라고 생각하는 경향이 있는데, 실제로 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현한다.
2. 벨만-포드 (bellmanford)
벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
벨만-포드의 핵심 이론
1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화한다.
벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 또한 최단 경로 리스트를 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
2. 모든 에지를 확인해 정답 리스트를 업데이트한다.
최단 거리 리스트에서 업데이트 반복 횟수는 노드 개수 -1이다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1 이기 때문이다. 모든 에지 E = (s,e,w)에서 다음 조건을 만족하면 업데이트를 실행한다. 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리이다.
업데이트 조건과 방법
dist[s] != Integer.MAX_VALUE이며 dist[e] > dist[s] + w 로 리스트의 값을 업데이트한다.
3. 음수 사이클 유무를 확인한다.
음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다. 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다. 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.
3. 플로이드-워셜 (floyd-warshall)
플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
플로이드-워셜의 핵심 이론
플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A노드에서 B노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라른 것이다.
색칠된 에지 경로가 1->5최단 경로라면 1->4최단 경로와 4->5최단 경로 역시 색칠된 에지로 이뤄질 수밖에 없다. 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다는 의미가 된다.
1. 리스트를 선언하고 초기화
D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다. S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화한다. 여기에서 S == E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문이다.
2. 최단 거리 리스트에 그래프 데이터 저장
출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E] = W로 에지의 정보를 리스트에 입력한다. 이로써 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.
3. 점화식으로 리스트 업데이트
점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트한다.
플로이드-워셜 알고리즘 로직
4. 최소 신장 트리
최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.
최소 신장 트리의 특징
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개다.
최소 신장 트리의 핵심 이론
1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화
최소 신장트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지 리스트의 형태로 저장한다. 이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 사이클 처리를 위한 유니온 파인드 리스트도 함께 초기화한다. 리스트의 인덱스를 해당 자리의 값으로 초기화하면 된다.
2. 그래프 데이터를 가중치 기준으로 정렬
에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬한다.
3. 가중치가 낮은 에지부터 연결 시도
가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 이때 바로 연결하지 않고 이 에지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union 연산을 이용해 두 노드를 연결한다.
4. 과정 3 반복
전체 노드의 개수가 N개이면 연결한 에지의 개수가 N-1이 될 때까지 과정 3을 반복한다.
5. 총 에지 비용 출력
에지의 개수가 N-1이 되면 알고리즘을 종료하고, 완성된 최소 신장 트리의 총 에지 비용을 출력한다.
5. 다익스트라 vs 최소 신장 트리 (MST)
6. 실전 문제
최단경로 (백준 1753) - 다익스트라
import org.w3c.dom.Node;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node_1753 {
int end;
int weight;
public Node_1753(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
public class P1753_최단경로 {
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 K = Integer.parseInt(br.readLine());
boolean[] visited = new boolean[V + 1];
int[] result = new int[V + 1];
ArrayList<Node_1753>[] al = new ArrayList[V + 1];
for (int i = 1; i <= V; i++) {
al[i] = new ArrayList<>();
result[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
al[u].add(new Node_1753(v, m));
}
PriorityQueue<Node_1753> queue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
result[K] = 0;
queue.add(new Node_1753(K, 0));
while (!queue.isEmpty()) {
Node_1753 now = queue.poll();
if (!visited[now.end]) visited[now.end] = true;
for (int i = 0; i < al[now.end].size(); i++) {
Node_1753 next = al[now.end].get(i);
if (!visited[next.end] && now.weight + next.weight < result[next.end]) {
result[next.end] = now.weight + next.weight;
queue.add(new Node_1753(next.end, result[next.end]));
}
}
}
for (int i = 1; i <= V; i++) {
if (result[i] == Integer.MAX_VALUE) System.out.println("INF");
else System.out.println(result[i]);
}
}
}
타임머신 (백준 11657) - 벨만-포드
import java.io.*;
import java.util.StringTokenizer;
class Node_11657 {
int start;
int end;
int weight;
Node_11657(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}
class P11657_타임머신 {
static int N, M;
static Node_11657[] a;
static long[] len;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
a = new Node_11657[M];
len = new long[N + 1];
for (int i = 1; i <= N; i++) len[i] = Integer.MAX_VALUE;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
a[i] = new Node_11657(u, v, w);
}
if (!bellmanFord(1))
System.out.println(-1);
else {
for (int i = 2; i <= N; i++) {
if (len[i] == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(len[i]);
}
}
}
static boolean bellmanFord(int s) {
len[s] = 0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j < M; j++) {
int start = a[j].start;
int end = a[j].end;
int weight = a[j].weight;
if (len[start] == Integer.MAX_VALUE) continue;
else {
if (len[end] > len[start] + weight) {
len[end] = len[start] + weight;
if (i == N) return false;
}
}
}
}
return true;
}
}
플로이드 (백준 11404) - 플로이드 워셜
import java.io.*;
import java.util.StringTokenizer;
public class P11404_플로이드 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] A = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) A[i][j] = 0;
else A[i][j] = 1000000000;
}
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
A[a][b] = Math.min(A[a][b], c);
}
for (int K = 1; K <= n; K++) {
for (int S = 1; S <= n; S++) {
for (int E = 1; E <= n; E++) {
A[S][E] = Math.min(A[S][E], A[S][K] + A[K][E]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (A[i][j] == 1000000000) bw.write(0 + " ");
else bw.write(A[i][j] + " ");
}
bw.write("\n");
}
bw.close();
}
}
최소 스패닝 트리 (백준 1197) - 최소 신장 트리
import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node_1197 implements Comparable<Node_1197> {
int start;
int end;
int weight;
Node_1197(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public int compareTo(Node_1197 o) {
return this.weight - o.weight;
}
}
public class P1197_최소스패닝트리 {
static int[] index;
static int sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
index = new int[V + 1];
sum = 0;
for (int i = 1; i <= V; i++) index[i] = i;
PriorityQueue<Node_1197> queue = new PriorityQueue<>();
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
queue.add(new Node_1197(u, v, w));
}
while(!queue.isEmpty()) {
Node_1197 Node_1197 = queue.poll();
union(Node_1197.start, Node_1197.end, Node_1197.weight);
}
bw.write(sum + "");
bw.close();
}
public static void union(int a, int b, int c) {
a = find(a);
b = find(b);
if (a != b) {
index[b] = a;
sum += c;
}
}
public static int find(int a) {
if (index[a] == a) return a;
else return index[a] = find(index[a]);
}
}
