다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 아래와 같습니다.
| 기능 | 특징 | 시간 복잡도 (V: 노드 수, E: 에지 수) |
| 출발 노드와 모든 노드 간의 최단 거리 탐색 | 에지는 모두 양수여야 함. | O(ElogV) |
다익스트라 최단 경로 알고리즘은 기본적으로 '그리디 알고리즘'으로 분류됩니다.
매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문입니다.
다익스트라 알고리즘 핵심 이론
아래 5 단계로 설명됩니다.
1. 인접 리스트로 그래프 구현
그래프가 위와 같을 때 인접리스트가 표현됩니다. 물론 그래프를 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N 의 크기가 클 것을 대비해서 보통 인접 리스트로 구현됩니다.
2. 최단 거리 배열 초기화
최단 거리 배열을 만들고 출발노드는 0, 이외의 노드는 무한 ∞ 으로 초기화합니다. 이 때 무한은 적당히 큰 값을 사용하면 됩니다.
여기서는 출발 노드를 노드 1로 설정했습니다.
3. 값이 가장 작은 노드 고르기
방문하지 않은 노드 중, 최단 거리 배열에서 현재 값이 가장 작은 노드를 고릅니다. 여기서는 값이 0인 출발 노드에서 시작합니다.
값이 가장 작은 노드를 고르면 그 노드는 방문 체크됩니다.
4. 최단 거리 배열 업데이트
선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트합니다.
연결 노드의 최단 거리는 아래처럼 두 값 중에서 더 작은 값으로 업데이트합니다.
Math.min(선택 노드의 최단 거리 배열 값(D[현재 노드]) + 에지 가중치 , 연결 노드의 최단 거리 배열 값(D[연결 노드]) )
5. 과정 3~4 를 반복해서 최단 거리 배열 완성
과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어서 처리하고 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성됩니다.
노드 1은 이미 방문했고 최단 거리 배열 중에서 가장 짧은 거리인 노드는 3이다. 그러므로 3번 노드를 선택하는 것을 시작으로 같은 동작을 반복합니다.
최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장해서 리스트를 항상 갱신한다는 특징이 있습니다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인합니다. 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 해당 짧은 경로로 업데이트합니다.
즉, '방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인하는 그리디 알고리즘' 이라고 할 수 있습니다.
다익스트라 알고리즘은 출발 노드와 그 외 노드 간의 최단 거리를 구하는 알고리즘이고, 에지는 항상 양수여야 한다는 제약 조건이 있습니다. 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현합니다.
다익스트라 알고리즘과 우선순위 큐
기존에는 하나의 노드를 방문하고 나서 다음 노드를 방문할 때 가장 최단 거리가 짧은 노드 (D[N] 이 가장 작은 노드) 을 선택했습니다. 이 때 우선순위 큐를 사용할 수 있습니다. 크게 어렵지 않으니 아래 그림을 살펴봅시다.
1. 초기에는 똑같이 그래프, 최단 거리 배열을 만들어 줍니다. 이 때 우선순위 큐를 만듭니다. 우선순위 큐의 정렬 기준은 '거리' 을 기준으로 오름차순으로 만듭니다.
2. 우선순위 큐에서 poll 한 노드를 현재 노드 cur 이라고 합시다. cur 의 인접 노드를 조사하고 최단 거리 배열 D[N] 을 업데이트 해줍니다. 그리고 출발 노드에서 인접 노드로 갈 때의 최단 거리를 우선순위 큐에 넣습니다.
우선순위 큐에서 poll 한 노드는 방문함으로 체크됩니다.
(3, 3) 이 (2, 8) 보다 거리가 더 짧으므로 우선순위 큐에서 더 우선으로 정렬됩니다.
3. 위 2번의 과정을 반복합니다.
위 그림에서 주목할 점은 우선순위 큐에 (4, 12) 와 (4, 16), 그리고 (5,14) 와 (5,23) 처럼 같은 노드가 우선순위 큐에 들어갈 수 있다는 점입니다. 하지만 상관없습니다. 왜냐하면 우선순위 큐에는 노드에 상관없이 가장 거리가 작은 값부터 정렬되고, 우선순위 큐에서 poll 한 노드는 방문함 체크가 되어서 다시 같은 노드를 poll 하더라도 무시되기 때문입니다.
이렇게 우선순위 큐를 다익스트라 알고리즘에 사용하면 최단 거리가 가장 작은 노드를 선택할 때의 시간 복잡도를 줄일 수 있어 효율적입니다.
이제 문제를 풀어봅시다.
백준 1753 최단경로
https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
1. 문제 분석
시작점과 다른 노드와 관련된 최단 거리를 구하는 문제입니다. 다익스트라 알고리즘의 가장 기본적인 형태입니다. 앞서 배운 다익스트라 알고리즘을 우선순위 큐를 이용해서 풀면 됩니다.
2. 손으로 풀기
1. 인접 리스트에 노드를 저장하고 거리 배열을 초기화합니다. 거리 배열은 출발 노드는 0, 나머지 노드는 ∞ (충분히 큰 값) 으로 초기화합니다.
2. 최초 시작점을 큐에 삽입하고, 아래 과정에 따라 다익스트라 알고리즘을 수행합니다.
a. 거리 배열에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택합니다. 이것은 우선순위 큐에서 poll 하는 것으로 구현합니다. poll 한 노드는 방문함으로 체크합니다..
b. 해당 노드와 연결된 노드들의 최단 거리값을 업데이트합니다.
[연결 노드 거리 리스트 값] 보다 [선택 노드의 거리 리스트 값 + 에지 가중치] 가 더 작으면 업데이트 수행
업데이트가 수행되는 경우 연결노드를 우선순위 큐에 삽입.
c. 큐가 빌 때까지 1 ~ 2 을 반복합니다.
퍄랸 글씨로 표시한 것처럼 최단 거리 배열이 업데이트되지 않는 경우에는 우선순위 큐에 노드를 삽입하지 않습니다.
3. 완성된 거리 배열의 값을 출력합니다.
3. 슈도코드
V: 노드 개수, E: 에지 개수
K: 출발 노드
graph: 인접 리스트 dist: 최단 거리 배열 visited 방문배열
queue: 우선순위 큐. 거리 우선 정렬
for(V){ dist 을 ∞ 로 초기화 }
dist[K] = 0;
for(E) { 그래프 에지 데이터 설정 }
queue 에 시작 노드 넣기 (K, 0)
while(큐가 빌 때까지){
int cur = 큐에서 poll
만약 cur 이 이미 방문했으면 -> 큐의 다음 노드로 넘어감.
아니면 -> cur 방문함 체크.
for(cur 의 인접 노드 adjNode 에 대해){
만약 (dist[cur] + 에지 가중치 < dist[인접 노드]) 이면
dist 업데이트, 큐에 offer
}
}
dist 출력. 만약 배열값이 ∞ 이면 INF 출력.
static class Node implements Comparable{
nodeNum. weight
거리 우선으로 정렬 기준 설정.
}
4. 코드
public class BaekJun1753Self {
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());
ArrayList<Node>[] graph = new ArrayList[V + 1];
boolean[] visited = new boolean[V + 1];
int[] dist = new int[V + 1];
PriorityQueue<Node> queue = new PriorityQueue<>();
for (int i = 1; i <= V; i++) {
dist[i] = 99_999_999;
graph[i] = new ArrayList<>();
}
dist[K] = 0;
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());
graph[u].add(new Node(v, w));
}
queue.offer(new Node(K, 0));
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNode = cur.nodeNum;
if (visited[curNode]) {
continue;
}
visited[curNode] = true;
for (Node adjNode : graph[curNode]) {
int next = dist[curNode] + adjNode.weight;
if (next < dist[adjNode.nodeNum]) {
dist[adjNode.nodeNum] = next;
queue.offer(new Node(adjNode.nodeNum, dist[adjNode.nodeNum]));
}
}
}
for (int i = 1; i <= V; i++) {
if (visited[i]) {
System.out.println(distance[i]);
} else {
System.out.println("INF");
}
}
}
static class Node implements Comparable<Node>{
int nodeNum;
int weight;
public Node(int nodeNum, int weight) {
this.nodeNum = nodeNum;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
}
백준 1916 최소비용 구하기
https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
1. 문제 분석
시작점과 도착점이 주어지고 이 목적지까지 가는 최소 비용을 구하는 문제입니다. 버스의 비용의 범위가 음수가 아니기 때문에 다익스트라 알고리즘을 이용해서 문제를 해결할 수 있습니다. 이전 문제 백준 1753 과 매우 흡사하게 풀면 됩니다.
2. 손으로 풀기
이전 문제와 비슷하므로 간단히 설명하겠습니다.
3. 슈도코드
N: 도시(노드) 개수, M: 버스(에지) 개수
graph: 인접 리스트
dist[N+1]: 최단 거리 배열
visited[N+1]: 방문 배열
queue: PriorityQueue<Node>
그래프 초기화
dist 을 ∞ 로 초기화
for(M){ graph 에지 입력받기 }
start: 출발 도시, arrival: 도착도시
dist[start] = 0
큐에 시작 노드(start, 0) 입력받기
while(큐가 빌 때까지)
Node cur = 큐에서 poll
만약 cur 이 도착 노드라면 break;
만약 cur 가 이미 방문했으면 큐에 다음 것으로 넘어가기
아니라면 방문함 표시
for( cur 의 인접 노드 adjNode 에 대해서){
만약 cur 에서 adjNode 로 가는 것이 기존 dist[adjNode] 보다 작으면
dist 을 업데이트
큐에 인접 노드와 업데이트된 값을 노드로 해서 넣기
}
}
}
dist[도착도시] 출력
static class Node implements Comparable<Node>{
nodeNum, weight
weight 오름차순으로 정렬
}4. 코드
public class BaekJun1916 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
ArrayList<Node>[] graph = new ArrayList[N + 1];
PriorityQueue<Node> queue = new PriorityQueue<>();
int[] dist = new int[N + 1];
boolean[] visited = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
dist[i] = 999_999_999;
}
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());
graph[u].add(new Node(v, w));
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int arrival = Integer.parseInt(st.nextToken());
dist[start] = 0;
queue.offer(new Node(start, 0));
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNode = cur.nodeNum;
if (curNode == arrival) {
break;
}
if (visited[curNode]) {
continue;
}
visited[curNode] = true;
for (Node adjNode : graph[curNode]) {
int next = dist[curNode] + adjNode.weight;
if (dist[adjNode.nodeNum] > next) {
dist[adjNode.nodeNum] = next;
queue.offer(new Node(adjNode.nodeNum, next));
}
}
}
System.out.println(dist[arrival]);
}
static class Node implements Comparable<Node> {
int nodeNum;
int weight;
public Node(int nodeNum, int weight) {
this.nodeNum = nodeNum;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
}
백준 1854 K번째 최단경로 찾기
https://www.acmicpc.net/problem/1854
1854번: K번째 최단경로 찾기
첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이
www.acmicpc.net
1. 문제 분석
시작점과 도착점이 주어지고 이 목적지까지 가는 K 번째 최단 경로를 구하는 문제입니다.
노드(도시) 개수는 최대 1,000 개, 에지(도로) 개수는 최대 2,000,000 개입니다. 시간 제한은 2초이므로 다익스트라 알고리즘으로 풀어봅시다.
K 번째 최단 경로를 찾는 핵심 방법은 아래와 같습니다.
최단 경로를 표현하는 배열을 우선순위 큐 배열(크기는 K) 로 변경해서 최단 경로뿐 아니라
최단 경로 ~ K 번째 최단 경로까지 표현하도록 함.
2. 손으로 풀기
1. 그래프와 최단 거리 배열을 만듭니다.
2. 최단 거리 배열을 우선순위 큐 배열로 선언하고 각 우선순위 큐는 내림차순으로 정렬되도록 합니다.
최단 거리 배열 채우기 규칙
a. 현재 노드에 저장된 경로가 K 개 미만일 때 신규 경로를 추가.
b. 경로가 K 개 일 때 현재 경로 중 최대 경로와 신규 경로를 비교해서 신규 경로가 더 작을 때 업데이트. (우선순위 큐를 이용)
3. 최단 거리 배열을 탐색하면서 K 번째 경로가 존재하면 출력하고, 존재하지 않으면 -1 을 출력합니다.
3. 슈도코드
n: 도시(노드), m: 도로(에지), k
graph: 인접 그래프
dist: 최단 거리 배열 각 원소는 크기가 k 인 우선순위 큐.
각 우선순위 큐는 내림차순임.
queue: 노드 방문할 때의 우선순위 큐.
그래프 초기화, dist 배열 준비
그래프 에지 정보 설정
// 다익스트라 알고리즘
출발 노드를 우선순위 큐에 넣기
dist 배열에 출발 노드 관련해서 넣기
while(큐가 빌 때까지){
cur: 큐에서 poll 한 현재 노드
for(현재 노드에 대한 인접 노드들에 대해서 ){
if(dist 의 원소(우선순위 큐)가 공간이 있으면, 즉, dist[인접노드].size < k 이면 ){
dist 배열에 거리 정보 삽입
queue 에 선택 노드 추가
}else if( dist 의 인접노드에서 가장 큰 값(poll 한 값) > 현재 가중치 + 두 노드 사이의 에지 가중치) {
해당 노드에 최단 거리 큐에 마지막 값 삭제
신규 값 삽입
queue 에 이 Edge 추가
}
}
}
// 출력
for( 1 ~ n){
dist[i] 의 크기가 k 이면 dist[i].peek 값 출력
아니면 -1 출력
}
static class Edge {
node, weight
weight 을 기준으로 오름차순 정렬
}
4. 코드
public class BaekJun1854Sec {
static int n, m, k;
static ArrayList<Edge>[] graph;
static PriorityQueue<Integer>[] dist;
static PriorityQueue<Edge> queue;
public static void main(String[] args) throws IOException {
input();
// dijkstra
dijkstraFunc(k, graph, dist, queue);
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
graph = new ArrayList[n + 1];
dist = new PriorityQueue[n + 1];
queue = new PriorityQueue<>();
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
dist[i] = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
}
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());
graph[a].add(new Edge(b, c));
}
br.close();
}
private static void dijkstraFunc(int k, ArrayList<Edge>[] graph, PriorityQueue<Integer>[] dist, PriorityQueue<Edge> queue) {
queue.offer(new Edge(1, 0));
dist[1].add(0);
while (!queue.isEmpty()) {
Edge cur = queue.poll();
int curNode = cur.node;
for (Edge adjEdge : graph[curNode]) {
int adjNode = adjEdge.node;
int adjWeight = adjEdge.weight;
int nextWeight = cur.weight + adjWeight;
if (dist[adjEdge.node].size() < k) {
dist[adjEdge.node].offer(nextWeight);
queue.add(new Edge(adjNode, nextWeight));
} else if (dist[adjEdge.node].peek() > nextWeight) {
dist[adjEdge.node].poll();
dist[adjEdge.node].offer(nextWeight);
queue.add(new Edge(adjNode, nextWeight));
}
}
}
}
private static void output() {
for (int i = 1; i <= n; i++) {
if (dist[i].size() == k) {
System.out.println(dist[i].peek());
} else {
System.out.println("-1");
}
}
}
static class Edge implements Comparable<Edge> {
int node;
int weight;
public Edge(int node, int weight) {
this.node = node;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
}
'Java > 코딩테스트' 카테고리의 다른 글
| 플로이드-워셜 알고리즘 자바 백준 BOJ 11404, 11403 (1) | 2023.08.21 |
|---|---|
| 벨만 포드 알고리즘 자바 백준 BOJ 11657, 1219 (0) | 2023.08.18 |
| 위상정렬 자바 백준 BOJ 2252, 1516, 1948 (0) | 2023.08.07 |
| 유니온 파인드 자바 백준 BOJ 1717, 1976, 1043 (0) | 2023.08.05 |
| 그래프 표현-2 자바 백준 BOJ 1707, 2251 (0) | 2023.08.05 |