다익스트라란?
•
다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다.
◦
가능한 적은 비용으로, 가장 빠르게 도달하는 경로를 찾아내는 문제에 활용한다.
•
이때 그래프는 음의 간선, 음의값이 없어야 한다.
◦
만약 음의 가중치를 가지며, 가중치의 합이 음인 사이클이 존재하지 않는 경우에는 벨만-포드 알고리즘을 사용한다.
•
BFS 와 DP 를 사용하여 구현한다.
백준 1916 최소 비용 구하기
전형적인 다익스트라 문제이다. 처음에 다익스트라가 뭔지 모르고 BFS 로 풀었는데, 메모리 초과가 떴다. 아래는 그 당시 코드이다.
import java.io.*;
import java.util.*;
public class PROB1916 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
static Queue<int[]> queue = new LinkedList<>();
static int N;
static int M;
static int startNode;
static int endNode;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
init();
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 c = Integer.parseInt(st.nextToken());
graph.get(u).add(new int[]{v, c});
}
st = new StringTokenizer(br.readLine());
startNode = Integer.parseInt(st.nextToken());
endNode = Integer.parseInt(st.nextToken());
bfs();
System.out.println(min);
}
public static void init() {
for (int i = 0; i < N + 1; i++) {
graph.add(new ArrayList<>());
}
}
public static void bfs() {
queue.add(new int[]{startNode, 0});
while (!queue.isEmpty()) {
int[] current = queue.poll();
int node = current[0];
int cost = current[1];
if (node == endNode) {
min = Math.min(min, cost);
}
for (int[] next : graph.get(node)) {
int nextNode = next[0];
int nextCost = next[1];
queue.add(new int[]{nextNode, cost + nextCost});
}
}
}
}
Java
복사
위와같이 코드를 작성하면 모든 경로를 탐색하기 때문에 메모리 사용량이 급증한다.
때문에 가중치가 있는 그래프에서 최단경로를 찾을 때에는 다익스트라 알고리즘을 사용하는 것이 좋다. 다익스트라의 경우 위의 코드와 달리 우선순위 큐를 사용하기 때문에 더 효율적으로 최단경로를 찾을 수 있다. 또한 각 노드를 한번만 확정적으로 방문하기 때문에 메모리 초과의 원인을 줄일 수 있다. 확정적으로 방문한다는것이 무슨소리인가? 
아래 gif 를 보면 쉽게 이해할 수 있다.
아래 gif 를 보면 쉽게 이해할 수 있다.
처음 A 에서 E 와 B 와 C 로 갈 수 있다. 하지만 우선순위 큐에서 나온 값은 C 일 것이다. cost 가 가장 적게 들기 때문이다. 해당 cost 를 C 에 넣어주고, 다음 시작점은 C 로 한다. C 에서는 B 와 D 로 갈 수 있다. 이때 B 로 가는 것의 cost 가 더 적으므로 B 로 이동하게 될 것이다. 이런식으로 우선순위 큐에 의해 확정적으로 방문한다. 위의 내용을 반영하여 수정한 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class PROB1916 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
static PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
static int[] distances;
static boolean[] visited;
static int N;
static int M;
static int startNode;
static int endNode;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
init();
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 c = Integer.parseInt(st.nextToken());
graph.get(u).add(new int[]{v, c});
}
st = new StringTokenizer(br.readLine());
startNode = Integer.parseInt(st.nextToken());
endNode = Integer.parseInt(st.nextToken());
dijkstra();
System.out.println(distances[endNode]);
}
public static void init() {
for (int i = 0; i < N + 1; i++) {
graph.add(new ArrayList<>());
}
visited = new boolean[N + 1];
distances = new int[N + 1];
Arrays.fill(distances, Integer.MAX_VALUE);
}
public static void dijkstra() {
distances[startNode] = 0;
pq.add(new int[]{startNode, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0];
int cost = current[1];
if (visited[node]) continue;
visited[node] = true; // 방문처리
for (int[] next : graph.get(node)) {
int nextNode = next[0];
int nextCost = next[1];
if (distances[nextNode] > cost + nextCost) {
distances[nextNode] = cost + nextCost; // 최솟값 갱신
pq.add(new int[]{nextNode, distances[nextNode]});
}
}
}
}
}
Java
복사
달라진 점은 아래와 같다.
•
queue → priority queue
•
방문한 노드 방문 처리
•
방문한 노드의 cost 값 갱신