[도구정리] 다익스트라 알고리즘
다익스트라
다익스트라 알고리즘은 최단거리 알고리즘으로 많이들 들어봤을 것이다.
-> 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다.
-> 일반적으로 시간 복잡도는 O((V+E) logV)의 시간 복잡도를 가지고 있다고 한다.(V : 노드의 개수, E : 간선의 개수)
-> 인접 리스트 및 우선 순위 큐를 통하여 구현하는 것이 대표적이다.
다익스트라 알고리즘 원리
기억하면 되는 것은 그리디 알고리즘이면서 다이내믹 프로그래밍 기법을 사용한다는 것이다.
딱 두 단계를 반복하며 모든 노드에 대해 반복하면 된다.
1) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.(그리디 알고리즘)
2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다(다이내믹 프로그래밍)
다음과 같은 그래프에서 1번 노드가 갈 수 있는 노드들에 대해 최단 경로를 찾아보자.
시작은, 모든 배열의 값을 무한(null)으로 정해둔다.
| 1 | 2 | 3 | 4 | 5 |
| INF | INF | INF | INF | INF |
이제 시작 노드인 1부터 과정을 밟으면 된다. 이때 위의 딱 두가지 과정만 기억하자.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 2 | 3 | INF | INF |
자기 자신은 0으로 저장되고 나머지 이동할 수 있는 경로에 대해 값이 넣어진다.
여기서 우리는 우선순위 큐를 사용할 것이라는걸 기억하자.
-> 경로상의 가중치에 대해 정렬할 것이다.
이제 1,2,3을 우선순위 큐에 넣게 될 것이고 다음 시작 지점은 1이 될 것이다.
1은 방문을 했었기 때문에 패스하고, 다음 순서인 2를 꺼내자.
2를 꺼내어 업데이트해주자.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 2 | 3 | 7 | INF |
와 같이 업데이트된다.
3을 해주자.
| 1 | 2 | 3 | 4 | 5 |
| 0 | 2 | 3 | 7 | INF |
이런 식의 흐름을 갖게 되는 것이다.
대표 문제 및 코드
사실 이해도 힘들고 하니 대표 문제와 함께 코드를 살펴보자.
백준 1753번이다.
https://www.acmicpc.net/problem/1753
문제의 풀이는 https://to-travel-coding.tistory.com/266을 참고하고, 다익스트라 부분만 살펴보자.
private static void dijkstra(int start){
PriorityQueue<Node> pq = new PriorityQueue<>();
boolean[] visited = new boolean[v+1];
pq.add(new Node(start, 0));
dist[start] = 0;
while(!pq.isEmpty()){
Node curNode = pq.poll();
int cur = curNode.end;
if(visited[cur]) continue;
visited[cur] = true;
for(Node node : list[cur]){
if(dist[node.end] > dist[cur] + node.weight){
dist[node.end] = dist[cur] + node.weight;
pq.add(new Node(node.end, dist[node.end]));
}
}
}
}
class Node implements Comparable<Node>{
int end, weight;
public Node(int end, int weight){
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
return weight - o.weight;
}
}
위의 코드를 예제와 함께 순서대로 따라가 보자.
처음에 start로 원하는 시작 지점(예제로 따지면 1)이 들어온다.
우선순위 큐를 선언해 주고, 한 번 방문한 지점은 재방문하지 않게 visited 배열을 선언한다.
우선순위 큐에 넣고 시작하며, 이때 dist(최단 거리 저장 배열)의 0을 0으로 해준다.
-> 여기서 왜 visited[1] = true는 안 해주나?라고 생각할 수 있지만 코드를 쭉 읽어보자.
큐가 비어있을 때까지 반복하며, 도착지가 다시 출발지가 된다.
만약 방문한 적이 있다면 건너뛴다.(이 부분에서 최단거리가 저장된다. 조금만 더 인내심을 가지고 살펴보자.)
이제 와서 [1]에 대해 방문을 처리해 주고, 1에서 갈 수 있는 2와 3에 대해 확인할 가치가 있는 노드인지를 조건문을 통해 검사한다.
이후 우선순위 큐에 추가해 준다.
다시 1이 큐에서 나올 것이고(가중치 0) 방문한 적이 있으므로 건너뛰어진다.
2가 큐에서 나오고 방문한 적이 없으므로 시작된다.
여기서 주요한 부분은 첫 번째로 3으로 가는 최단거리가 이미 저장되어 있기 때문에 그것과 비교를 해야 한다.
dist[3] = 3
dist[2] = 2
node.weight = 4로 조건문을 만족시키지 못하기에 넘어가진다.
그럼 여기서 문제!! 2 -> 3이 0이라면 어떻게 될까?
조건문을 통과하고 들어갈 수 있으며 dist [3] = 2 + 0으로 업데이트될 것이다. 후에 pq.add(new Node(3, dist[3])이 들어간다.
즉, 여기서 우선순위 큐에 의해 현재 경로가 가장 짧다고 나온 것 순으로 진행되기에 최단거리를 보장할 수 있게 되는 것이다!!
결과적으로 2->3에서 들어온 Node가 먼저 뽑혀서(2->3이 만약 0이라면) 3이 방문처리 될 것이기에 이 전에 들어온 3에 대한 값은 넘어가질 것이다.