오늘은 다익스트라 알고리즘에 대해 자세히 알아보자!
다익스트라 Dijkstra 란?
이 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 유명한 방법 중 하나다. 많은 사람이 다익스트라 알고리즘이 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이라고 생각하는 경향이 있는데, 실제로 완성된 배열은 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현한다!
그러면 다익스트라 알고리즘의 특징은 무엇이 있을까?
🧐 특징
-
음수 가중치를 가진 간선이 존재하지 않는다 -> 간선은 모두 양수이다!
-
시간 복잡도의 경우 인접 행렬로 표현된 그래프의 시간 복잡도는 O(n^2)이다. 하지만 우선순위 큐를 사용하여 시간 복잡도를 O(ElogV)까지 낮출 수 있다.
-
그리디 알고리즘(탐욕법)과 다이나믹 프로그래밍(동적 계획법)의 특성을 가진다.
방문하지 않은 노드중에서 가장 비용이 적은 노드를 선택한다 ⇒ 그리디 알고리즘
해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 ⇒ 다이나믹 프로그래밍
다익스트라 알고리즘이 언제 사용되는지 알았으니 이제 다익스트라 알고리즘의 원리와 작동 방식에 대해 함께 살펴보자
다익스트라 알고리즘의 핵심 원리
- 인접 리스트로 그래프를 구현한다.
그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결하였다.
class Node {
int vertex; // 정점
int value; // 가중치
Node(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
}
2. 최단 거리 배열을 초기화하자
최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 큰 값(Integer.MAX_VALUE)으로 초기화한다.
int[] distance = new int[V+1];
for(int i=1; i<=V; i++) {
if(i==start) continue;
distance[i] = Integer.MAX_VALUE;
}3. 값이 가장 작은 노드를 고르자
최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작하면 된다.
4. 최단 거리 배열 업데이트 하기
선택된 노드에 연결된 에지(간선)의 값을 바탕으로 다른 노드의 값을 업데이트 한다.
이때 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트한다!
if(distance[연결된 노드] > distance[선택된 노드] + value) {
distance[연결된 노드] = distance[선택된 노드] + value;
}5. 과정 3~4를 반복해 최단 거리 배열을 완성한다
이제 관련된 예제 중 한문제를 풀어보자
다익스트라 알고리즘 예제 문제
문제는 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 것이다. 이때 가중치는 10이하의 자연수이다.
🔎 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static ArrayList<Node>[] graph;
static boolean visited[];
static int distance[];
static PriorityQueue<Node> pq;
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()); // 에지 개수
graph = new ArrayList[V+1];
for(int i=1; i<=V; i++) {
graph[i] = new ArrayList<>();
}
visited = new boolean[V+1];
// 객체가 우선순위 큐 내에서 자동으로 정렬
pq = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.w, o2.w)));
int K = Integer.parseInt(br.readLine()); // 시작점
distance = new int[V+1];
for(int i=1; i<=V; i++) { // 시작점만 0
if(i==K) continue;
distance[i] = Integer.MAX_VALUE;
}
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));
}
// 우선순위 큐에 시작점 저장
pq.add(new Node(K,0));
// 다익스트라
Dijkstra();
// 최단 경로값 출력
for(int i=1; i<=V; i++) {
if(!visited[i]) System.out.println("INF");
else System.out.println(distance[i]);
}
}
static void Dijkstra() {
while(!pq.isEmpty()) {
Node current = pq.poll();
int c_v = current.vertex;
if(visited[c_v]) continue; // 이미 방문하면 큐에 넣지 않음
visited[c_v] = true;
for(Node n : graph[c_v]) {
int next = n.vertex;
int value = n.value;
if(distance[next] > distance[c_v] + value) {
// 타깃 노드 최단 거리 업데이트하기
distance[next] = distance[c_v] + value;
// 우선순위 큐에 타깃 노드 추가하기
pq.add(new Node(next, distance[next]));
}
}
}
}
}
class Node{
int vertex;
int value; // 가중치
Node(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
}📃 풀이
⭐ PriorityQueue를 이용한 시간 줄이기
현재 노드에서 갈수 있는 노드 중 가장 작은 value 값을 찾기 위해서는 최악의 경우 O(N)이 걸린다. 하지만 우선순위큐를 사용하면 가장 작은 value 값을 지니고 있는 노드를 빠르고 간편하게 찾을 수 있다. 우선순위 큐는 데이터가 새롭게 들어올 때마다 자동으로 정렬한다.
PriorityQueue 정렬 기준을 세우는 코드는 아래와 같이 작성하면 된다.
1. 람다 식을 사용
pq = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.w, o2.w)));2. Node 클래스에서 적절한 compareTo() 함수를 이용해 설정
class Node implements Comparable<Node>{
int vertex;
int value; // 가중치
Node(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
@Override
public int compareTo(Node o) {
return value - o.value;
}
}class Node implements Comparable<Node>{
int vertex;
int value; // 가중치
Node(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
@Override
public int compareTo(Node o) {
if(this.value > o.value) return 1;
else return -1;
}
}💌 참고 자료
- Do it! 알고리즘 코딩테스트 자바 편
- [알고리즘/Java]다익스트라(Dijkstra) 알고리즘
- [Java] 다익스트라(Dijkstra Algorithm)
