다익스트라 알고리즘은 한 꼭짓점에서 다른 꼭짓점까지의 최단 경로를 계산하기 위해서 사용되는 알고리즘이다.
해당 알고리즘은 여러 변형들이 존재한다. 일반적인 변형은 두 꼭짓점에서 최단 경로 계산에 국한된 것이 아닌 모든 꼭짓점에 대한 최단 경로를 계산하는 알고리즘으로 최단 경로 트리 (SPT, Shortest Path Tree)를 구성하는 방식으로 확장된다.
정의
다익스트라 알고리즘은 가중 그래프(Weighted Graph)에서 한 꼭짓점(출발점)으로부터 다른 모든 꼭짓점까지의 최단 경로를 효율적으로 찾는 알고리즘이다.
해당 알고리즘은 동작에 있어 우선순위 큐(Priority Queue)와 탐욕적 방법(Greedy Approach)을 사용해 탐색하는 방식으로 동작한다.
여기서 우선순위 큐를 사용하는 이유에 대해서는 나중에 설명을 하겠다.
추가적으로 이 알고리즘을 사용하기 위해서 그래프에서 음수인 가중치가 없어야 한다.
- 왜 가중치가 음수일 경우는 만족하지 않는 것이가?
만약 음수인 가중치가 존재 한다면, 이미 방문한 노드도 이후에 갱신될 가능성이 있기 때문에 올바른 최단 경로를 보장할 수 없다.
간단한 예를 들면, 측정 한 노드까지의 경로가 10이라고 정의되어 있을 때, 추가로 음수인 간선을 통해서 더 짧은 경로가 발견될 수 있다. 하지만 해당 알고리즘은 이미 정의된 경로를 수정하고 있지 않기 때문에 잘못된 결과를 도출할 수 있기 때문이다.
동작 과정
자세한 동작 과정에 대하여 이해를 위해서 간단한 예시 그래프를 사용 하겠다.
(A)
/ \
4 2
/ \
(B)---1---(C)
\ /
5 3
\ /
(D)Step. 1. 초기화
출발 지점에서 각 노드 까지의 거리 값을 담을 배열을 선언하고, 출발 지점은 0값을 나머지 노드에 대한 값은 무한대로 설정을 한다.
| A | B | C | D |
|---|---|---|---|
| 0 | ♾️ | ♾️ | ♾️ |
Step. 2 인접한 노드 거리 측정
현재 위치에서 인접한 노드 중에서 방문하지 않은 노드에 대하여 가중치를 갱신해준다.
| A | B | C | D |
|---|---|---|---|
| 0 | 4 | 2 | ♾️ |
Step.3 노드 이동
가중치에 대한 정보를 담은 배열에서 가장 작은 값을 갖고 있는 노드로 이동을 하여 인접한 노드들의 가중치를 갱신을 한다.
현재 위치 A -> C 이동
| A | B | C | D |
|:---:|:---:|:---:|:---:|
| 0 | 4 | 2 | ♾️ |
C위치에서 이동할 수 있는 방법은 B로 이동을 하거나 D로 이동을 할 수 있다.
B로의 이동은 기존 배열에 A -> B로의 이동에 대한 가중치 값이 갱신되어 있지만, A -> C -> B로의 이동이 오히려 더 작은 값을 갖고 있다.
| A -> B | 비교 | A -> C -> B |
|---|---|---|
| 4 | > | 2 + 1 = 3 |
이러한 경우에는 가중치 배열에서 더 낮은 값을 채택한다.
| A | B | C | D |
|---|---|---|---|
| 0 | 3 | 2 | 5 |
Step. 3 반복
모든 노드들로 이동하지 않았기 떄문에 아직은 정확한 값이라고 판단하기 이르다. 그렇기 때문에 다음으로 가중치가 적은 노드로 이동하여 가중치를 비교하는 동작을 반복하자.
다음으로 B로 이동을 하여 다른 노드로의 이동할 때 소요되는 비용을 비교하여 모든 노드들을 방문하여 계속 갱신하면 된다.
이해를 돕기 위해서 시청각 자료를 준비했다.
코드로 구현
일반 배열을 사용
import java.util.Arrays;
public class DijkstraArray {
private static final int INF = Integer.MAX_VALUE; // 무한대 값 설정
public static int[] dijkstra(int[][] graph, int start) {
int V = graph.length;
int[] distance = new int[V]; // 최단 거리 정보를 담을 배열
boolean[] visited = new boolean[V]; // 방문 여부 정보를 담을 배열
// 1. 거리 배열 초기화
Arrays.fill(distance, INF);
distance[start] = 0; // 시작 노드 거리 0
// 2. 모든 노드에 대해 반복
for (int i = 0; i < V - 1; i++) {
int minIndex = -1;
int minValue = INF;
// 3. 방문하지 않은 노드 중 가장 가까운 노드를 선택
for (int j = 0; j < V; j++) {
if (!visited[j] && distance[j] < minValue) {
minValue = distance[j];
minIndex = j;
}
}
if (minIndex == -1) break; // 남은 노드가 없으면 종료
visited[minIndex] = true; // 선택된 노드 방문 처리
// 4. 선택된 노드를 기준으로 인접 노드 거리 갱신
for (int j = 0; j < V; j++) {
if (!visited[j] && graph[minIndex][j] != 0 && distance[minIndex] != INF) {
int newDist = distance[minIndex] + graph[minIndex][j];
if (newDist < distance[j]) {
distance[j] = newDist;
}
}
}
}
return distance
}
public static void main(String[] args) {
int[][] graph = {
{0, 4, 2, 0},
{4, 0, 1, 5},
{2, 1, 0, 3},
{0, 5, 3, 0}
};
int [] answer = dijkstra(graph, 0); // 0번 노드에서 시작
}
}위 간단하게 구현한 코드를 자세히 몇 가지 특징들이 존재한다.
- n개의 노드 처리를 위해 반복문 사용
- 각 노드에 대하여 n개의 노드를 순회하면서 최소 거리 노드를 찾는다
이렇게 두 가지 점들 때문에 시간 복잡도는
해당 방식의 문제점은 노드의 수가 많아지면 연산 속도가 느려질 수 있다. 또한 간선의 수가 적을 때 비효율적으로 동작할 수 있게 된다.
💡우선순위 큐 사용(힙, Heap)
import java.util.*;
public class DijkstraPQ {
private static final int INF = Integer.MAX_VALUE;
static class Node implements Comparable<Node> {
int index, cost;
Node(int index, int cost) {
this.index = index;
this.cost = cost;
}
public int compareTo(Node other) {
return Integer.compare(this.cost, other.cost); // 우선순위 큐에서 최소 비용 기준 정렬
}
}
// 양방향을 위해 메서드로 정의
public static void addEdge(List<List<Node>> graph, int u, int v, int cost) {
graph.get(u).add(new Node(v, cost));
graph.get(v).add(new Node(u, cost));
}
public static int[] dijkstra(List<List<Node>> graph, int start) {
int V = graph.size();
int[] distance = new int[V];
Arrays.fill(distance, INF);
distance[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
while (!pq.isEmpty()) {
Node current = pq.poll();
int curIndex = current.index;
int curCost = current.cost;
if (curCost > distance[curIndex]) continue; // 이미 처리된 경우 건너뛰기
for (Node neighbor : graph.get(curIndex)) {
int newDist = curCost + neighbor.cost;
if (newDist < distance[neighbor.index]) {
distance[neighbor.index] = newDist;
pq.add(new Node(neighbor.index, newDist));
}
}
}
return distance;
}
public static void main(String[] args) {
int V = 4;
List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
addEdge(graph, 0, 1, 4); // A ↔ B (4)
addEdge(graph, 0, 2, 2); // A ↔ C (2)
addEdge(graph, 1, 2, 1); // B ↔ C (1)
addEdge(graph, 1, 3, 5); // B ↔ D (5)
addEdge(graph, 2, 3, 3); // C ↔ D (3)
int[] answer = dijkstra(graph, 0); // A(0)번 노드에서 시작
}
}위 구현 코드를 보면 기존과 다르게 우선순위 큐를 이용하여 거리가 가장 작은 노드를 빠른 시간에 찾을 수 있게 되면서 시간 복잡도는 줄어들게 된다.
그래서 그래프가 클수록 일반 배열을 사용하는 방식보다는 우선순위 큐를 이용하는 방식이 효율적인 방법이 된다.
각 방법에 대하여 비교를 하면 아래와 같다.
| 방식 | 장점 | 단점 | 시간 복잡도 |
|---|---|---|---|
| 일반 배열 | 구현이 쉽다 | 노드의 수가 많으면 비효율 | |
| 우선순위 큐 | 희소 그래프에서 성능 향상 | 구현이 어렵다 |
