Problem Solving/Algorithm
[알고리즘] 최소 비용의 경로를 찾는 다익스트라 알고리즘
se0m
2021. 6. 7. 01:23
최단 경로 문제
최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제
가중치 그래프 (Weighted Graph)에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적
최단 경로 문제 종류
1. 단일 출발 및 단일 도착(single-source and single-destination shortest path problem) 최단 경로 문제
그래프 내의 특정 노드 `u`에서 출발해서 또 다른 특정 노드 `v`에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발(single-source shortest path problem) 최단 경로 문제
그래프 내의 특정 노드 `u`와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제(다익스트라 알고리즘)
3. 전체 쌍(all-pair) 최단 경로
그래프 내의 모든 노드 쌍 `(u, v)`에 대한 최단 경로를 찾는 문제
다익스트라 알고리즘
첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며 최단 거리를 갱신하는 기법
- 다익스트라 알고리즘은 너비우선탐색(BFS)과 유사
- 첫 정점부터 각 노드 간의 노드 간의 거리를 저장하는 1차원 배열을 만든 후
- 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서
- 첫 정점부터 해당 노드 간의 가장 짧은 거리를 해당 배열에 업데이트
- 우선순위 큐를 활용한 다익스트라 알고리즘
- 우선순위 큐는 MinHeap 방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
- 1) 첫 정점을 기준으로 배열을 선언하여 첫 번째 정점에서 각 정점까지의 거리를 저장
- 초기에는 첫 정점의 거리는 `0`, 나머지는 무한대로 저장함 (`inf`라고 표현함)
- 우선순위 큐에 `(첫 번째 정점, 0)`만 먼저 넣음
- 2) 우선순위 큐에서 노드를 꺼냄
- 처음에는 첫번째 정점만 저장되어 있으므로 첫 번째 정점이 꺼내짐
- 첫 정점에 인접한 노드들 각각에 대해 첫 번째 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 번째 정점에서 각 정점까지의 거리를 비교한다.
- 배열에 저장되어 있는 거리보다 첫번째 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다. (즉 다이렉트로 가기 🆚 거쳐서 가기 비교)
- 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
- 결과적으로 너비 우선 탐색 방식과 유사하게 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
- 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 `(노드, 거리)` 루트를 발견했을 경우에는 해당 노드와 인접한 노드 간의 거리 계산을 하지 않음
- 3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복
우선순위 큐를 활용한 다익스트라 알고리즘
- 우선순위 큐는 MinHeap 방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
1 단계: 초기화
첫 번째 정점을 기준으로 배열을 선언하여 첫 번째 정점에서 각 정점까지의 거리를 저장
- 초기에는 첫 번째 정점의 거리는 `0`, 나머지는 무한대로 저장함 (`inf`라고 표현함)
- 우선순위 큐에 `(첫 번째 정점, 0)`을 먼저 넣음
2 단계: 우선순위 큐에 추출한 `(A, 0)`을 기반으로 인접한 노드와의 거리 계산
우선순위 큐에서 노드를 꺼냄
- 처음에는 첫 번째 정점만 저장되어 있으므로 첫 번째 정점이 꺼내짐
- 첫 번째 정점에 인접한 노드들 각각에 대해 첫 번째 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 번째 정점에서 각 정점까지의 거리를 비교한다.
- 배열에 저장되어 있는 거리보다 첫 번째 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다. (최소 힙)
- 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
- 결과적으로 너비 우선 탐색 방식과 유사하게 첫 번째 정점에 인접한 노드들을 순차적으로 방문하게 됨
- 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리(루트)를 가진 `(노드, 거리)`의 경우에는 해당 노드와 인접한 노드 간의 거리 계산을 하지 않음
이전 표에서 보이듯이 첫 번째 정점 이외에 모두 `inf`였었으므로
첫 번째 정점에 인접한 노드들은 모두 우선순위 큐에 들어가고 첫 번째 정점과 인접한 노드 간의 거리가 배열에 업데이트됨
3 단계: 우선순위 큐에 추출한 `(C, 1)`을 기반으로 인접한 노드와의 거리 계산
- 우선순위 큐가 MinHeap(최소 힙) 방식이므로 위 표에서 넣어진 `(C, 1)`, `(D, 2)`, `(B, 8)` 중 `(C, 1)`이 먼저 추출됨 (pop)
- 위 표에서 보듯이 1단계까지의 [A → B] 최단 거리는 8인 상황임
- [A → C]의 거리는 1, C에 인접한 B, D에서 [C → B]는 5, 즉 [A → C → B]는 1 + 5 = 6 이므로, A → B 최단 거리 8보다 더 작은 거리를 발견, 이를 배열에 업데이트
- 배열에 업데이트했으므로 `(B, 6)`, 즉 A에서 B까지의 현재까지 발견한 최단 거리 값이 우선순위 큐에 넣어짐
- [C → D]의 거리는 2, 즉 [A → C → D]는 1 + 2 = 3 이므로 [A → D]의 현재 최단 거리인 2 보다 긴 거리이므로 D의 거리는 업데이트되지 않음
4 단계: 우선순위 큐에 추출한 `(D, 2)`을 기반으로 인접한 노드와의 거리 계산
- 지금까지 접근하지 못했던 E와 F 거리가 계산됨
- [A → D]의 거리인 2에 [D → E]가 3 이므로 이를 더해서 `(E, 5)`
- [A → D]의 거리인 2에 [D → F]가 5 이므로 이를 더해서 `(F, 7)`
5 단계: 우선순위 큐에 추출한 `(E, 5)`을 기반으로 인접한 노드와의 거리 계산
- [A → E]의 거리가 5인 상태에서 E에 인접한 F를 가는 거리는 1, 즉 [A → E → F]의 거리는 5 + 1 = 6, 현재 배열에 [A → F]의 최단거리가 7로 기록되어 있으므로 `(F, 6)`으로 업데이트
- 우선순위 큐에 `(F, 6)` 추가
6 단계: 우선순위 큐에 추출한 `(B, 6)`, `(F, 6)`을 순차적으로 추출해 각 노드 기반으로 인접한 노드와의 거리 계산
- 예제의 방향 그래프에서 B 노드는 다른 노드로 가는 루트가 없음
- F 노드는 A 노드로 가는 루트가 있으나 현재 [A → A]가 0 인 반면에 [A → F → A]는 6 + 5 = 11, 즉 더 긴 거리이므로 업데이트되지 않음
7 단계: 우선순위 큐에 추출한 `(F, 7)`, `(B, 8)`을 순차적으로 추출해 각 노드 기반으로 인접한 노드와의 거리 계산
- [A → F]로 가는 하나의 루트의 거리가 7 인 상황이나 배열에서 이미 [A → F]로 가는 현재의 최단 거리가 6인 루트의 값이 있는 상황이므로 더 긴 거리인 `(F, 7)` 루트 기반 인접 노드까지의 거리는 계산할 필요가 없음 그래서 계산 없이 스킵함
- 계산하더라도 [A → F] 거리가 6인 루트보다 무조건 더 긴 거리가 나올 수밖에 없음
- B, 8 도 현재 [A → B] 거리가 6이므로 인접 노드 거리 계산이 필요 없음
※ 우선순위 큐를 사용하면 불필요한 계산 과정을 줄일 수 있음
▶지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산
▶더 긴 거리로 계산된 루트에 대해서는 계산을 스킵할 수 있음
다익스트라 알고리즘 Java 구현
1) 인접 리스트 기반으로 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Dijkstra_AdjList_PQ {
// 우선순위 큐에 사용할 노드 정의 (거리 기준 정렬)
static class Node implements Comparable<Node> {
int vertex;
int distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.distance, other.distance);
}
}
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int V = Integer.parseInt(st.nextToken()); // 정점 개수
int E = Integer.parseInt(st.nextToken()); // 간선 개수
st = new StringTokenizer(in.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
// 인접 리스트 초기화
List<Node>[] adjList = new ArrayList[V];
for (int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
// 간선 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(in.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int distance = Integer.parseInt(st.nextToken());
adjList[from].add(new Node(to, distance));
}
// 다익스트라 초기화
int[] distance = new int[V];
Arrays.fill(distance, INF);
boolean[] visited = new boolean[V];
PriorityQueue<Node> pq = new PriorityQueue<>();
distance[start] = 0;
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
if (visited[current.vertex]) continue;
visited[current.vertex] = true;
for (Node neighbor : adjList[current.vertex]) {
if (!visited[neighbor.vertex] && distance[neighbor.vertex] > distance[current.vertex] + neighbor.distance) {
distance[neighbor.vertex] = distance[current.vertex] + neighbor.distance;
pq.offer(new Node(neighbor.vertex, distance[neighbor.vertex]));
}
}
}
// 결과 출력
System.out.println(distance[end] != INF ? distance[end] : -1);
}
}2) 인접 행렬 기반으로 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Dijkstra_AdjMatrix_PQ {
private static final int INF = Integer.MAX_VALUE;
static class Node implements Comparable<Node> {
int index;
int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.distance, o.distance);
}
}
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int V = Integer.parseInt(in.readLine());
int[][] adjMatrix = new int[V][V];
StringTokenizer st = new StringTokenizer(in.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
for (int i = 0; i < V; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < V; j++) {
adjMatrix[i][j] = Integer.parseInt(st.nextToken());
}
}
int[] distance = new int[V];
boolean[] visited = new boolean[V];
Arrays.fill(distance, INF);
distance[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int cur = current.index;
if (visited[cur]) continue;
visited[cur] = true;
for (int i = 0; i < V; i++) {
if (!visited[i] && adjMatrix[cur][i] > 0) {
int newDist = distance[cur] + adjMatrix[cur][i];
if (newDist < distance[i]) {
distance[i] = newDist;
pq.offer(new Node(i, newDist));
}
}
}
}
System.out.println(distance[end] != INF ? distance[end] : -1);
}
}
시간 복잡도
- 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거침
- 각 노드마다 인접한 간선들을 모두 검사하는 과정
- 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정
- 각 과정별 시간 복잡도 계산
- 각 노드는 최대 한 번씩 방문하므로(첫 노드와 해당 노드 간의 갈 수 있는 루트가 있는 경우만 해당) 그래프의 모든 간선은 최대 한 번씩 검사
- 즉 각 노드마다 인접한 간선들을 모두 검사하는 과정은 `𝑂(𝐸)` 시간이 걸림(E는 간선(edge)의 약자)
- 우선순위 큐에 가장 많은 (노드, 거리) 정보가 들어가는 경우에 우선순위 큐에 (노드, 거리) 정보를 넣고 삭제하는 과정이 최악의 시간이 걸림
- 우선순위 큐에 가장 많은 (노드, 거리) 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다 배열의 최단 거리가 갱신되고 우선순위 큐에 노드/거리가 추가되는 것임
- 이때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로 최대 `𝑂(𝐸)`의 시간이 걸리고 `𝑂(𝐸)`개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 `𝑂(𝑙𝑜𝑔𝐸)`가 걸림
- 따라서 해당 과정의 시간 복잡도는 `𝑂(𝐸𝑙𝑜𝑔𝐸)`
- 각 노드는 최대 한 번씩 방문하므로(첫 노드와 해당 노드 간의 갈 수 있는 루트가 있는 경우만 해당) 그래프의 모든 간선은 최대 한 번씩 검사
- 과정 1 + 과정 2 = `𝑂(𝐸)` + `𝑂(𝐸𝑙𝑜𝑔𝐸)` = `𝑂(𝐸 + 𝐸𝑙𝑜𝑔𝐸)` = `𝑂(𝐸𝑙𝑜𝑔𝐸)`
- 힙의 시간 복잡도: `𝑂(𝑙𝑜𝑔N)`