최단 경로 1) 다익스트라 알고리즘
다익스트라 알고리즘
다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용되는 알고리즘이다.
다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. 이때, 거리가 음수인 간선은 포함할 수 없다. 하지만, 현실 세계에서는 거리가 음수인 경로는 존재하지 않아서 다익스트라는 현실 세계에 적용하기 매우 적합한 알고리즘 중 하나이다.
다익스트라 알고리즘이 다이나믹 프로그래밍인 이유는 “최단 거리가 여러 개의 최단 거리”로 이루어져 있기 때문이다. 즉, 하나의 최단 거리를 구할 때, 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 것이다.
다익스트라 동작 원리
출발 노드 설정
최단 거리 테이블 초기화 (1차원 배열)
- 연결된 간선 → 그 값
- 연결되지 않은 간선 → 무한
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
해당 노드에서 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 최단 거리 테이블을 직접 갱신하지 않고, 우선순위 큐에 삽입하는 방식을 사용할 수도 있다.
모든 노드에 대해 3, 4번 반복
각 노드에 대한 현재까지의 최단 거리 정보를 1차원 배열에 저장하며 배열을 계속 갱신한다는 특징이 있으며, 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다는 점에서 그리디 알고리즘의 유형으로 볼 수 있다.
다익스트라 알고리즘의 오리지날 버전은 최소 힙을 사용하지 않았기 때문에 O(N²)이라는 시간복잡도를 갖는다. 이때 N은 꼭지점의 개수이다.
그런데 최소 힙에 기반한 다익스트라 알고리즘의 시간 복잡도는 O(변의 개수 + Nlog₂N)이다.
따라서 이번 포스팅에서는 선형 탐색과 선형 자료 구조(배열)을 이용한 방식과 인접리스트와 최소 힙을 이용한 방식을 각각 다뤄보려고 한다.
선형 자료 구조 + 선형 탐색을 이용한 다익스트라 알고리즘
동작 과정
그래프 G: 다익스트라 알고리즘을 이용할 무방향 가중치 그래프
선형 자료구조: 그래프의 정점 - 가중치 관계를 배열로 표현한 것
방문 처리: 각 정점의 방문 처리 여부를 나타내는 배열
최단 거리: 시작 정점에서 각 정점까지의 최단 거리 경로를 나타내는 배열
먼저, 시작 정점을 A로 설정한다. 그 후 A를 방문처리 한 후, 선형 자료 구조에서 A를 참조하여 최단거리 배열에 복사한다. 그리고 최단 거리 배열 중에서 가장 적은 가중치를 가지고 있는 인덱스 2(C)를 선택한다.
C로 이동한 후 방문 처리한 후, 선형 자료구조 C를 참조한다.
여태까지 A에서 C로만 이동을 했기 때문에, 이동거리는 1이다. 그렇기 때문에 C를 참조한 배열에 아래의 2가지 조건을 만족하는 모든 정점들의 가중치에 이동거리 1을 더한다.
조건
- 방문 처리를 하지 않은 정점
- 자기 자신을 제외한 모든 정점
최단거리 배열에 있는 요소와 인덱스별로 값을 비교한다. 그리고 둘 중에 더 작은 값을 최단 거리 배열에 복사한다. 비교는 방문 처리를 하지 않은 정점끼리만 하도록 한다.
그러면 시작 정점 A에서 모든 노드로 가는 최단거리는 다음과 같다. 정점 C는 E와 연결되지 않았기 때문에 아직 E에 대한 최단거리는 무한(INF)다.
이제 최단거리 배열에서 방문 하지 않은 노드 중 가장 작은 가중치를 갖고 있는 정점 D로 이동한 후 방문처리 한다.
이제 모든 정점을 방문할 때 까지 1-5 과정을 반복한다. 방문 처리 배열의 값이 모두 True일 경우, 프로그램은 종료된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 인접행렬 방식으로 구하기
const INF = Infinity;
const arr = [
[0, 2, 5, 1, INF, INF],
[2, 0, 3, 2, INF, INF],
[5, 3, 0, 3, 1, 5],
[1, 2, 3, 0, 1, INF],
[INF, INF, 1, 1, 0, 2],
[INF, INF, 5, INF, 2, 0]
];
const isVisit = new Array(6).fill(false);
const getMin = function (vertex) {
let min = INF;
let idx = 0;
for (let i = 0; i < vertex.length; i++) {
if (min > vertex[i] && !isVisit[i]) {
min = vertex[i];
idx = i;
}
}
return idx;
};
const dist = function (start) {
let v = arr[start - 1];
let count = 0;
let end = v.length;
let min = 0;
let startV = v;
isVisit[start - 1] = true;
while (count < end) {
const idx = getMin(startV);
min += startV[idx];
const next = arr[idx];
for (let i = 0; i < v.length; i++) {
if (v[i] > next[i] + min && !isVisit[i]) v[i] = next[i] + min;
}
startV = arr[idx];
isVisit[idx] = true;
count++;
}
console.log(v);
};
const main = (function () {
dist(1);
})();
최소 힙을 이용한 다익스트라 알고리즘
동작 과정
그래프 G: 다익스트라 알고리즘을 이용할 무방향 가중치 그래프
최단거리: 시작정점에서 현재 방문한 정점까지의 최단 이동거리를 저장하는 배열
최소 힙: (가중치, 노드) 객체를 저장할 최소 힙
먼저, 시작 노드을 1로 설정한 후 방문처리 한다.(다른 것으로 해도 무방). 현재 이동한 거리는 0이므로, 최단거리 배열 인덱스 0(1)에 0을 삽입한다.
이제 1와 인접한 노드의 수 만큼 가중치, 노드 두 개의 속성을 가지고 있는 객체를 생성한다. 그리고 노드 속성에는 인접 노드를 삽입하고, 가중치 속성에는 현재 정점 1까지 이동한 거리에 가중치를 더한 값(이동거리 + 가중치)을 삽입한다.
그리고 각 객체를 최소힙에 삽입한다. 이 때 주의할 점은, 삽입할 객체의 정점이 방문처리가 됐는지를 확인해야한다. 만약 방문이 되었을 경우, 최소 힙에 객체를 삽입하지 않는다. (가중치의 값이 작을수록 최소 힙의 위쪽에 위치한다.)
최소 힙을 pop(루트 노드에 있는 값을 꺼낸다.)한다.
방금 빼낸 객체의 노드 속성의 값은 3이므로 전에 정점 3를 방문 했는지 검사한다. 방문이 안된 정점일 경우, 3를 방문처리 해준다.
그리고 시작노드 1에서 현재 방문 중인 정점 3까지 이동한 거리(방금 빼낸 객체의 가중치 속성 값)는 1이므로, 최단 거리 배열 인덱스 2(3) 요소에 1(방금 빼낸 객체의 가중치 속성 값)을 삽입한다.
3와 인접한 노드의 수 만큼 노드, 가중치 속성을 가진 객체를 생성한다. 가중치 속성에는 최단거리 배열의 인덱스 2(3)의 값에 가중치를 더한 값을 삽입한다. 그리고 객체의 정점의 방문처리 여부를 검사 후 최소 힙에 객체를 삽입한다.
방금 빼낸 객체의 노드 속성의 값은 4이므로 전에 정점 4를 방문 했는지 검사한다. 방문이 안된 정점일 경우, 4를 방문처리 해준다.
시작노드 1에서 현재 방문 중인 정점 4까지 이동한 거리(방금 빼낸 객체의 가중치 속성 값)는 2이므로, 최단 거리 배열 인덱스 3(4) 요소에 2(방금 빼낸 객체의 가중치 속성 값)을 삽입한다.
4와 인접한 노드의 수 만큼 노드, 가중치 속성을 가진 객체를 생성한다. 가중치 속성에는 최단거리 배열의 인덱스 3(4)의 값에 가중치를 더한 값을 삽입한다. 그리고 객체의 정점의 방문처리 여부를 검사 후 최소 힙에 객체를 삽입한다.
이제 최소 힙의 데이터가 하나도 없을 때까지 1-3 과정을 반복한다. 최소 힙의 길이가 0이되면 프로그램은 종료된다.
소스 코드
JavaScript는 기본적으로 우선순위 큐를 라이브러리로 제공하지 않는다.
• 최단 경로 알고리즘 등에서 힙(heap)이 필요한 경우 별도의 라이브러리를 사용해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
let INF = Infinity;
let n = 7; // 노드의 개수
let start = 1; // 시작 노드 번호
let distance = new Array(n + 1).fill(INF); // 최단 거리 테이블을 모두 무한으로 초기화
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
let graph = [
// 각 간선은 [노드, 비용] 형태
[],
[
[2, 3],
[3, 1],
[4, 2]
], // 1 번 노드의 간선들
[
[1, 3],
[3, 1],
[5, 1]
], // 2 번 노드의 간선들
[
[1, 1],
[2, 1],
[4, 3],
[6, 5]
], // 3번 노드의 간선들
[
[1, 2],
[3, 3],
[7, 1]
], // 4번 노드의 간선들
[
[2, 1],
[6, 2]
], // 5번 노드의 간선들
[
[3, 5],
[5, 2]
], // 6번 노드의 간선들
[[4, 1]] // 7번 노드의 간선들
];
function dijkstra() {
// 다익스트라(Dijkstra) 알고리즘 수행
let pq = new PriorityQueue((a, b) => b[0] - a[0]); // 최소힙(Min Heap)
// 시작 노드로 가기 위한 최단 거리는 0으로 우선순위 큐에 삽입
pq.enq([0, start]);
distance[start] = 0;
while (pq.size() != 0) {
// 우선순위 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
let [dist, now] = pq.deq();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (distance[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (let i of graph[now]) {
let cost = dist + i[1];
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < distance[i[0]]) {
distance[i[0]] = cost;
pq.enq([cost, i[0]]);
}
}
}
}
// 다익스트라 알고리즘을 수행
dijkstra();
// 모든 노드로 가기 위한 최단 거리를 출력
for (let i = 1; i <= n; i++) {
// 도달할 수 없는 경우 무한(INFINITY)이라고 출력
if (distance[i] == INF) console.log("INFINITY");
// 도달할 수 있는 경우 거리를 출력
else console.log(distance[i]);
}
다익스트라 문제 예제
예제) Baekjoon 1753 - 최단경로
💡 문제 확인
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
💡 최단경로 문제의 해법
한 지점에서 다른 모든 지점까지의 최단 경로를 구하는 문제로 다익스트라 알고리즘을 사용할 수 있다.
💡 최단경로 문제 해결 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
let INF = 1e9;
let node = 5;
let start = 1;
let distance = Array(5).fill(INF);
let graph = [
// [node, distance]
0,
[
[5, 1],
[2, 2],
[3, 3]
],
[
[1, 2],
[3, 4],
[4, 5]
],
[
[1, 3],
[2, 4],
[4, 6]
],
[
[2, 5],
[3, 6]
],
[[1, 1]]
];
function dijkstra() {
let pq = new PriorityQueue((a, b) => b[0] - a[0]);
pq.enq([0, start]);
distance[start] = 0;
while (pq.size() !== 0) {
let [dis, node] = pq.deq();
if (distance[node] < dis) continue;
for (let i of graph[node]) {
let cost = dis + i[1];
if (cost < distance[i[0]]) {
distance[i[0]] = cost;
pq.enq([cost, i[0]]);
}
}
}
}
dijkstra();
for (let i = 1; i <= node; i++) {
if (distance[i] == INF) console.log("INF");
else console.log(distance[i]);
}
📑 참고 자료