이번에 배워볼 알고리즘은 그래프에서 최단 경로를 찾기 위한 알고리즘 중 하나인 다익스트라 알고리즘(Dijkstra Algorith)이다. 다익스트라 알고리즘은 한 정점에서 나머지 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 단, 그래프 내에 음의 간선(경로)이 존재한다면 다익스트라 알고리즘을 적용할 수가 없다.
다익스트라 알고리즘은 다이나믹 프로그래밍, 그리디 알고리즘으로 분류된다. 이전에 구했던 최단 경로 정보를 이용하기 때문에 다이나믹 프로그래밍이라고 불리며, 가장 최단 경로인 간선을 선택하기 때문에 그리디 알고리즘이라고 불린다.
다익스트라 알고리즘의 동작원리는 다음과 같다.
- 시작 정점을 선택한다.
- 시작 정점을 기준으로 다른 정점으로 가는 비용을 저장한다.
- 현재 방문하지 않는 정점들 중 가장 작은 비용을 가지는 정점을 선택한다.
- 시작 정점에서 다른 정점으로 가는 비용보다 선택한 정점을 거쳐서 가는 비용이 더 저렴하다면 갱신한다. 모든 정점을 방문할 때까지 3, 4번 과정을 반복하여 최단 경로를 갱신한다.
이전 DFS, BFS처럼 그래프 알고리즘은 글보다 그림으로 보는 것이 훨씬 수월하다. 다익스트라 알고리즘도 그림으로 이해해 보자.
간선들이 가중치를 가지는 무방향 그래프가 위 그림처럼 있다고 하자. 1번 정점을 시작 정점으로 설정하고 다른 정점까지의 최단 비용을 구하는 과정을 살펴보자.
간선들이 가중치를 가지는 무방향 그래프가 위 그림처럼 있다고 하자. 1번 정점을 시작 정점으로 설정하고 다른 정점까지의 최단 비용을 구하는 과정을 살펴보자.
1번 정점에서 다른 정점으로 가는 비용은 1차원 배열로 표현한다. 이때 자신에게 가는 비용은 0. 다른 정점으로 가는 비용은 갈 수 없다는 의미로 무한히 큰 수로 초기화한다. 나는 INF로 표현하겠다.
1번 정점을 선택하고 1번 정점에 연결된 간선으로 갈 수 있게된 2, 3, 4번 정점의 거리를 갱신해준다. 또한, 1번 정점을 방문했다는 표시를 해준다.
현재 방문하지 않은 정점들 중에서 최소 비용을 가지는 정점은 3번 정점이다. 3번 정점을 방문함으로써 6번, 7번 정점을 갈 수 있게 되었다. 기존에 알던 2, 4번 정점은 3번 정점을 통해 갈 수가 없기 때문에 갱신되지 않는다.
다음으로 4번 정점이 최소 비용을 가지기 때문에 4번 정점을 방문한다. 4번 정점을 거쳐서 5번 정점을 5+6=11의 비용으로 갈 수 있게 되었다.
또한, 기존에 정점으로 가는 비용들이 갱신이 된다. 첫 번째로 2번으로 가는 비용이 13이었지만 4번을 거쳐서 가게 되면 5+2=7의 비용으로 저렴하게 갈 수 있게 된다. 두 번째로 3번을 거쳐 6번으로 가는 비용 13보다 4번을 거쳐서 6번으로 가는 비용이 5+2=7의 비용으로 더 저렴하다. 이러한 원리로 모든 정점을 방문하면서 비용을 갱신하게 된다.
다음으로 2, 6번 정점이 최소 비용을 가진다. 나는 낮은 번호를 가지는 2번 정점을 방문하겠다. 2번을 방문하여도 갱신되는 경로는 없다.
다음으로 6번 정점을 방문한다. 기존의 1-4-5로 가는 11의 비용보다 1-4-6-5로 가는 비용이 10으로 더 저렴하기 때문에 갱신해 준다.
다음으로 7번 정점을 방문한다. 기존의 1-4-6-5로 가는 비용 10보다 1-3-7-5로 가는 비용이 9로 저렴하기 때문에 갱신한다.
마지막으로 5번 정점을 방문하면서 경로를 갱신한다.
최종적으로 다익스트라 알고리즘을 통해 시작 정점인 1번 정점에서 다른 정점들로 가는 최소 비용을 구하였다.
다익스트라 알고리즘을 Java로 구현한 코드는 다음과 같다.
class MyGraph {
final int INF = 987654321;
int N;
int[][] m;
int[] dist;
boolean[] visit;
public MyGraph(int N) {
this.N = N;
m = new int[N+1][N+1];
}
public void make_UndirectedEdge(int from, int to, int cost) {
m[from][to] = cost;
m[to][from] = cost;
}
public int findMinCostVertex() {
int minCost = INF;
int index = 0;
for (int i = 1; i <= N; ++i) {
if (!visit[i] && dist[i] < minCost) {
index = i;
minCost = dist[i];
}
}
return index;
}
public void dijkstra(int v) {
// 자기로 가는 비용 0, 갈수없는 비용 INF로 초기화
for (int i = 1; i <= N; ++i) {
for (int j = i+1; j <= N; ++j) {
if (m[i][j] == 0) {
m[i][j] = INF;
m[j][i] = INF;
}
}
}
// 방문 표시할 배열
visit = new boolean[N+1];
visit[v] = true;
// 최단 경로를 저장할 배열
dist = new int[N+1];
// 초기 비용 저장
for (int i = 1; i <= N; ++i) {
dist[i] = m[v][i];
}
// 1번 정점은 이미 방문했기 때문에 N-1개의 정점을 방문
for (int i = 0; i < N-1; ++i) {
// 방문하지 않은 정점들중 최소 비용을 가지는 정점을 찾음
int index = findMinCostVertex();
visit[index] = true;
for (int j = 1; j <= N; ++j) {
// 방문하지 않은 정점(방문한 정점에 인접한 간선들로는 이미 갱신하였음)들중
// 시작정점에서 j정점까지 가는 비용보다 시작정점에서 index정점을 거쳐 j정점까지 가는 비용이 저렴하다면 갱신
if (!visit[j]) {
if (dist[j] > dist[index] + m[index][j]) {
dist[j] = dist[index] + m[index][j];
}
}
}
}
for (int a = 1; a <= N; ++a) {
System.out.print(dist[a]==INF?"INF ":dist[a]+" ");
}
}
}
public class Blog {
public static void main(String[] args) {
MyGraph mg = new MyGraph(7);
mg.make_UndirectedEdge(1, 2, 13);
mg.make_UndirectedEdge(1, 3, 1);
mg.make_UndirectedEdge(1, 4, 5);
mg.make_UndirectedEdge(2, 4, 2);
mg.make_UndirectedEdge(2, 5, 4);
mg.make_UndirectedEdge(2, 7, 11);
mg.make_UndirectedEdge(3, 6, 12);
mg.make_UndirectedEdge(3, 7, 7);
mg.make_UndirectedEdge(4, 5, 6);
mg.make_UndirectedEdge(4, 6, 2);
mg.make_UndirectedEdge(5, 6, 3);
mg.make_UndirectedEdge(5, 7, 1);
mg.make_UndirectedEdge(6, 7, 8);
mg.dijkstra(1);
}
}
이렇게 구현한 다익스트라 알고리즘은 최소 비용을 가지는 정점을 찾기 위해서 N번 반복문을 돌아야 하기 때문에 O(N^2)의 시간 복잡도를 가진다.
최소 비용을 가지는 정점을 빠르게 찾아낼 수 있다면 더 효율적인 다익스트라 알고리즘을 구현할 수 있지 않을까? 다행히도 우리는 이전에 우선순위 큐라는 자료구조를 배웠음을 기억하라.
우선순위 큐는 힙 자료구조로 구현된 큐로 우선순위 조건에 맞는 데이터를 O(log N)이라는 빠른 시간에 뽑아낼 수 있는 훌륭한 자료구조였다. 최소 비용이라는 우선순위를 부여하여 우선순위 큐로 간선들을 관리한다면 O(N log N)이라는 시간 복잡도로 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있다.
우선순위 큐를 활용하여 구현한 다익스트라 알고리즘 코드는 다음과 같다. Edge라는 클래스를 선언하여 간선을 관리해 준다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
class MyGraph {
final int INF = 987654321;
int N;
int[] dist;
ArrayList<Edge>[] edgeList;
class Edge implements Comparable<Edge>{
int to, cost;
public Edge(int to, int cost) {
this.to = to;
this.cost = cost;
}
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
public MyGraph(int N) {
this.N = N;
edgeList = new ArrayList[N+1];
for (int i = 0; i <= N; ++i) {
edgeList[i] = new ArrayList<>();
}
}
public void make_UndirectedEdge(int from, int to, int cost) {
edgeList[from].add(new Edge(to, cost));
edgeList[to].add(new Edge(from, cost));
}
public void dijkstra_PriorityQueue(int v) {
// 최단 경로를 저장할 배열
dist = new int[N+1];
// 초기 비용 저장, 시작 정점을 제외한 나머지는 INF
Arrays.fill(dist, INF);
dist[v] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(v, 0));
// 우선순위 큐가 빈다면 더 이상 갱신이 가능한 정점이 없다.
while (!pq.isEmpty()) {
int to = pq.peek().to;
int cost = pq.poll().cost;
// v->to보다 현재 Edge의 비용이 더 비싸면 갱신할 필요가 없음
if (dist[to] < cost) continue;
for (int i = 0; i < edgeList[to].size(); ++i) {
Edge n = edgeList[to].get(i);
// v->n.to 비용보다 v->to->n.to로 가는 비용이 더 싸면
if (dist[n.to] > n.cost + cost) {
dist[n.to] = n.cost + cost;
pq.offer(new Edge(n.to, dist[n.to]));
}
}
}
for (int i = 1; i <= N; ++i) {
System.out.print(dist[i]+" ");
}
}
}
public class Blog {
public static void main(String[] args) {
MyGraph mg = new MyGraph(7);
mg.make_UndirectedEdge(1, 2, 13);
mg.make_UndirectedEdge(1, 3, 1);
mg.make_UndirectedEdge(1, 4, 5);
mg.make_UndirectedEdge(2, 4, 2);
mg.make_UndirectedEdge(2, 5, 4);
mg.make_UndirectedEdge(2, 7, 11);
mg.make_UndirectedEdge(3, 6, 12);
mg.make_UndirectedEdge(3, 7, 7);
mg.make_UndirectedEdge(4, 5, 6);
mg.make_UndirectedEdge(4, 6, 2);
mg.make_UndirectedEdge(5, 6, 3);
mg.make_UndirectedEdge(5, 7, 1);
mg.make_UndirectedEdge(6, 7, 8);
mg.dijkstra_PriorityQueue(1);
}
}'Computer Science > 알고리즘' 카테고리의 다른 글
| 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) (0) | 2021.07.03 |
|---|---|
| 벨만-포드 알고리즘(Bellman-Ford Algorithm) (0) | 2021.07.03 |
| 너비 우선 탐색(Breadth First Search) : BFS (0) | 2021.07.02 |
| 깊이 우선 탐색(Depth First Search) : DFS (1) | 2021.07.02 |
| Lower_bound & Upper_bound (0) | 2021.07.02 |
댓글