2020. 7. 2. 18:32ㆍJavascript/자료구조
1. 다익스트라 알고리즘
다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘이다. 최단거리 알고리즘의 사용 예시로 도시의 지도에서 출발지에서 목적지 사이의 거리 중 가장 짧은 거리를 찾는 네비게이션이나, 인공위성 GPS 소프트웨어 등이 있다. 다익스트라 알고리즘은 음의 간선을 포함할 수 없기 때문에 모든 가중치가 양수여야만 한다
다익스트라 알고리즘의 실행 순서는 다음과 같이 동작한다.
-
모든 꼭지점을 미방문 상태로 만든다.
-
시작 정점을 정한다(정점 A에서 탐색을 시작할 건지, 정점 B에서 시작할 건지 결정).
-
시작정점 A를 방문상태로 처리한다(시작 정점을 A라고 가정).
-
정점 A에 인접한 정점으로 가는 모든 거리 값을 기록한다.
-
정점 A에 각각의 인접 정점과 연결된 거리 중에서, 최단 거리를 갖는 정점을 찾는다(최소 가중치 탐색).
-
최단 거리를 갖은 경로를 통해 다음 정점으로 이동한다.
-
이동 거리를 기록한다.
-
다음 정점을 B라고 가정하면, 정점 B에 인접한 정점으로 가는 모든 거리 값에 이동거리를 더한 값(B에 인접한 각 정점들의 가중치 + 이동거리)과 (5)에서 기록한 최단거리 값을 서로 비교한다. 이때 최소 값을 갖는 거리를 기록한다.
-
정점 B를 방문상태로 처리한다.
-
모드 정점이 방문 상태가 될 때까지 (1)-(9) 과정을 반복한다.
다익스트라 알고리즘의 오리지날 버전은 최소 힙을 사용하지 않았기 때문에 O(N²)이라는 시간복잡도를 갖는다. 이때 N은 꼭지점의 개수이다. 그런데 최소 힙에 기반한 다익스트라 알고리즘의 시간 복잡도는 O(변의 개수 + Nlog₂N)이다. 따라서 이번 포스팅에서는 선형 탐색과 선형 자료 구조(배열)을 이용한 방식과 인접리스트와 최소 힙을 이용한 방식을 각각 다뤄보려고 한다.
2. 선형 자료 구조 + 선형 탐색을 이용한 다익스트라 알고리즘
이제 선형 자료 구조와 선형 탐색을 이용해서 구현한 다익스트라 알고리즘에 대해 설명하려고 한다. 밑에 [그림 1]은 이 방법을 위해 필요한 준비물이다.
각 준비물에 대한 설명은 다음과 같다.
-
그래프 G: 다익스트라 알고리즘을 이용할 무방향 가중치 그래프
-
선형 자료구조: 그래프의 정점 - 가중치 관계를 배열로 표현한 것
-
방문 처리: 각 정점의 방문 처리 여부를 나타내는 배열
-
최단 거리: 시작 정점에서 각 정점까지의 최단 거리 경로를 나타내는 배열
1. 먼저, 시작 정점을 A로 설정한다. 그 후 A를 방문처리 한 후, 선형 자료 구조에서 A를 참조하여 최단거리 배열에 복사한다. 그리고 최단 거리 배열 중에서 가장 적은 가중치를 가지고 있는 인덱스 2(C)를 선택한다.
2. C로 이동한 후 방문 처리한 후, 선형 자료구조 C를 참조한다.
3. 여태까지 A에서 C로만 이동을 했기 때문에, 이동거리는 1이다. 그렇기 때문에 C를 참조한 배열에
- 방문 처리를 하지 않은 정점
- 자기 자신을 제외한 모든 정점
두 가지 조건을 만족하는 모든 정점들의 가중치에 이동거리 1을 더한다. 그리고 최단거리 배열에 있는 요소와 인덱스별로 값을 비교한다. 그리고 둘 중에 더 작은 값을 최단 거리 배열에 복사한다. 비교는 방문 처리를 하지 않은 정점끼리만 하도록 한다.
4. 그러면 시작 정점 A에서 모든 노드로 가는 최단거리는 다음과 같다. 정점 C는 E와 연결되지 않았기 때문에 아직 E에 대한 최단거리는 무한(INF)다.
5. 이제 최단거리 배열에서 방문 하지 않은 노드 중 가장 작은 가중치를 갖고 있는 정점 D로 이동한 후 방문처리 한다.
6. 이제 모든 정점을 방문할 때 까지 1-5 과정을 반복한다. 방문 처리 배열의 값이 모두 True일 경우, 프로그램은 종료된다.
프로그램은 다음과 같다.
// 인접행렬 방식으로 구하기
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);
}());
3. 최소 힙을 이용한 다익스트라 알고리즘
이제 최소 힙을 이용한 다익스트라 알고리즘에 대해서 설명하려고 한다. 이번에는 선형 자료구조가 아닌 인접리스트를 이용하려고 한다. 선형 자료구조를 이용한 다익스트라 알고리즘은 정점을 인덱스화 시켜서 인접 정점의 가중치가 저장되어 있는 배열을 참조해서 비교를 했지만, 최소 힙을 이용하는 경우, 인접 정점, 가중치 두 개를 객체화 시켜서 최소 힙에 삽입하면 된다. 그리고 어차피 루트 노드에는 항상 최소 가중치를 가진 정점이 저장되어 있기 때문에 루트 노드 값을 빼서 방문처리를 한 후 다시 방문 중인 정점과 인접한 정점, 가중치를 객체화 시켜서 최소 힙에 삽입하는 과정을 모든 정점을 방문할때까지 반복한다. 설명에 수식어가 많아서 어려워할 수 있으니, 이해를 돕기 위해 단계별로 그림을 이용해서 설명을 하도록 하겠다. [그림 7]은 이 방법을 위해 필요한 준비물이다.
준비물에 대한 설명은 다음과 같다.
-
그래프 G: 다익스트라 알고리즘을 이용할 무방향 가중치 그래프
-
최단거리: 시작정점에서 현재 방문한 정점까지의 최단 이동거리를 저장하는 배열
-
최소 힙: (정점, 가중치) 객체를 저장할 최소 힙
-
방문 처리: 각 정점의 방문처리 여부를 나타내는 배열
1. 먼저, 시작 정점을 A로 설정한 후 방문처리 한다.(다른 것으로 해도 무방). 현재 이동한 거리는 0이므로, 최단거리 배열 인덱스 0(A)에 0을 삽입한다. 이제 A와 인접한 정점의 수 만큼 가중치, 정점 두 개의 속성을 가지고 있는 객체를 생성한다. 그리고 정점 속성에는 인접 정점데이터를 삽입하고, 가중치 속성에는 현재 정점 A까지 이동한 거리에 가중치를 더한 값(이동거리 + 가중치)을 삽입한다. 그리고 각 객체를 최소힙에 삽입한다. 이 때 주의할 점은, 삽입할 객체의 정점이 방문처리가 됐는지를 확인해야한다. 만약 방문이 되었을 경우, 최소 힙에 객체를 삽입하지 않는다.
2. 최소 힙을 pop(루트 노드에 있는 값만 뺌)한다.
3. 방금 빼낸 객체의 정점 속성의 값은 C이므로, 현재 방문 중인 정점은 C다. 전에 정점 C를 방문 했는지 검사한다. 방문이 안된 정점일 경우, C를 방문처리 해준다. 그리고 시작정점 A에서 현재 방문 중인 정점 C까지 이동한 거리(방금 빼낸 객체의 가중치 속성 값)는 1이므로, 최단 거리 배열 인덱스 2(C) 요소에 1(방금 빼낸 객체의 가중치 속성 값)을 삽입한다.
3. C와 인접한 정점의 수 만큼 정점, 가중치 속성을 가진 객체를 생성한다. 이때 정점에는 인접한 정점을 나타내는 데이터를 삽입하고, 가중치 속성에는 최단거리 배열의 인덱스 2(C)의 값에 가중치를 더한 값을 삽입한다. 그리고 객체의 정점의 방문처리 여부를 검사 후 최소 힙에 객체를 삽입한다.
4. 이제 최소 힙의 데이터가 하나도 없을 때까지 1-3 과정을 반복한다. 최소 힙의 길이가 0이되면 프로그램은 종료된다.
프로그램은 다음과 같다.
const Node = function(vertex, weight=0){
this.vertex = vertex;
this.weight = weight;
this.link = null;
}
const Graph = function(size){
this.graph = Array.from({length: size}, (e,i) => new Node(String.fromCharCode(65+i)));
const insertNode = (v1, v2, w) => {
const v1Node = new Node(v1, w);
const v2Node = new Node(v2, w);
const v1Idx = v1.charCodeAt(0) - 65;
const v2Idx = v2.charCodeAt(0) - 65;
let graph1 = this.graph[v1Idx];
let graph2 = this.graph[v2Idx];
if(graph1.link === null){
graph1.link = v2Node;
}
else{
while(graph1.link !== null){
graph1 = graph1.link;
}
graph1.link = v2Node;
}
if(graph2.link === null){
graph2.link = v1Node;
}
else{
while(graph2.link !== null){
graph2 = graph2.link;
}
graph2.link = v1Node;
}
return;
}
Graph.prototype.insertEdge = function(v1, v2, w){
insertNode(v1, v2, w);
}
Graph.prototype.printGraph = function(){
//간선 그래프 전체 출력
for(let i=0; i<size; i++){
let graph = this.graph[i];
let print = graph.vertex;
while(graph.link !== null){
graph = graph.link;
print += `--[${graph.weight}]--${graph.vertex}`;
}
console.log(print);
}
}
Graph.prototype.getGraph = function(){
return this.graph;
}
}
// 매개변수: 힙, 그래프, 이동거리(가중치), 방문여부
const heapPush = (h, g, move, isVisit) => {
// 다음 그래프가 null이 아닐 때 까지 검사
while(g.link !== null){
g = g.link; // 가중치 0(자기 자신)은 넣지 않는다.
// 방문 유무 검사 하기 위해서
let idx = g.vertex.charCodeAt(0) - 65;
// 방문 했을 경우, heap에 push하지 않는다.
if(!isVisit[idx]){
// g.weight + move: 여태 이동 가중치(move) + 현재 가중치를
// 더해준다. 나머지도 같다
if(!h.length) h.push({v:g.vertex, w:g.weight+move});
else{
if(h[0].w > g.weight){
let temp = h[0];
h[0] = {v:g.vertex, w:g.weight+move};
h.push(temp);
}
else{
h.push({v:g.vertex, w:g.weight+move});
}
}
}
}
}
const heapPop = (h) => {
//최소 힙 구하기!
const item = h[0];
const lastItem = h.pop();
let idx = 0;
if(!h.length) return item;
h[0] = lastItem;
// 자식 노드 유무 확인! 없으면 더 이상 검사 하지 않음!
while(h[idx*2+1] || h[idx*2+2]){
let temp = 0;
// 왼쪽 자식노드 검사
if(h[0].w > h[idx*2+1].w){
temp = h[0];
h[0] = h[idx*2+1];
h[idx*2+1] = temp;
idx = idx*2+1;
}
// 오른쪽 자식노드 검사!
else if(h[idx*2+2] && h[0].w > h[idx*2+2].w){
temp = h[0];
h[0] = h[idx*2+2];
h[idx*2+2] = temp;
idx = idx*2+2;
}
// 왼, 오른쪽 자식노드 둘 다 루트 노드보다 클 경우!
else
idx++;
}
return item;
}
const dijkstra = (start, graph) => {
const size = graph.length; // 정점 개수!
const isVisit = new Array(size).fill(false); // 정점 개수 만큼 방문처리 유무를 검사하기 위한 배열
const dist = []; // 거리 배열
const heap = []; // 힙
let move = 0; // 이동 가중치
let idx = start.charCodeAt(0) - 65; // 현재 인덱스
let g = graph[idx]; // 현재 그래프
heap.push({v:g.vertex, w:g.weight}); // 시작 그래프 노드 push
while(heap.length){
g = heapPop(heap); //최소 힙에서 루트노드(최솟 값) 꺼내기!
idx = g.v.charCodeAt(0) - 65; //방문 유무 검사하기 위한 인덱스
// 방문 되지 않은 정점에 대해서만 작업을 한다.
if(!isVisit[idx]){
isVisit[idx] = true;
move = g.w;
dist[idx] = move;
heapPush(heap, graph[idx], move, isVisit);
}
}
console.log(dist);
}
const main = (function(){
const graph = new Graph(6);
//간선 만들기
graph.insertEdge("A", "B", 1);
graph.insertEdge("A", "C", 9);
graph.insertEdge("B", "C", 10);
graph.insertEdge("B", "D", 2);
graph.insertEdge("C", "D", 5);
graph.insertEdge("C", "E", 1);
graph.insertEdge("D", "E", 1);
graph.insertEdge("E", "F", 2);
//간선 출력
console.log("간선 출력");
graph.printGraph();
//다익스트라 알고리즘 실행!
console.log("\nA의 최소 경로 출력")
dijkstra('A', graph.getGraph());
}());
4. 참고자료
'Javascript > 자료구조' 카테고리의 다른 글
| [JS] 타잔 알고리즘 (0) | 2020.07.09 |
|---|---|
| [JS] 위상 정렬 (0) | 2020.07.08 |
| [JS] 다이나믹 프로그래밍 (0) | 2020.06.29 |
| [JS] 이진 검색 (0) | 2020.06.26 |
| [JS] 순차검색 (0) | 2020.06.26 |