개요
안녕하세요. J4J입니다.
이번 포스팅은 다익스트라 알고리즘에 대해 적어보는 시간을 가져보려고 합니다.
다익스트라 알고리즘이란?
다익스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 탐색하기 위해 사용되는 알고리즘 기법으로 시작 정점에서부터 다른 정점들까지 도달하기 위해 필요한 최소 거리를 찾기 위해 사용됩니다.
다익스트라를 이용해 최단 경로를 구하는 식은 D[i][j] = min(D[i][j], D[i][k] + D[k][j])이고 이를 이용해 최단 경로를 구하는 방법은 다음과 같습니다.
예를 들어 A, B, C, D, E 정점이 있고 정점들 사이의 거리는
A ↔ C 거리: 3
A ↔ D 거리: 5
B ↔ C 거리: 4
B ↔ D 거리: 4
C ↔ E 거리: 2
D ↔ E 거리: 1
이며 A정점이 시작 정점이라고 한다면 다음과 같은 순서로 최단 경로를 탐색합니다.
1-1. A에서 갈 수 있는 정점과 거리를 확인합니다. (C: 3, D: 5)
1-2. 갈 수 있는 정점 중 최소 거리를 가지는 C정점을 방문합니다. (방문 A, C)
2-1. C에서 갈 수 있는 정점과 거리를 확인합니다. (A: 3, B: 4, E: 2)
2-2. 각 정점까지의 거리와 C까지 도달하기 위한 최소 거리(3)를 더합니다. (A: 6, B: 7, E: 5)
2-3. 이전에 방문했던 정점들의 최소치와 비교하여 방문하지 않은 정점들의 최소 거리를 확인합니다. (B: 7, D: 5, E: 5)
2-4. 갈 수 있는 정점 중 최소 거리를 가지는 D정점을 방문합니다. (방문 A, C, D)
3-1. D에서 갈 수 있는 정점과 거리를 확인합니다. (A: 5, B: 4, E: 1)
3-2. 각 정점까지의 거리와 D까지 도달하기 위한 최소 거리(5)를 더합니다. (A: 10, B: 9, E: 6)
3-3. 이전에 방문했던 정점들의 최소치와 비교하여 방문하지 않은 정점들의 최소 거리를 확인합니다. (B: 7, E: 5)
3-4. 갈 수 있는 정점 중 최소 거리를 가지는 E정점을 방문합니다. (방문 A, C, D, E)
4-1. E에서 갈 수 있는 정점과 거리를 확인합니다. (C: 2, D: 1)
4-2. 각 정점까지의 거리와 E까지 도달하기 위한 최소 거리(5)를 더합니다. (C: 7, D: 6)
4-3. 이전에 방문했던 정점들의 최소치와 비교하여 방문하지 않은 정점들의 최소 거리를 확인합니다. (B: 7)
4-4. 갈 수 있는 정점 중 최소 거리를 가지는 B정점을 방문합니다. (방문 A, C, D, E, B)
5-1. 더 이상 방문할 수 있는 정점이 존재하지 않아 실행이 종료됩니다.
그림 예시
위의 순서와 동일한 상황을 그림으로 표현해보겠습니다. (A: 0, B: 1, C: 2, D: 3, E: 4)
구현 코드 - 인접 행렬 (Java)
package shortest;
public class DijkstraArray {
public static void main(String[] args) {
int N = 5; // 정점의 갯수
int graph[][] = new int[N][N]; // 정점 간 거리 저장
boolean visited[] = new boolean[N]; // 정점 방문여부
int minDistance[] = new int[N]; // 정점에 도착할 수 있는 최소 거리 저장
init(graph, minDistance); // 초기화, graph의 모든 간선과 정점 간 거리를 모두 정수 최대값으로 초기화
// 정수 최대값인 경우는 길이 없다는 것을 의미
// 길(간선) 추가
add(0, 2, 3, graph);
add(0, 3, 5, graph);
add(1, 2, 4, graph);
add(1, 3, 4, graph);
add(2, 4, 2, graph);
add(3, 4, 1, graph);
int index = 0; // 시작 정점
minDistance[index] = 0;
while(index != -1) { // 다음 정점을 찾지 못할 때까지 순환
visited[index] = true; // 방문 체크
for(int i=0; i<N; i++) {
if(!visited[i] && graph[index][i] != Integer.MAX_VALUE) { // 아직 방문한지 않았거나 현재 정점에서 길이 있는 정점일 경우
minDistance[i] = Math.min(minDistance[i], minDistance[index] + graph[index][i]); // (저장되어 있는 최솟값)과 (index까지의 최솟값과 index부터 i번째까지 거리의 합)을 비교
}
}
index = -1; // 아래 for문을 지나도 index가 -1일 경우 갈 수 있는 다음 정점이 없음
for(int i=0; i<N; i++) {
if(!visited[i] && minDistance[i] != Integer.MAX_VALUE) { // 아직 방문하지 않았거나 최솟값이 존재할 경우
if(index == -1) { // 초기 저장
index = i;
} else {
if(minDistance[index] > minDistance[i]) { // index의 최솟값보다 i번째가 더 작을 경우
index = i;
}
}
}
}
}
for(int i=0; i<N; i++) {
System.out.println(i + "번 정점까지의 최소 거리: " + minDistance[i]);
// 0번 정점까지의 최소 거리: 0
// 1번 정점까지의 최소 거리: 7
// 2번 정점까지의 최소 거리: 3
// 3번 정점까지의 최소 거리: 5
// 4번 정점까지의 최소 거리: 5
}
}
public static void add(int v, int u, int distance, int graph[][]) { // 가중치 추가
graph[u][v] = graph[v][u] = distance;
}
public static void init(int graph[][], int minDistance[]) { // 값 초기화
int N = graph.length;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
graph[i][j] = Integer.MAX_VALUE;
}
}
for(int i=0; i<N; i++) {
minDistance[i] = Integer.MAX_VALUE;
}
}
}
시간 복잡도 - 인접 행렬
인접 행렬로 구현된 다익스트라 알고리즘의 시간 복잡도는 O(N^2)입니다.
while문 내부를 N만큼 순회하고 while문 내부에 있는 for문을 N만큼 순회하므로 N x N = N^2이라는 시간 복잡도가 나옵니다.
구현 코드 - 힙 (Java)
package shortest;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class DijkstraHeap {
public static void main(String[] args) {
int N = 5; // 정점의 갯수
List<Node> graph[] = new List[N];
for(int i=0; i<N; i++) {
graph[i] = new ArrayList<Node>();
}
int minDistance[] = new int[N]; // 정점에 도착할 수 있는 최소 거리 저장
init(minDistance); // 초기화, graph의 모든 간선과 정점 간 거리를 모두 정수 최대값으로 초기화
// 정수 최대값인 경우는 길이 없다는 것을 의미
// 길(간선) 추가
add(0, 2, 3, graph);
add(0, 3, 5, graph);
add(1, 2, 4, graph);
add(1, 3, 4, graph);
add(2, 4, 2, graph);
add(3, 4, 1, graph);
// 힙으로 구현된 우선순위 큐
PriorityQueue<Node> pqueue = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.distance - o2.distance;
}
});
pqueue.add(new Node(0, 0)); // 0번 정점을 방문하기 위해 필요한 거리는 0
while(!pqueue.isEmpty()) {
Node node = pqueue.poll(); // 큐의 첫 번째 노드 가져오기
if(minDistance[node.vertext] == Integer.MAX_VALUE) { // 방문한적이 없는 정점일 경우
minDistance[node.vertext] = node.distance; // 최소거리 저장
for(int i=0; i<graph[node.vertext].size(); i++) { // 해당 정점에 연결된 길(간선) 순회
Node nextNode = graph[node.vertext].get(i);
if(minDistance[nextNode.vertext] == Integer.MAX_VALUE) { // 연결되어 있는 정점을 방문한적이 없는 경우
pqueue.add(new Node(nextNode.vertext, node.distance + nextNode.distance)); // 현재까지 온 거리에 다음 정점 방문하기 위해 필요한 거리를 저장
}
}
}
}
for(int i=0; i<N; i++) {
System.out.println(i + "번 정점까지의 최소 거리: " + minDistance[i]);
// 0번 정점까지의 최소 거리: 0
// 1번 정점까지의 최소 거리: 7
// 2번 정점까지의 최소 거리: 3
// 3번 정점까지의 최소 거리: 5
// 4번 정점까지의 최소 거리: 5
}
}
public static void add(int v, int u, int distance, List<Node> graph[]) { // 가중치 추가
graph[u].add(new Node(v, distance));
graph[v].add(new Node(u, distance));
}
public static void init(int minDistance[]) { // 값 초기화
int N = minDistance.length;
for(int i=0; i<N; i++) {
minDistance[i] = Integer.MAX_VALUE;
}
}
private static class Node { // vertex를 방문하기 위해 필요한 거리는 distance
int vertext;
int distance;
public Node(int vertext, int distance) {
this.vertext = vertext;
this.distance = distance;
}
}
}
시간 복잡도 - 힙
힙으로 구현된 다익스트라 알고리즘의 시간 복잡도는 O(ElogN)입니다.
여기서 E는 길(간선)의 개수의 총합을 의미합니다.
while문 내부를 N만큼 순회하고 while문 내부에 있는 for문을 각 정점마다 연결되어 있는 길(간선)의 개수만큼 순회하기 때문에 (N x 정점마다 연결되어 있는 길(간선)의 개수)의 총합인 E만큼 시간이 사용됩니다.
그리고 for문 내부에 있는 우선순위 큐에 저장할 때 logN만큼의 시간이 사용됩니다.
결과적으로 E만큼 순회할 때마다 logN만큼의 시간이 추가적으로 필요하기 때문에 E x logN = ElogN이라는 시간 복잡도가 나옵니다.
정리
이상으로 다익스트라 알고리즘에 대해 간단하게 알아보는 시간이었습니다.
읽어주셔서 감사합니다.
'Algorithm > Algorithm' 카테고리의 다른 글
| [Algorithm] 최단 경로 탐색(Shortest Path) - 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) (0) | 2021.02.01 |
|---|---|
| [Algorithm] MST - 크루스칼 알고리즘(Kruskal Algorithm) (0) | 2021.01.30 |
| [Algorithm] MST - 프림 알고리즘(Prim Algorithm) (0) | 2021.01.27 |
| [Algorithm] 최소 신장 트리(MST, Minimum Spanning Tree) (0) | 2021.01.24 |
| [Algorithm] 너비 우선 탐색(BFS, Breadth First Search) (0) | 2021.01.21 |
댓글