다익스트라 Dijkstra
- 다익스트라 알고리즘이란 가중치가 있는 그래프에서 특정 정점에서 다른 모든 정점으로 가기 위한 최단 경로를 찾을때 사용하는 알고리즘이다.
- 시작 정점에서 거리가 최소인 정점부터 탐욕적으로 선택해 나가면서 최단 거리를
계속 갱신한다.
알고리즘 특징
다이나믹 프로그래밍
a -> b -> c 로 가는 최단 거리는 a -> c 로 가는 최단거리이고 이는 a -> b 최단거리와 b -> c 최단 거리의 합이고, 그것들도 각각의 최단 거리이므로 다이나믹 프로그래밍 유형이라고 할 수 있다.
이 개념을 활용해서, 다익스트라 문제에서 간선이 추가될 경우 다시 다익스트라를 돌리지 않아도 효율적으로 최단거리를 갱신 할 수 있다.
(a에서 b 로 가는 최단거리 가 있을 때 그래프에 i -> j 간선이 추가될 경우, a 에서 i 로 가는 최단거리 + i -> j 간선의 가중치 + j 에서 b 로 가는 최단거리 값을 기존 최단 거리 값과 비교해서 작은 값이 갱신된 최단거리가 된다.)
그리디(탐욕) 알고리즘
근시안적으로 그 순간에 최적이라고 생각되는 것을 선택해 나가면 그것이 답이 된다.
다음 정점을 선택할 때 시작 위치에서 최소 비용으로 갈 수 있는 정점을 선택하여 최소 비용을 갱신하므로 탐욕 알고리즘이다.
음의 가중치가 존재하는 그래프에서는 불가능
다익스트라에서 이미 선택한 정점은 최소 비용이 정해진다. 하지만 음의 가중치라면 이미 선택한 정점이여도 음의 가중치를 가진 간선이 발견되면 해당 정점의 최소 비용을 갱신해야 하므로, 음의 가중치가 존재하는 그래프에서는 작동하지 않는다.
-> 벨만 포드 알고리즘은 가능하다.
사이클, 셀프 루프, 두 노드 사이의 여러 간선이 있어도 상관없음
해당 노드까지의 더 짧은 경로가 발견되면 무시하므로 음의 가중치만 없으면 상관없다.
알고리즘 접근 방식
그래프 설명
- 시작 정점을 기준으로
정점 v까지의 최단 거리를d[v]라고 한다. - 위 그래프는
시작 정점 s가 있고,d[a],d[b]값은 구해져 있는 상태이다. - 또한 가중치가 있는 간선
s -> e,a -> e,b -> e가 존재한다.
(i -> j 간선의 가중치는w(i, j)로 표현)
최단 거리 구하기
위 그래프에서 시작 정점 s부터 정점 e까지의 최소 비용 d[e] 를 구하기 위한 방법은 다음과 같다.
- a까지의 최단 경로 가중치 합 + a부터 e로 향하는 간선의 가중치
=d[a]+w(a, e) - b까지의 최단 경로 가중치 합 + b부터 e로 향하는 간선의 가중치
=d[b]+w(b, e) - s 에서 e 까지 간선의 가중치
=w(s, e)
위 세 값을 비교하여 가장 작은 값이 d[e] 가 된다.
다익스트라 알고리즘은 이 아이디어를 사용한다.
다익스트라 알고리즘
다익스트라 알고리즘에는 정점의 전체 집합 V, 최소 비용를 찾은 (선택된) 정점들의 집합 S가 있다.
-
처음 시작
시작은정점 s이면d[s] = 0이다. 배열 d의 다른 값들은 무한대이다.
(집합 V - S에 속하는정점 n들에 대해d[n] = ∞) -
정점 선택하기 (탐욕적)
1.집합 S에 속하지 않은 정점 중, 출발 지점부터 가장 거리가 가까운정점 u를 선택한다. (정점 u를집합 S에 추가한다.)
2.집합 S에 속하지 않은정점 u의 모든인접 정점 v들에 대해서
지금까지 찾은 출발점에서 정점 v까지 최소비용이정점 u를 겨처서정점 v에 이르는 경우의 비용보다 크면 더 짧은 경로를 찾은것이므로정점 v까지의 최소비용을 갱신한다.
->d[v] > d[u] + w(u, v)이면d[v] = d[u] + w(u, v)
3. 위 과정을V = S가 될때 까지 반복한다.
예시
위와 같은 그래프가 있다. 위에서 설명한 논리 그대로 정점 1에서 부터 다른 정점까지의 최단 거리를 구해보겠다.
-
시작 d[1] = 0, 나머지는 무한대
아래는 d 배열이다.
i 1 2 3 4 d[i] 0 ∞ ∞ ∞ 현재 집합
S = {} -
정점 1 선택
집합 S에 속하지 않은 d값이 최소인 정점 1을 선택하고 집합 S에 추가
정점 1의 인접 정점중 집합 S에 속하지 않은 2, 3 에 대해서
d[2] > d[1] + w(1,2) (∞ > 0 + 3) 이므로 d[2] = 3
d[3] > d[1] + w(1,3) (∞ > 0 + 6) 이므로 d[3] = 6i 1 2 3 4 d[i] 0 3 6 ∞ 현재 집합
S = {1}
-
정점 2 선택
집합 S 에 속하지 않은 d값이 최소인 정점 2를 선택하고 집합 S에 추가
정점 2의 인접 정점중 집합 S에 속하지 않은 3, 4에 대해서
d[3] > d[2] + w(2, 3) (6 > 3 + 2) 이므로 d[3] = 5
d[4] > d[2] + w(2, 4) (∞ > 3 + 1) 이므로 d[4] = 4i 1 2 3 4 d[i] 0 3 5 4 현재 집합
S = {1, 2} -
정점 4 선택
집합 S 에 속하지 않은 d값이 최소인 정점 4 를 선택하고 집합 S에 추가
인접 정점이 없으므로 넘어간다.i 1 2 3 4 d[i] 0 3 5 4 현재 집합
S = {1, 2, 4} -
정점 3 선택
집합 S 에 속하지 않은 d값이 최소인 정점 3 를 선택하고 집합 S에 추가
인접 정점 2, 4 모두 집합 S에 포함되므로 넘어간다.i 1 2 3 4 d[i] 0 3 5 4 현재 집합
S = {1, 2, 4, 3} -
집합 S 가 전체 집합과 동일하므로 종료
최종적으로 정점 1부터 나머지 정점까지의 최단 거리는 다음과 같다.
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| d[i] | 0 | 3 | 5 | 4 |
구현 (최적화 X)
일단 위 논리 그대로 구현해보겠다. 그래프는 인접 리스트로 표현했다.
n은 정점의 개수, 정점은 1번부터 n번까지 있다.
dijkstra() 는 start 부터 다른 정점들 까지의 최소 비용을 담은 int [] d 배열을 반환한다.
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
private int[] dijkstra(int n, int start, List<Edge>[] graph) {
Set<Integer> S = new HashSet<>();
// d 초기화: 시작 정점은 0, 나머지는 큰 값
int[] d = new int[n + 1];
Arrays.fill(d, Integer.MAX_VALUE - 1);
d[start] = 0;
// S 가 전체 집합이 될 때 까지 반복
while (S.size() != n) {
// S 에 속하지 않고 d가 가장 작은 정점 찾기
int min = Integer.MAX_VALUE;
int node = -1;
for (int i = 1; i <= n; i++) {
if (!S.contains(i) && d[i] < min) {
min = d[i];
node = i;
}
}
S.add(node); // S 에 정점 넣기
for (Edge next : graph[node]) {
int nextNode = next.to;
int newWeight = d[node] + next.weight;
// d[nextNode] > d[node] + w(node, nextNode) 이면 값 업데이트
if (!S.contains(nextNode) && d[nextNode] > newWeight) {
d[nextNode] = newWeight;
}
}
}
return d;
}
// start 부터 end 까지의 최단 거리는 d[end] 가 된다.시간복잡도
while 문 안의 S 에 속하지 않고 d가 가장 작은 정점 찾기 부분에서 최솟값을 찾느라 을 써버리는 것을 알 수 있다.
때문에 이 dijkstra 함수의 시간복잡도는 이다. (E 는 간선의 개수)
최적화 (우선순위 큐)
집합 S에 포함되지 않는 정점 중에 현재까지의 최소 비용 = d 값이 가장 작은 정점을 꺼내는 작업을 효율적으로 하기 위해 우선순위 큐 를 사용한다.
큐를 집합 V - S 라고 생각하면, 집합 S에 넣는 행동을 큐에서 꺼내는 것으로 대체할 수 있고, d값이 가장 작은 값은 꺼내는 작업을 큐에서 최소값을 꺼내는 것으로 대체하면 딱 들어맞는다.
우선순위 큐에 방문할 예정인 정점들과 거리값을 넣어두고, 거리가 최소인것 부터 꺼내서 선택하면 된다.
-
처음 시작
시작 정점이s라면d[s] = 0, 나머지d의 값은 무한대이다.
우선순위 큐에 시작 정점 번호와 weight값(s, 0)을 넣는다. -
정점 선택하기
1.우선순위 큐에서cost값이 가장 작은 데이터(node, cost)를 꺼낸다.
2.node의 인접 정점nextNode들에 대해
d[nextNode] > d[node] + w(node, nextNode)면
d[nextNode] = d[node] + w(node, nextNode),
우선순위 큐에(nextNode, d[node] + w(node, nextNode))를 넣는다.
3. 위 과정을우선순위 큐가 빌때까지 반복한다.
코드
새로운 State 클래스를 만들어서 현재 정점의 번호 node와 현재까지의 최소비용 cost 를 저장하고, 이 데이터를 담는 우선순위 큐 pq를 만든다.
dijkstra() 는 start 부터 다른 정점들 까지의 최소 비용을 담은 int [] d 배열을 반환한다.
class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
// Edge 와 자료형이 동일하지만 다른 개념이므로 새로 구현해서 사용
class State {
int node, cost;
State(int node, int cost) {
this.node = node;
this.cost = cost;
}
}
private int[] dijkstra(int n, int start, List<Edge>[] graph) {
Queue<State> pq = new PriorityQueue<>((s1, s2) -> Integer.compare(s1.cost, s2.cost));
pq.offer(new State(start, 0));
int[] d = new int[n + 1];
Arrays.fill(d, Integer.MAX_VALUE);
d[start] = 0;
// 큐가 비는 순간이 모든 정점을 선택한 순간이다.
while (!pq.isEmpty()) {
State state = pq.poll();
int node = state.node;
int cost = state.cost;
// 이미 최소 비용이 정해진 정점일 경우 넘어간다. (중복 방문 방지)
if (cost > d[node]) {
continue;
}
for (Edge next : graph[node]) {
int nextNode = next.to;
int newWeight = d[node] + next.weight;
if (d[nextNode] > newWeight) {
d[nextNode] = newWeight;
pq.offer(new State(nextNode, newWeight));
}
}
}
return d;
}시간복잡도
우선순위 큐를 사용한 다익스트라의 시간복잡도는 이다.
이것이 일반적인 다익스트라 알고리즘의 구현 방식이다.
문제 풀이
정점 X 기준으로 왕복 최소 비용이 가장 큰 값을 출력하는 문제이다.
위 예시와 dijkstra 함수의 코드는 동일하다.
간선의 방향을 반대로 한 그래프로 다익스트라 알고리즘을 돌리면 올 떄의 최소 비용을 알 수 있다.
이를 활용해서 왕복 최소 비용을 효율적으로 구했다.
import java.io.*;
import java.util.*;
public class Main {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static class State {
int node, cost;
State(int node, int cost) {
this.node = node;
this.cost = cost;
}
}
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
List<Edge>[] graph = new ArrayList[n + 1];
List<Edge>[] reverse_graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
reverse_graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(bf.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
graph[from].add(new Edge(to, time));
reverse_graph[to].add(new Edge(from, time));
}
int[] dist = dijkstra(n, x, graph);
int[] reverse_dist = dijkstra(n, x, reverse_graph);
int max = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
max = Math.max(max, dist[i] + reverse_dist[i]);
}
System.out.println(max);
}
private static int[] dijkstra(int n, int start, List<Edge>[] graph) {
Queue<State> pq = new PriorityQueue<>((s1, s2) -> Integer.compare(s1.cost, s2.cost));
pq.offer(new State(start, 0));
int[] d = new int[n + 1];
Arrays.fill(d, Integer.MAX_VALUE);
d[start] = 0;
while (!pq.isEmpty()) {
State state = pq.poll();
int node = state.node;
int cost = state.cost;
if (cost > d[node]) {
continue;
}
for (Edge next : graph[node]) {
int nextNode = next.to;
int newWeight = d[node] + next.weight;
if (d[nextNode] > newWeight) {
d[nextNode] = newWeight;
pq.offer(new State(nextNode, newWeight));
}
}
}
return d;
}
}읽어보면 좋은 글: 잘못 구현한 다익스트라 알고리즘 저격하기 - djm03178
