최단 경로(Shortest Path)
가장 짧은 경로를 찾는 알고리즘이다.
- 그리디 알고리즘 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다.
- 최단 경로 출력 문제 보다는 단순히 최단 거리 출력하는 문제가 많이 출제된다.
최단 거리 알고리즘 중 다익스트라 최단 경로 알고리즘을 설명한다.
다익스트라 최단 경로
그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
- 음의 간선(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작한다.
- 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택하기 때문이다.
알고리즘의 기본 원리
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 [3][4]번을 반복한다.
- Step 1: 출발인 1번 노드를 선택하고, 해당 노드를 거쳐 갈 수 있는 다른 노드들(2번과 3번)의 거리를 계산하여 갱신한다. 무한값 보다 작으므로 갱신된다.
- Step 2: : 방문하지 않은 노드 중 가장 짧은 최단거리 노드(2번)를 선택하고 해당 노드를 거쳐갈 수 있는 다른 노드의 최단 거리 값을 갱신한다.
노드 위의 식별값은 최단거리, 이전 노드로 표현되며, 방문한 적이 있는 노드는 더이상 갱신할 필요가 없어 * 표시를 한다.
- Step 3: 마찬가지로 3번 노드를 선택하여 반복
여기서 중요한점은 4번 노드의 최단거리는 2번 노드에 의해 13이었는데 이번 단계에서 3번 노드에 의해 12(4+8)로 갱신된다
이 과정을 계속 반복하면 결국 아래와 같은 결과와 최단거리 테이블을 얻을 수 있다.
구현 방법 2가지
- 간단한 다익스트라 알고리즘 - 구현하기 쉽지만 느리게 동작하는 코드
- 개선된 다익스트라 알고리즘 - 구현하기에 조금 까다롭지만 빠르게 동작하는 코드(정확히 이해하고 구현할 수 있어야 한다!!)
1. 간단한 다익스트라 알고리즘
- 시간복잡도: O(v2)
- 총 O(v) 번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색 X 현재 노드와 연결된 노드를 매번 일일이 확인
- 노드가 5000개 이하라면 풀 수 있지만, 10000개가 넘어가면 이 코드로는 해결하기 어렵다.
- 개선된 다익스트라 알고리즘 을 이용해야 한다.
class Node {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
public class Main {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
public static int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
public static boolean[] visited = new boolean[100001];
// 최단 거리 테이블 만들기
public static int[] d = new int[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
public static int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
public static void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph.get(start).size(); j++) {
d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance();
}
// 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph.get(now).size(); j++) {
int cost = d[now] + graph.get(now).get(j).getDistance();
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(j).getIndex()]) {
d[graph.get(now).get(j).getIndex()] = cost;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Node>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph.get(a).add(new Node(b, c));
}
// 최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
}2. 개선된 다익스트라 알고리즘
간단한 다익스트라 알고리즘은 '최단 거리가 짧은 노드'를 찾기 위해서, 매번 최단 거리 테이블을 선형적으로 탐색해야 했다. 그러나, 힙(heap) 자료구조를 이용하여 특정 노드의 최단 거리에 대한 정보를 찾는 개선된 다익스트라 알고리즘을 사용한다면 더욱 빠르게 찾을 수 있다. 이 과정에서 선형 시간이 아닌 로그 시간이 걸린다.
시간복잡도: 최악의 경우에도 O(ElogV) 보장 // V: 노드의 개수, E: 간선의 개수
- '현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인'하는 총횟수는 총 최대 간선의 개수(E)만큼 연산이 수행될 수 있다.
- 그렇다면 알고리즘은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사하다.
- 힙에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 과정은 O(NlogN) 이다.
- 힙(Heap)의 삽입시간: O(logN), 삭제시간: O(logN)
- [데이터 개수가 N이라면] 삽입때, O(logN) 연산을 N번 반복하므로 O(NlogN)이고 삭제도 마찬가지이다. 따라서 전체 연산 횟수는 대략 2NlogN으로 빅오 표기법에 따라 전체 시간 복잡도는 O(NlogN)이 된다.
- 최대 E개의 간선 데이터를 힙에 넣었다가 다시 빼는 것으로 볼 수 있으니, O(ElogE)가 되고, 이때 중복 간선을 포함하지 않는 경우, E는 항상 v2보다 작다. 왜냐하면, 모든 노드끼리 다 연결되어 있다 했을 때, 간선의 개수를 약 v2 이하로 볼 수 있다. 즉 logE는 logv2(2logV) 보다 작다.
- 따라서 전체 시간 복잡도는 O(ElogV)이다.
💡힙이란?
- 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나이다. 우선순위 큐란 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. (대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리를 지원하여, 힙 자료구조 부터 작성해서 우선순위 큐를 구현할 일은 없다)
- 우선순위 큐를 구현할 때는 내부적으로 최소 힙(Min Heap)혹은 최대 힙(Max Heap)을 이용한다. 최소 힙을 이용하는 경우 값이 낮은 데이터가 먼제 삭제되고, 최대 힙을 이용하는 경우 값이 큰 데이터가 먼저 삭제된다. Java에서는 기본적으로 최소 힙 구조를 이용한다.
- 최소 힙을 최대 힙처럼 사용하기 위해서 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가, 나중에 우선순위 큐에서 꺼낸 다음에 다시 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용할 수 있다.
- java에서 최대 힙 사용 코드 :
new PriorityQueue<>(Collections.reverseOrder());
public static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.offer(new Node(start, 0));
d[start] = 0;
while(!pq.isEmpty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
Node node = pq.poll();
int dist = node.getDistance(); // 현재 노드까지의 비용
int now = node.getIndex(); // 현재 노드
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph.get(now).size(); i++) {
int cost = d[now] + graph.get(now).get(i).getDistance();
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(i).getIndex()]) {
d[graph.get(now).get(i).getIndex()] = cost;
pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
}
}
}
}
열심히 달리는 개발자