다익스트라 (Dijkstra) 알고리즘
하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘
다익스트라 알고리즘에서 음수 간선이 존재하면 안 되는 이유
다익스트라 알고리즘의 각 단계
먼저 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자.
다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열이 반드시 있어야 한다.
이 1차원 배열을 distance라고 한다.
시작 정점을 v라 한다면 distance[v] = 0이고, 다른 정점에 대한 distance값은 시작 정점과 해당 정점 간의 가중치 값이 된다.
가중치 인접 행렬을 weight라 하면 distance[w] = weight[v][w]가 된다.
정점 v에서 정점 w로의 직접 간선이 없을 경우에는 무한대의 값을 저장한다.
(왜냐하면 가중치가 0일 수도 있기 때문이다. 따라서 가중치로 나오지 않을 무한대의 값을 저장하는 것)
시작단계에서는 아직 최단 경로가 발견된 정점이 없으므로 S = {v} 일 것이다.
즉 처음에는 시작 정점 v를 제외하고는 최단거리가 알려진 정점이 없다.
알고리즘이 진행되면서 최단거리가 발견되는 정점들이 S에 하나씩 추가될 것이다.
최단 경로 증명
위에서 설명한 것을 바탕으로 최단거리를 구해보자.
그러기 위해선 알고리즘의 각 단계에서 S안에 있지 않은 정점 중 가장 distance 값이 작은 정점을 S에 추가한다.
그 이유를 다음 그림에서 알아보자.
현재 S에 들어있지 않은 정점 중에서 distance값이 가장 작은 정점을 u라고 하자.
그러면 시작 정점 v에서 정점 u까지의 최단거리는 경로 1이 된다.
만약 더 짧은 경로, 예를 들어 정점 w를 거쳐서 가는 가상적인 경로가 있다고 가정해보자.
그러면 v -> u까지의 거리는 v -> w까지의 거리 2와 w -> u까지의 거리 3을 합한 값이 될 것이다.
그러나 경로 2는 경로 1보다 항상 길 수밖에 없다.
왜냐하면 현재 distance값이 가장 작은 정점은 u이기 때문이다.
다른 정점은 정점 u까지의 거리보다 항상 더 길 것이다.
따라서 매 단계에서 집합 S에 속하지 않는 정점 중에서 distance값이 가장 작은 정점들을 추가해나가면 시작 정점에서 모든 정점까지의 최단거리를 구할 수 있다.
distance값 갱신
새로운 정점 u가 S에 추가되면 S에 있지 않은 다른 정점들의 distance 값을 수정한다.
새로 추가된 정점 u를 거쳐서 정점 w까지 가는 거리와 기존에 w로 가는 거리를 비교해 더 작은 거리로 distance값을 수정한다.
즉 아래와 같은 수식을 이용한다.
distance[w] = min(distance[w], distance[u] + weight[u][w]) // min 함수는 두 매개변수 중 최솟값을 distance [w]에 저장하는 함수
다익스트라의 분석
네트워크에 n개의 정점이 있다면,
최단 경로 알고리즘은 주 반복문을 n번 반복하고 내부 반복문을 2n번 반복하므로 O(n^2)의 복잡도를 가진다.
구현 코드 1
백준 1916번 최소 비용 구하기를 기반으로 구성한 코드입니다.
https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
* 무한대를 처음엔 Integer.MAX_VALUE로 했는데 오버플로우가 나는지 채점 중 런타임 에러가 났다ㅠㅠ
무한대 값을 Integer.MAX_VALUE-1 로 하면 안남...왜지?
* 백준 사이트에서 알아본 결과
INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 합니다.
거리가 가장 멀어지는 경우를 생각해 보면, 1-2-3-4-5-6-...-V 이렇게 일직선으로 모든 간선이 최대 가중치를 가지고 연결되어 있을 때
총 V-1개의 간선을 전부 차례대로 지나가야 하기 때문입니다.
따라서 무작정 Integer.MAX_VALUE처럼 제일 큰 값 말고 int INF = 100000 * (N-1); 와 같이 INF를 설정 후 푸는 것이 좋을 것 같다.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[][] arr = new int[N+1][N+1];
for(int i = 1; i < N+1; i++) {
Arrays.fill(arr[i], -1); // 가중치 0이 있을수도 있으니 -1로 초기화
}
for(int i = 0; i < M; i++) {
int a = sc.nextInt();
int d = sc.nextInt();
int c = sc.nextInt();
// 시작 정점과 도착 정점이 같은데 비용이 다른 값이 들어올 수 있기 때문에 예외 처리
if(arr[a][d] == -1)
arr[a][d] = c;
else if(arr[a][d] > c)
arr[a][d] = c;
}
int start = sc.nextInt();
int end = sc.nextInt();
boolean[] check = new boolean[N+1]; // 정점이 집합 S에 속하는지 아닌지를 판별할 배열
int[] distance = new int[N+1]; // 최단 거리를 담을 배열
Arrays.fill(distance, Integer.MAX_VALUE-1); // 무한대로 초기화
distance[start] = 0;
for(int i = 0; i < N-1; i++) { // 시작점을 넣고 시작하기 때문에 N-1만큼만 반복
int min = Integer.MAX_VALUE;
int index = -1;
for(int j = 1; j < N+1; j++) { // 집합 S에 속하지 않는 가장 최단 거리를 갖는 정점 선택
if(!check[j] && distance[j] < min) {
min = distance[j]; // 최단 거리
index = j; // 최단 거리를 갖는 정점의 index
}
}
check[index] = true;
// S에 속하지 않는다면 더 작은 값을 갖는 거리로 distance값 갱신
for (int j = 1; j < N+1; j++) {
if (!check[j] && arr[index][j] != -1 && distance[index] + arr[index][j] < distance[j]) { // 간선이 연결되지 않은 -1의 경우 역시 제외해야함
distance[j] = distance[index] + arr[index][j];
}
}
}
System.out.println(distance[end]); // 도착점까지의 최단 거리 출력
}
}우선순위 큐로 구현한 다익스트라 알고리즘
위에서 설명한 다익스트라 알고리즘을 좀 더 효율적인 시간 복잡도로 구현하는 방법에 대해 알아보자.
먼저 위의 1916번 소스코드를 보면 distance 배열에서 거리가 최소가 되는 인덱스를 찾아,
인접해 있는 노드들의 distance값을 업데이트해주었다.
distance 배열 전체를 탐색하면서 최솟값을 찾았기 때문에 시간 복잡도가 N^2이 되는 것이다.
우선순위 큐를 사용한다면 시간 복잡도를 NlogN으로 줄일 수 있다.
또한 우선순위 큐를 사용할 때 인접 리스트를 이용하면 더더욱 시간을 줄일 수 있다.
왜냐하면 현재 정점에 연결된 간선들의 번호만 리스트에 저장되어 사용되기 때문에 훨씬 시간을 줄일 수 있는 것이다.
ex) 인접 행렬을 사용하게 되면 2만 개의 정점에 대해 2만 개 정점으로 가는 간선들을 저장해야 하는데,
간선 하나당 1바이트에 저장한다고 하더라도 4억 바이트, 약 400MB의 메모리를 쓰게 될 뿐 아니라
시간 복잡도 역시 O(V^2)으로 좋지 못하게 된다.
설명
구현 시 눈여겨봐야 할 포인트는 우선순위 큐로 구현할 시, 거리와 인덱스가 하나의 데이터형으로 입력되어야 한다는 것이다.
따라서 Element 클래스를 정의하고,
거리 정보를 오름차순으로 정렬해 최단 거리를 빠르게 구할 수 있도록,
클래스에 Comparable 인터페이스를 implements후, compareTo(object o) 메서드를 오버라이드 해 재정의해준다.
Element 클래스와 compareTo 메서드를 구현하는 내용을 빼면, BFS 탐색 방법과 동일하게 진행된다.
* Comparable 인터페이스를 구현한 객체 정렬에 대해 자세히 알고 싶다면 아래 블로그 포스트를 추천한다.
Java 객체 정렬 Comparable과 Comparator의 차이와 사용법
구현
백준 1753번 최단경로 문제를 바탕으로 구현 방법에 대해 세세하게 알아보자.
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
* 1753번 FAQ 참고 - www.acmicpc.net/board/view/34516
인접 리스트로 정점과 간선을 표현하고
최단 거리를 담기 위한 distance 배열, 정점에 방문했는지를 확인할 check 배열을 선언하는 것은 똑같다.
- 시작 정점 자신을 제외한 모든 정점까지의 거리를 무한대로 초기화한다.
- 시작 정점을 우선순위 큐에 삽입한다.
- 우선순위 큐에서 정점 하나를 꺼낸 후 해당 정점에서 갈 수 있는 모든 인접한 정점들을 확인한다.
- 3-1. 인접 정점까지의 거리가 이미 기록된 해당 정점까지의 거리보다 더 짧다면 거리 값을 갱신한다.
- 3-2. 이미 기록된 인접 정점까지의 거리가 더 짧다면 넘어간다.
- 3-1에서 거리 값이 갱신된 정점들을 우선순위 큐에 삽입한다.
- 우선순위 큐에 더 이상 정점이 없을 때까지 3~4번 과정을 반복한다.
코드
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
int E = sc.nextInt();
int start = sc.nextInt(); // 시작 정점
// 인접 리스트 구현
ArrayList<Element>[] adjList = new ArrayList[V+1];
for(int i = 1; i < V+1; i++) {
adjList[i] = new ArrayList<>();
}
for(int i = 0; i < E; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
adjList[u].add(new Element(v, w));
}
boolean[] check = new boolean[V+1];
int[] distance = new int[V+1];
int INF = 10 * (V-1) + 1; // INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 한다.
Arrays.fill(distance, INF);
distance[start] = 0;
PriorityQueue<Element> pq = new PriorityQueue<>();
pq.offer(new Element(start, 0));
while(!pq.isEmpty()) {
int current = pq.poll().index;
if(check[current]) continue;
check[current] = true;
for(Element next : adjList[current]) {
if(distance[next.index] > distance[current] + next.distance) {
distance[next.index] = distance[current] + next.distance;
pq.offer(new Element(next.index, distance[next.index]));
}
}
}
for(int i = 1; i < V+1; i++) {
if(distance[i] == INF)
System.out.println("INF");
else
System.out.println(distance[i]);
}
}
}
class Element implements Comparable<Element> {
int index;
int distance;
Element(int index, int distance) {
this.index = index;
this.distance = distance;
}
@Override
public int compareTo(Element o) {
//return this.distance <= o.distance ? -1 : 1;
return Integer.compare(this.distance, o.distance);
/*
Integer.compare(int x, int y)
x == y -> 0 return
x < y -> -1 return
x > y -> 1 return
*/
}
}코드2
우선순위 큐를 사용하지 않고 위의 1753번 코드를 인접 리스트와 기존 다익스트라 구현 코드를 사용해 풀이
(Scanner 사용시 시간 초과)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static class Edge {
int v;
int weight;
public Edge(int v, int weight) {
this.v = v;
this.weight = weight;
}
}
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());
int start = Integer.parseInt(br.readLine());
// 인접 리스트 구현
ArrayList<Edge>[] adjList = new ArrayList[V+1];
for(int i = 1; i < V+1; i++) {
adjList[i] = new ArrayList<>();
}
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());
adjList[u].add(new Edge(v, w));
}
boolean[] check = new boolean[V+1];
int[] distance = new int[V+1];
int INF = 10 * (V-1) + 1; // INF는 항상 (간선 가중치의 최댓값) * (정점 개수 - 1) 보다 큰 값을 사용해야 한다.
Arrays.fill(distance, INF);
distance[start] = 0;
for(int i = 0; i < V-1; i++) {
int min = Integer.MAX_VALUE;
int current = -1;
for(int j = 1; j < V+1; j++) {
if(!check[j] && distance[j] < min) {
min = distance[j];
current = j;
}
}
check[current] = true;
for(Edge next : adjList[current]) {
if(!check[next.v] && distance[current] + next.weight < distance[next.v]) {
distance[next.v] = distance[current] + next.weight;
}
}
}
for(int i = 1; i < V+1; i++) {
if(distance[i] == INF)
System.out.println("INF");
else
System.out.println(distance[i]);
}
}
}참고
C언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 생능 출판
최단경로 - (1) 다익스트라(Dijkstra) 알고리즘
알고리즘 Graph - 다익스트라 알고리즘(우선순위 큐 사용)
'Algorithm' 카테고리의 다른 글
| 정렬 Sort (0) | 2021.05.23 |
|---|---|
| [C & Java] Heap 힙 (0) | 2021.05.19 |
| 이진탐색 = 이분탐색 (Binary Search) - Java로 구현 (400) | 2021.02.06 |
| [Java] 트리 Tree 3 - 이진 탐색 트리 (0) | 2020.12.31 |
| [Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현 (13) | 2020.11.06 |
댓글