다익스트라 알고리즘은 가장 유명한 그래프 알고리즘 중 하나이다. 단일 시작점 최단 경로 알고리즘으로, 시작 정점 $s$에서부터 다른 정점들까지의 최단 거리를 계산한다.
동작 과정
그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘이다. '음의 간선'이 없을 때 정상적으로 동작한다.
다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해 임의의 과정을 반복하기 때문이다.
간략한 원리는 다음과 같다.
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3, 4번을 반복한다.
각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다.
동작 원리를 살펴보자.
다음과 같은 그래프가 있다.
출발 노드를 1이라 하자. 초기 상태에선 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화한다. 실제 코드에선 999,999,999와 같은 값으로 설정할 수 있다.
먼저 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0이기 때문에 처음에는 출발 노드가 선택된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다.(1번 노드와 연결된 모든 간선을 확인하기). 1번 노드에서 2번, 3번, 4번 노드로 가는 최소 비용은 2, 5, 1이므로 이 값들로 테이블을 갱신한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | ∞ | ∞ |
이다음의 모든 단계에서도 마찬가지로 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 따라서 4번 노드가 선택된다. 4번 노드에서 3번, 5번 노드로 가는 최소 비용은 4(1+3), 2(1+1)이다(기존의 거리를 더한다). 이 두 값은 기존의 리스트에 담겨 있던 값보다 작기 때문에 테이블을 갱신해준다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | ∞ |
방문하지 않은 노드 중 최단 거리가 가장 짧은 2번 노드를 선택하고(최단 거리가 같을 경우, 일반적으로 번호가 작은 노드) 확인해보면, 2번 노드를 거쳐서 도달할 수 있는 경우, 현재의 최단 거리를 더 짧게 갱신할 수 없다. 3번 노드는 5, 4번 노드는 4이기 때문이다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | ∞ |
다음은 5번 노드. 3번 노드와 6번 노드로 이동하는 경우, 각각 3(2+1), 4(2+2)이므로 테이블을 갱신한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
3번, 6번 노드에 대해서 다음과 같은 과정을 반복해준다. 최종 테이블은 다음과 같다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
이 테이블이 의미하는 것은 1번 노드에서 출발했을 때 각각의 노드로 가기 위한 최단 경로가 2, 3, 1, 2, 4라는 것이다.
위의 과정을 반복하면서 선택된 노드는 '최단 거리'가 완전히 선택된 노드이기 때문에, 더 이상 알고리즘을 반복 수행해도 최단 거리가 줄어들지 않는다. 즉, 다익스트라 알고리즘은 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 생각할 수 있다.
우선순위 큐를 이용하는 BFS
다익스트라 알고리즘은 BFS와 유사한 형태를 가진 알고리즘으로, BFS처럼 시작점에서 가까운 순서대로 정점을 방문해 간다. 하지만, 다익스트라 알고리즘에서는 큐 대신 우선순위 큐를 사용한다. 우선순위 큐에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다. 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 해준다.
우선순위 큐를 사용한다는 점을 제외하면 BFS의 구조와 비슷하다. 각 정점까지의 최단 거리를 저장하는 배열 $dist[]$를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사한다. 만약 간선 $(u, v)$를 검사했는데 $v$가 아직 방문하지 않은 정점이라고 하자. 그러면 $u$까지의 최단 거리에 $(u, v)$의 가중치를 더해 $v$까지의 경로의 길이를 찾는다. 이것이 지금까지 우리가 찾은 최단 거리라면 $dist[v]$를 갱신하고 $(dist[v], v)$를 큐에 넣는다.
이때 유의해야 할 것은 각 정점까지의 최단 경로가 갱신될 수 있다는 것이다. 아래의 간단한 예시 그림을 보자.
시작점 $s$를 방문하고 나면 $(2, a)$와 $(12, c)$가 우선순위 큐에 들어갈 것이다. 최단 거리 순으로 정점들을 큐에서 꺼낸다고 하면 $c$는 큐에 그대로 들어 있고, $a$와 $b$가 순서대로 방문되게 된다. 문제는 $b$가 방문될 때이다. $b$까지의 최단 경로에 $(b, c)$간선을 덧붙이면 $s$에서 $c$로 가는 길이 9인 경로를 찾을 수 있다. 이것은 우리가 알고 있던 길이 12인 경로보다 짧은 것이다. 이때 $dist[c]$를 갱신하기는 간단하지만, 우선순위 큐에 이미 들어 있는 $(12, c)$는 어떻게 할까?
대개 사용하는 방법은 $(12, c)$를 그대로 두고 $(9, c)$를 추가한 뒤, 나중에 큐에서 $(12, c)$가 꺼내지면 무시하는 방법이다. 그럼 이를 무시해야 하는지 어떻게 알 수 있을까?
큐에서 정점 번호 $u$와 최단 거리 $cost$의 쌍을 뽑아낸 후, $dist[u]$와 $cost$를 비교한다. 만약 $dist[u] < cost$라면, $u$까지 오는 $cost$보다 짧은 경로가 이미 발견됐다는 의미이므로 $(cost, u)$쌍은 무시하면 된다.
구현
우선순위 큐를 이용한 다익스트라 알고리즘을 구현한 자바 코드는 다음과 같다.
import java.util.*;
class Node implements Comparable<Node> {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Node other) {
if (this.distance < other.distance) {
return -1;
}
return 1;
}
}
public class Main {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
public static int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 최단 거리 테이블 만들기
public static int[] d = new int[100001];
public static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.offer(new Node(start, 0));
d[start] = 0;
while(!pq.isEmpty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
Node node = pq.poll();
int dist = node.getDistance(); // 현재 노드까지의 비용
int now = node.getIndex(); // 현재 노드
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph.get(now).size(); i++) {
int cost = d[now] + graph.get(now).get(i).getDistance();
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(i).getIndex()]) {
d[graph.get(now).get(i).getIndex()] = cost;
pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Node>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph.get(a).add(new Node(b, c));
}
// 최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
}
알고리즘 그대로 구현하는 방법
import java.util.*;
class Node {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
public class Main {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
public static int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
public static boolean[] visited = new boolean[100001];
// 최단 거리 테이블 만들기
public static int[] d = new int[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
public static int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
public static void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph.get(start).size(); j++) {
d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance();
}
// 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph.get(now).size(); j++) {
int cost = d[now] + graph.get(now).get(j).getDistance();
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(j).getIndex()]) {
d[graph.get(now).get(j).getIndex()] = cost;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Node>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph.get(a).add(new Node(b, c));
}
// 최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
}출처 : https://github.com/ndb796/python-for-coding-test/blob/master/9/1.java
'알고리즘 > 알고리즘' 카테고리의 다른 글
| [Algorithm] 위상 정렬(Topological Sort) (0) | 2023.04.14 |
|---|---|
| [Algorithm] 분할 정복 (0) | 2022.08.25 |
| [Algorithm] BFS : 너비 우선 탐색(Java) (0) | 2022.08.02 |
| [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘 (0) | 2022.07.06 |