# BOJ01753 최단경로
https://www.acmicpc.net/problem/1753 (opens new window)
# 다익스트라 최단 경로 알고리즘
다익스트라 Dijkstra 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
# 특징
'음의 간선'이 없을 때 동작한다. 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.그리디 알고리즘으로 분류된다. 매번'가장 비용이 적은 노드'를선택해서 임의의 과정을 반복하기 때문이다.- 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상
1차원 리스트에 저장하며 리스트를 계속갱신한다는 특징이 있다. - 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것이다.
# 원리
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3, 4번을 반복한다.
# 문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구한다. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
아래는 시작 노드 번호가 주어지면 최단 경로를 저장하기 위핸 배열 d에 최단 경로를 채워넣기 위한 dijkstra 메소드이다.
가장 짧은 경로가 먼저 나오도록 우선순위를 설정한다.
PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
if (o1.distance < o2.distance) {
return -1;
} else if (o1.distance == o2.distance) {
return 0;
}
return 1;
});
시작점에서 시작점 까지의 거리는 0이므로 d[start] = 0으로 설정한다.
우선순위 큐에 시작점을 넣고 최단 경로를 탐색한다.
private static void dijkstra(int start) {
PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
if (o1.distance < o2.distance) {
return -1;
} else if (o1.distance == o2.distance) {
return 0;
}
return 1;
});
d[start] = 0;
priorityQueue.offer(new Node(start, 0));
while (!priorityQueue.isEmpty()) {
Node node = priorityQueue.poll();
int index = node.index;
int distance = node.distance;
if (d[index] < distance) {
continue;
}
for (int i = 0; i < graph.get(index).size(); i++) {
int cost = d[index] + graph.get(index).get(i).distance;
if (cost < d[graph.get(index).get(i).index]) {
d[graph.get(index).get(i).index] = cost;
priorityQueue.offer(new Node(graph.get(index).get(i).index, cost));
}
}
}
}
문제에서 요구하는 답은 시작점을 기준으로 차례대로 최단 경로 값을 출력하는 것이다.
dijkstra에서 완성된 최단 경로 배열을 반복하여 돌며 적절히 값을 출력한다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class BOJ1753 {
public static final int INF = Integer.MAX_VALUE;
private static final List<List<Node>> graph = new ArrayList<>();
private static int[] d; // 최단 경로 명시를 위한 테이븖
private static class Node {
private final int index;
private final int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
}
private static void dijkstra(int start) {
PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
if (o1.distance < o2.distance) {
return -1;
} else if (o1.distance == o2.distance) {
return 0;
}
return 1;
});
d[start] = 0;
priorityQueue.offer(new Node(start, 0));
while (!priorityQueue.isEmpty()) {
Node node = priorityQueue.poll();
int index = node.index;
int distance = node.distance;
if (d[index] < distance) {
continue;
}
for (int i = 0; i < graph.get(index).size(); i++) {
int cost = d[index] + graph.get(index).get(i).distance;
if (cost < d[graph.get(index).get(i).index]) {
d[graph.get(index).get(i).index] = cost;
priorityQueue.offer(new Node(graph.get(index).get(i).index, cost));
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt(); // 정점의 개수
int e = scanner.nextInt(); // 간선의 개수
int k = scanner.nextInt();
for (int i = 0; i <= v; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < e; i++) {
int a = scanner.nextInt(); // start
int b = scanner.nextInt(); // end
int c = scanner.nextInt(); // weight
graph.get(a).add(new Node(b, c));
}
d = new int[v + 1];
Arrays.fill(d, INF);
dijkstra(k);
StringBuilder stringBuilder = new StringBuilder();
for (int i = 1; i <= v; i++) {
if (d[i] == INF) {
stringBuilder.append("INF\n");
} else {
stringBuilder.append(d[i]).append("\n");
}
}
System.out.println(stringBuilder);
}
}