![[알고리즘] 데이크스트라(Dijkstra)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJEJJD%2FbtsBGkIePKO%2FuHCbZPDvqqbRO3kLKsAGE0%2Fimg.png)
[알고리즘] 데이크스트라(Dijkstra)CS/알고리즘2023. 12. 9. 18:27
Table of Contents
Concept
- 그리디 알고리즘의 한 분류
- 다이나믹 프로그래밍 메모이제이션 기법 활용
- 부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음.
- 주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘
Feature
우선순위 큐와 거리배열(DP)을 활용하여 로직 구성.
- 한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐.
- 가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘
- 음수 가중치를 가진 그래프에서는 사용불가.
- 우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN)
Implement
인접 리스트를 통한 구현
- 우선 데이크스트라 소스코드를 보자.
private static int dijkstra(int start, int end) {
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
int[] dp = new int[list.size()]; //거리 저장 배열
Arrays.fill(dist, Integer.MAX_VALUE);
pq.offer(new int[]{start,0});
while(!pq.isEmpty()) {
int[] cur = pq.poll();
if(cur[0] == end) return cur[1]; //목표 정점에 도착한 경우
for(Node n : list.get(cur[0])) {
if(dp[n.v] > cur[1]+n.w) { //기존의 최단거리보다 더 낮을 경우에만
pq.offer(new int[]{n.v, cur[1] + n.w});
dp[n.v] = cur[1]+n.w;
}
}
}
return -1; //start -> end 까지의 경로가 존재하지 않을 경우
}
코드 설명
- 위 코드는 start → end까지의 최단거리를 구하기 위해 두 개의 매개변수를 받아 구현.
- start로부터 모든 정점까지의 최단거리를 구하려면 if(cur[0] == end) return cur[1]; 구문만 제거하면 됨.
- 우선순위 큐의 거리(cur[1])에 따른 오름차순 정렬 재정의
- 거리배열(dp)를 정점의 개수만큼 선언 및 최대값으로 초기화
- while문을 돌면서 큐에서 꺼낸 정점과 인접해있는 정점들에 대해 dp배열의 거리와 비교해 더 최단거리일 경우에만 큐에 추가 및 dp배열 갱신
동작과정
- 위와 같은 그래프에서 1 → 3으로 가는 최단거리는 6
- 1 → 3 (거리 : 10)
- 1 → 2 → 4 → 3 (거리 : 3+1+2 = 6)
- 1번 정점과 인접한 2(거리:3) 와 3(거리:10)이 큐에 추가되고 dp배열 갱신이 이루어짐.
- 우선순위 큐 정렬에 의해 2번 정점이 먼저 꺼내지고 인접한 4번 정점이 큐에 추가되고(거리:4) 최단 거리 갱신이 이루어짐.
- 4번 정점이 큐에서 꺼내질 때 현재 부분문제인 1→4 까지의 최단거리는 4
- 4에서 4→3 까지의 거리인 2를 더해 6과 dp[3]의 값을 비교
- 10(기존값) > 6 이므로 dp[3]이 6으로 갱신됨.
정리
- 데이크스트라는 알고리즘 문제 중에서 꽤나 비중있는 알고리즘 분류 중 하나이며 생각보다 개념이 쉽기 때문에 한번 제대로 알아두면 두고두고 써먹을 수 있는 알고리즘이니 정리를 한번 해보는것도 나쁘지 않음.
- 간단히 요약하자면 BFS를 알고있는 사람이라면 BFS의 PQ(우선순위 큐)버전이라 생각하는 것도 좋을 듯!
(약간의 dp를 곁들인)
'CS > 알고리즘' 카테고리의 다른 글
[PS] 백준13460 : 구슬 탈출 2(Java) (0) | 2023.12.13 |
---|---|
[PS] 백준2294 : 동전 2(Java) (0) | 2023.12.09 |
[알고리즘] 최장 증가 수열 (LIS, Longest Increasing Subsequence) (0) | 2023.12.08 |
[PS] 백준20165 : 인내의 도미노 장인 호석(Java) (0) | 2023.12.08 |
[알고리즘] 배낭 문제(Knapsack Problem) (0) | 2023.12.08 |
@Beemo9 :: BeHinD
개발 기술 블로그, Dev
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!