Dijkstra 알고리즘
- 정의
Dijkstra 알고리즘은 하나의 정점에서 나머지 정점까지의 최단 거리(경로)를 구하는 알고리즘입니다.
정점 사이에 간선이 존재하고, 간선마다 가중치(=비용)가 있습니다. 특징으로는 모든 가중치가 양수일 때만 사용할 수 있는 알고리즘입니다.
어떠한 정점에 방문할 때 이전의 선택했던 경로가 아니라 다른 경로를 거쳐 방문하는 것이 더 적은 비용이 든다면, 다른 경로를 거쳐 방문하면서 최단 거리를 구합니다.
말로만 설명하면 이해하기 어려우니 과정을 보면서 설명하겠습니다.
- 최단거리를 구하는 과정
위의 그래프는 정점이 5개, 간선이 6개이며 각 간선에는 가중치가 표시되어 있습니다.
distance배열은 시작 정점이 1일 때 각 정점으로 갈 수 있는 최소 비용을 저장합니다. 아직 어떠한 정점도 방문한 적이 없기 때문에 초기값으로 무한대를 의미하는 INF를 저장하고, 1은 자기 자신이기 때문에(=비용이 들지 않기 때문에) 0을 저장해놓습니다.
먼저 1에서 바로 갈 수 있는 정점부터 살펴봅니다.
"1 -> 2" 로 갈 때 "distance[2] > distance[1] + 5"가 성립하므로 distance[2]에 5를 저장합니다.
"1->4"로 갈 때 "distance[4] > distance[1] + 9"가 성립하므로 distance[4]에 9를 저장합니다.
"1->5"로 갈 때 "distance[5] > distance[1] + 1"가 성립하므로 distance[5]에 1을 저장합니다.
1에서 직접 갈 수 있는 정점을 모두 확인하였으니 1과 연결된 간선은 더이상 확인하지 않아도 됩니다. 현재 갈 수 있는 정점(정점 2, 4, 5가 해당됩니다.)을 거쳐서 갈 수 있는 정점이 있는지 확인해봐야 합니다. 따라서 현재 갈 수 있는 정점 중 가장 짧은 거리의 정점인 5를 살펴봅니다.
"1->5->4"로 간다면 "1->4"로 직접 갈 때보다 비용이 적게 듭니다. 즉 "distance[4] > distance[5] + 2"가 성립하므로 distance[4]에 3을 저장합니다.
위의 경우처럼 5와 연결된 간선는 모두 확인하였으니 현재 갈 수 있는 정점 중 가장 짧은 거리의 정점인 4를 살펴봅니다.(1과 5는 제외)
1에서 3으로 직접갈 수 있는 경로가 없었는데 정점 4를 거치면 정점 3에 방문할 수 있습니다. 즉 "distance[3] > distance[4] + 6"가 성립하므로 distance[3]에 9를 저장합니다.
4와 연결된 간선은 모두 확인하였으니 현재 갈 수 있는 정점 중 가장 짧은 거리인 2를 살펴봅니다.
정점 3에 방문할 때 4를 거치는 것보다 2를 거치는 것이 비용이 적게 듭니다. 따라서 "distance[3] > distance[2] + 2"가 성립하므로 distance[3]에 7을 저장합니다.
모든 정점을 다 방문했으므로 정점 3에서 갈 수 있는 정점이 없습니다. 따라서 종료합니다.
- 전체 코드
아래는 Dijkstra의 전체 코드입니다.
(백준 "1753 최단경로"의 코드이기도 합니다.)
Dijkstra 알고리즘 구현에서 핵심은 PriorityQueue이며, 현재 갈 수 있는 정점에서 가장 짧은 거리의 정점을 찾는 데 이용합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static int v, e;
static ArrayList<Node>[] graph;
static int[] dist;
static int INF = 10000000;
static class Node implements Comparable<Node>{ //PriorityQueue에서 가장 거리가 짧은 노드를 선택할 때 사용되기 때문에 Comparable 인터페이스 구현
int end, weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
public static void dijkstra(int k) {
PriorityQueue<Node> queue = new PriorityQueue<>(); //가장 거리가 짧은 노드를 선택해야 하기 때문에
boolean[] check = new boolean[v+1];
dist[k] = 0;
queue.add(new Node(k, 0));
while(!queue.isEmpty()) {
Node cur = queue.remove();
if(!check[cur.end]) {
check[cur.end] = true; //check에 true 저장하는 시점이 중요
for(Node next : graph[cur.end]) {
if(dist[next.end] > dist[cur.end]+next.weight) { //현재 위치에서 next로 가는게 더 짧은 경우 update
dist[next.end] = dist[cur.end]+next.weight;
queue.add(new Node(next.end, dist[next.end]));
}
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(br.readLine());
graph = new ArrayList[v+1];
for(int i=0; i<=v; i++)
graph[i] = new ArrayList<>();
for(int i=0; i<e; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
graph[a].add(new Node(b, w));
}
dist = new int[v+1];
for(int i=0; i<=v; i++)
dist[i] = INF;
dijkstra(k);
for(int i=1; i<=v; i++) {
if(dist[i]==INF)
System.out.println("INF");
else
System.out.println(dist[i]);
}
}
}