다익스트라 (Dijkstra)
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 다음과 같다.
| 기능 | 특징 | 시간 복잡도 (노드 수 : V, 에지 수: E) |
| 출발 노드와 모든 노드 간의 최단 거리 탐색 | 에지는 모든 양수 | O(ElogV) |
특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다.
다익스트라 알고리즘의 핵심 이론
1. 인접 리스트로 그래프 구현하기
인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다. 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결했다.
2. 최단 거리 배열 초기화하기
최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다. 이때 무한은 적당히 큰 값을 사용하면 된다.
3. 값이 가장 작은 노드 고르기
최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다 (한 번 사용한 노드는 다시 사용하지 않으므로, 최단 거리를 구해야 하기 때문에). 여기서는 값이 0인 출발 노드에서 시작한다.
4. 최단 거리 배열 업데이트하기
선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다. 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트한다.
최단 거리 업데이트 방법
Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)
5. 과정 3~4를 반복해 최단 거리 배열 완성하기
모든 노드가 처리될 때까지 과정 3~4를 반복한다. 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성된다.
다익스트라 알고리즘은 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘이고, 에지는 항상 양수여야 한다는 조건이 있다. 많은 사람이 다익스트라 알고리즘이 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이라고 생각하는 경향이 있는데, 실제로 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현한다.
[백준 1753번] 최단경로
https://www.acmicpc.net/problem/1753
1. 인접 리스트에 노드를 저장하고 거리 배열을 0으로 초기화한다.
2. 최초 시작점을 큐에 삽입하고, 다음 과정에 따라 다익스트라 알고리즘을 수행한다.
1. 거리 배열에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다.
2. 해당 노드와 연결된 노드들의 최단 거릿값을 다음 공식을 이용해 업데이트한다.
- Min(선택 노드의 거리 배열 값 + 에지의 가중치, 연결 노드의 거리 배열의 값)
- 거리 배열의 값이 업데이트된 경우 연결 노드를 큐에 삽입
3. 큐가 빌 때까지 1~2 반복
3. 완성된 거리 배열의 값을 출력.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static int V, E, K;
public static int[] distance;
public static boolean[] visited;
public static ArrayList<Edge>[] list;
public static PriorityQueue<Edge> q = new PriorityQueue<Edge>();
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());
distance = new int[V + 1];
visited = new boolean[V + 1];
list = new ArrayList[V + 1];
for (int i = 1; i <= V; i++) {
list[i] = new ArrayList<>();
distance[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 w = Integer.parseInt(st.nextToken());
list[u].add(new Edge(v, w));
}
q.add(new Edge(K, 0)); // K를 시작점으로 설정하기
distance[K] = 0;
while(!q.isEmpty()) {
Edge current = q.poll();
int c_v = current.vertex;
if(visited[c_v]) continue; // 이미 방문한 적이 있는 노드는 다시 큐에 넣지 않음
visited[c_v] = true;
for (int i = 0; i < list[c_v].size(); i++) {
Edge tmp = list[c_v].get(i);
int next = tmp.vertex;
int value = tmp.value;
if(distance[next] > distance[c_v] + value) { // 최소 거리로 업데이트하기
distance[next] = value + distance[c_v];
q.add(new Edge(next, distance[next]));
}
}
}
for (int i = 1; i <= V; i++) { // 거리 배열 출력
if(visited[i]) System.out.println(distance[i]);
else System.out.println("INF");
}
}
static class Edge implements Comparable<Edge> {
int vertex, value;
Edge(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
}
}
여기서는 distance 값이 업데이트된 경우에 우선순위 큐에 추가했는데 그것과 별개로 방문하지 않았다면 그냥 큐에 추가해도 똑같이 정답이 나온다. 시간이 아주 조금 더 걸리긴 한다. 처음에 방문 체크를 하면 더 작은 거리값으로 업데이트가 안되는게 아닌가 생각했는데 어차피 해당 노드와 연결된 노드들의 거리 배열은 전부 (더 작은 값으로) 업데이트가 되고 지금(current) 노드의 방문 여부만을 체크하는 것이기 때문에 상관 없다 (지금 current 노드의 연결 노드를 전부 돌며 최단 거리로 업데이트 하는 경우를 2번 이상 반복할 필요는 없으므로). 방문 여부 체크를 하지 않을 시 메모리 초과가 발생한다.
[백준 1916번] 최소비용 구하기
https://www.acmicpc.net/problem/1916
시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단 거리)를 구하는 문제이다. 또한 버스 비용의 범위가 음수가 아니기 때문에 이 문제는 다익스트라 알고리즘을 이용해 해결할 수 있다.
1. 주어진 예제 데이터를 기반으로 그래프를 그린다. 도시는 노드로, 도시 간 버스 비용은 에지로 나타낸다.
2. 첫째 숫자(도시 개수)의 크기만큼 인접 리스트 배열의 크기를 설정한다. 이때 버스의 비용(가중치)이 존재하므로 인접 리스트 배열의 자료형이 될 클래스를 선언한다. 그리고 둘째 숫자(버스 개수)의 크기만큼 반복문을 돌면서 그래프를 리스트 배열에 저장한다.
3. 다익스트라 알고리즘을 수행한다. 최단 거리 배열이 완성되면 정답을 출력한다.
[정답]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static ArrayList<Node>[] list; // 인접리스트로 그래프 표현하기.
static int[] dist; // 최단거리 배열.
static boolean[] visit; // 사용노드인지 확인하는 배열.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
list = new ArrayList[N + 1];
dist = new int[N + 1];
visit = new boolean[N + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
for (int i = 0; i <= N; i++) {
list[i] = new ArrayList<Node>();
}
for (int i = 0; i < M; i++) { // 주어진 그래프의 간선들을 인접리스트 자료구조에 넣는 부분
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
list[start].add(new Node(end, weight));
}
st = new StringTokenizer(br.readLine());
int startIndex = Integer.parseInt(st.nextToken());
int endIndex = Integer.parseInt(st.nextToken());
// 다익스트라 알고리즘 수행
bw.write(dijkstra(startIndex, endIndex) + "\n");
bw.flush();
bw.close();
br.close();
}
public static int dijkstra(int start, int end) { // 다익스트라 알고리즘
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Node nowNode = pq.poll();
int now = nowNode.targetNode;
if (!visit[now]) {
visit[now] = true;
for (Node n : list[now]) { // 선택노드 + 비용 < 타켓노드인 경우 값을 갱신하는 부분
if (dist[n.targetNode] > dist[now] + n.value) {
dist[n.targetNode] = dist[now] + n.value;
pq.add(new Node(n.targetNode, dist[n.targetNode]));
}
}
}
}
return dist[end];
}
}
class Node implements Comparable<Node> {
int targetNode;
int value;
Node(int targetNode, int value) {
this.targetNode = targetNode;
this.value = value;
}
@Override
public int compareTo(Node o) {
return value - o.value;
}
}현재 사용할 수 있는 노드를 우선순위 큐 자료구조에 넣은 이유
이 문제에서 현재 사용할 수 있는 노드들을 우선순위 큐에 넣은 이유는 현재 연결된 노드 중 가장 적은 비용을 지니고 있는 노드를 빠르고 간편하게 찾을 수 있기 때문이다. 우선순위 큐는 데이터가 새롭게 들어올 때마다 자동으로 정렬한다. 정렬 기준은 Node 클래스에서 적절한 compareTo() 함수를 이용해 설정할 수 있다.
[백준 1854번] K번째 최단경로 찾기
https://www.acmicpc.net/problem/1854
K번째 최단 경로 해결 방법
- 최단 경로를 표현하는 배열을 우선순위 큐 배열(크기는 K)로 변경. 이렇게 하면 최단 경로뿐 아니라 최단 경로 ~ K 번째 최단 경로까지 표현 가능.
- 방문 확인 배열은 필요 없음. K번째 경로를 찾기 위해서는 노드를 여러 번 쓰는 경우가 생기기 때문.
1. 도시는 노드로, 도로는 에지로 표현.
2. 변수를 선언하고, 그래프 데이터를 받는 부분은 모두 다익스트라 알고리즘 준비 과정과 동일하다.
3. 최단 거리 배열을 우선순위 큐 배열로 선언하고, 다음과 같은 기준을 세워 채워야 한다. (예제에서 주어진 K는 2지만 여기서는 이해를 돕기 위해 3으로 진행한다.)
최단 거리 배열 채우기 규칙
- 현재 노드에 저장된 경로가 K개 미만일 때 신규 경로를 추가한다.
- 경로가 K개일 때 현재 경로 중 최대 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 업데이트한다. 우선순위 큐를 사용하면 이 로직을 쉽게 구현할 수 있다.
- K번째 경로를 찾기 위해서는 노드를 여러 번 쓰는 경우가 생기므로 사용한 노드는 방문 배열에 확인해 두고 재사용하지 않는 부분은 삭제한다.
4. 최단 거리 배열을 탐색하면서 K번째 경로가 존재하면 출력하고, 존재하지 않으면 -1을 출력한다.
우선순위 큐로 선언하면 편리한 점
이 부분에서 최단 거리 배열의 객체 형식을 우선순위 큐로 선언했기 때문에 새로운 노드가 삽입됐을 때 별도의 정렬을 해주지 않아도 자동으로 정렬돼 편리하게 구현할 수 있다.
참고
https://goodbyeanma.tistory.com/66
백준 1854번 - K번째 최단경로 찾기
https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와,
goodbyeanma.tistory.com
[정답]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
PriorityQueue<Integer>[] distQueue = new PriorityQueue[N + 1];
Comparator<Integer> cp = new Comparator<Integer>() { // 내림차순 정렬 기준 설정
@Override
public int compare(Integer o1, Integer o2) {
return o1 < o2 ? 1 : -1;
}
};
for (int i = 0; i < N + 1; i++) {
distQueue[i] = new PriorityQueue<>(K, cp);
}
int[][] W = new int[1001][1001];
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());
W[a][b] = c;
}
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(1, 0));
distQueue[1].add(0);
while(!pq.isEmpty()) {
Node u = pq.poll();
for (int adjNode = 1; adjNode <= N; adjNode++) {
// 연결된 모든 노드로 검색하기 (시간 복잡도 측면에서 인접 행렬이 불리한 이유)
if (W[u.node][adjNode] != 0) {
// 저장된 경로가 K개가 안 될 때는 그냥 추가하기
if(distQueue[adjNode].size() < K) {
distQueue[adjNode].add(u.cost + W[u.node][adjNode]);
pq.add(new Node(adjNode, u.cost + W[u.node][adjNode]));
}
// 저장된 경로가 K개이고, 현재 가장 큰 값보다 작을 때만 추가하기
else if(distQueue[adjNode].peek() > u.cost + W[u.node][adjNode]) {
distQueue[adjNode].poll(); // 기존 큐에서 Max값 먼저 삭제해야 함
distQueue[adjNode].add(u.cost + W[u.node][adjNode]);
pq.add(new Node(adjNode, u.cost + W[u.node][adjNode]));
}
}
}
}
for (int i = 1; i <= N; i++) { // K번째 경로 출력하기
if(distQueue[i].size() == K)
bw.write(distQueue[i].peek() + "\n");
else
bw.write(-1 + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
class Node implements Comparable<Node> {
int node;
int cost;
public Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return cost - o.cost;
}
}
[참고 자료]
- Do it! 알고리즘 코딩 테스트 자바편
