다익스트라 알고리즘은 출발 노드 한 지점을 기준으로 다른 모든 노드로 가는 각각의 최단거리를 계산하는 알고리즘이다.다익스트라 알고리즘은 다음과 같은 과정을 반복한다.
출발 지점을 지정한다.
그래프에서 현재 노드에서 갈 수 있는 경로 중 가장 거리가 짧은 노드를 선택한다.
해당 노드를 거친 거리가 기존 노드의 최단거리 보다 짧다면 최단거리를 갱신한다.
이후 반복
3번 과정으로 인해 다익스트라 알고리즘은 일종의 그리디 알고리즘으로 분류되기도 한다.위와 같이 노드 5개, 간선 7개를 가진 그래프가 존재한다는 상황에서 알아가보자.
출발 지점 지정 및 초기화
각 노드의 최단거리의 기준이 될 출발 지점을 1로 지정한다.이때 거리 테이블을 [0, Infinity, Infinity, Infinity, Infinity]와 같이 도달할 수 없다는 의미의 Infinity로 출발 지점을 제외한 노드에 초기화한다.
현재 노드에서 갈 수 있는 가장 짧은 노드를 선택
이제 현재 노드의 방문 가능 노드를 추린다.1 노드에서 다른 노드로 갈 수 있는 경로는 2, 3, 5가 존재한다.
현재 해당 노드들의 최단거리는 Infinity이므로 최단거리를 갱신하여 방문처리한다.그리고 가장 가까운 노드인 3 노드에 방문한다.이후 똑같이 3 노드에서 가능한 경로를 탐색한다.4 노드의 경우 기존 최단거리인 Infinity보다 3의 최단거리(2) + 3에서 4로 가는 거리(1) = 3가 더 낮으므로 값을 갱신한다.5 노드의 경우도 기존 최단거리인 5보다 3의 최단거리(2) + 3에서 5로 가는 거리(2) = 5가 더 낮으므로 값을 갱신한다.이후 4 노드는 방문 가능한 노드가 없으므로 넘어간다.
나머지 2 => 5, 5 => 4 노드의 그래프도 확인하지만 해당 경우는 기존 최단거리보다 짧지 않으므로 값을 갱신하지 않는다.위 과정을 반복하면 출발 노드 1에 대한 나머지 노드의 최단 거리를 계산할 수 있다.
코드로 보기
1const graph =Array.from({length: n +1},()=>[]);2const d =Array.from({length: n +1},()=>Infinity);34for(const v of arr){5const[from, to, dist]= v;6 graph[from].push([to, dist]);7}89const queue =[];10queue.push([start,0]);11d[start]=0;1213while(queue.length!==0){14const[curNode, dist]= queue.pop();1516if(d[curNode]< dist)continue;1718for(const v of graph[curNode]){19const node = v[0];20const cost = dist + v[1];2122if(cost < d[node]){23 queue.push([node, cost]);24 queue.sort((a, b)=> a[1]- b[1]);25 d[node]= cost;26}27}28}29
그림 백장보다 코드 열줄이 더 이해하기 편하니 코드로 확인해보자. 위 코드를 조각조각 쪼갠다면 다음과 같다.
1const graph =Array.from({length: n +1},()=>[]);2const d =Array.from({length: n +1},()=>Infinity);3
graphgraph는 인덱스마다 각각의 노드를 가지는 이차원 배열이다.dd는 현재 각 노드의 최단 거리를 저장하는 배열이며 초깃값으로 Infinity를 가진다.
1for(const v of arr){2const[from, to, dist]= v;3 graph[from].push([to, dist]);4}5
주어진 입력값을 바탕으로 그래프를 초기화한다.
참고로 해당 코드는 단방향 간선을 기준으로 구현되었다!
만약 무방향 간선이라면 역방향에도 경로를 추가하는 것을 잊지 말자.
이후 방문 노드 목록을 저장할 큐를 하나 생성해주자.
그리고 출발 지점에 대한 초기화를 실행한다.만약 출발 지점이 1이라면 queue[1]의 경우 최단거리는 당연히 0 일테니 해당 값으로 초기화 하고 방문 노드에 [출발 노드, 0]을 삽입하여 출발 지점부터 탐색을 시작하도록 한다.
이후 큐에서 가장 짧은 거리를 가진 방문 노드를 꺼낸다.
이때, 만약 현재 최단 거리보다 꺼내온 방문 노드의 거리가 더 길다면 스킵한다.이유는 간단한다. 가져온 방문 노드가 기존 거리보다 더 길다면 해당 노드에서 어떤 값을 더해봤자 최단 거리를 갱신할 수 있는 경우의 수는 존재하지 않기 때문이다.물론 음수는 제외한다! 이는 다익스트라 알고리즘이 음수 가중치 간선이 존재하는 경우 사용이 불가능한 이유이기도 하다.
그리고 가져온 가장 가까운 노드가 방문 가능한 노드를 탐색한다.
이때 기존 노드의 최단거리(dist) + 가져온 노드에서 목표 노드의 거리(v[1])이 목표 노드의 기존 최단거리보다 짧을 경우 최단거리를 갱신한다. 그리고 큐에 [타켓 노드, 방금 갱신된 최단거리]를 삽입하여 위 과정을 반복하도록 한다.이때 정렬을 통하여 이후 과정이 반복되더라도 pop()으로 가장 가까운 노드를 반환하도록 설정한다.하지만 이때, 정렬로 인해서 시간 복잡도에 문제가 생기게 된다.
반복된 정렬로 인해 발생하는 비용
위에서도 볼 수 있다시피 가장 가까운 노드를 가져오기 위해서 sort 메서드를 활용해 정렬을 수행한다. 하지만 정렬을 반복적으로 실행할 경우 성능상 문제는 더욱 커진다. 만약 현재 큐에서 정렬해야할 노드가 몇만개라면...? 방문해야하는 노드의 개수가 늘어날수록 정렬에서 걸리는 시간과 메모리 또한 기하급수적으로 늘어날 것이다. 이러한 현상을 해결하기 위해서 우선순위 큐라는 자료구조를 사용해야한다.
우선순위 큐(Priority Queue)
비로소 큐라고 한다면 먼저 들어온 요소가 먼저 나가는, 즉 **선입선출(FIFO, First In Fist Out)**의 원칙을 지키는 것이 도리이다. 하지만 우선순위 큐의 경우 먼저 들어온 것과는 상관이 없이 정해놓은 우선순위에 따라서 값을 반환한다.그래서 우선순위 큐를 어떻게 구현하냐? 여기서 힙이라는 자료구조가 등장한다.
힙(Heap)이란?
힙(Heap)이란 (완전 이진 트리(Complete Binary Tree))[https://www.geeksforgeeks.org/complete-binary-tree/]로 이루어진 자료구조이다.예를 들어 최소 힙의 경우 모든 부모 노드는 자식 노드보다 값이 작거나 같고,
최대 힙의 경우 모든 부모 노드는 자식 노드보다 값이 크거나 같다.따라서 힙에 특정 값을 추가하더라도 이진 탐색을 통해 값을 분류할 수 있게되니 이진 탐색의 시간 복잡도인 O(log n)와 동일하다.
그래서 자바스크립트에서 힙을 어떻게 쓰죠?
Java, C++의 경우 PriorityQueue가 제공되며 Python의 경우 heapq, heapify가 존재한다.???: 그렇다면 자바스크립트에서는 어떻게 쓰면 되나요?하지만 자바스크립트에는 내장 힙 관련 라이브러리가 없다.
즉 직접 손수 맹글어 쓰라 이 말이다.어쩔 수 있나 지름길이 없다면 자갈밭을 걸을 수 밖에 없다.최소 힙을 자바스크립트로 직접 구현해보자.
자바스크립트로 최소 힙 만들기
1classPriorityQueue{2constructor(){3this.heap=[];4}56size(){7returnthis.heap.length;8}910swap(idx1, idx2){11[this.heap[idx1],this.heap[idx2]]=[this.heap[idx2],this.heap[idx1]];12}1314push(data){15if(this.size()===0){16this.heap.push(data);17return;18}1920this.heap.push(data);21let checkedIdx =this.heap.length-1;2223while(checkedIdx >0){24let parentIdx =Math.floor((checkedIdx -1)/2);25if(this.heap[parentIdx][1]>this.heap[checkedIdx][1]){26this.swap(parentIdx, checkedIdx);27 checkedIdx = parentIdx;28}else{29break;30}31}32}3334pop(){35if(this.size()===0)return;36if(this.size()===1)returnthis.heap.pop();3738const value =this.heap[0];39this.heap[0]=this.heap.pop();40let currentIdx =0;4142while(currentIdx <this.size()){43let left = currentIdx *2+1;44let right = left +1;4546if(!this.heap[left])break;4748let smaller =this.heap[right]!==undefined?(this.heap[left][1]<=this.heap[right][1]? left : right): left;4950if(this.heap[smaller][1]<this.heap[currentIdx][1]){51this.swap(smaller, currentIdx);52 currentIdx = smaller;53}else{54break;55}56}5758return value;59}60}61
힙의 요소를 컨트롤하는데에는 Node 클래스를 만들 수도 있지만 배열을 사용해도 인덱스를 통해 트리 형태로 구조화가 가능하니 배열을 사용한다.메서들을 설명하자면 empty는 힙의 길이를 반환하고, swap은 인자로 받은 두 인덱스의 위치를 변경한다. 핵심 메서드는 push와 pop에 존재한다.
그림을 보면 부모 노드 4가 2보다 큰 것을 알 수 있다. 따라서 swap 메서드를 통해 두 인덱스를 서로 변경한다.이후 인덱스를 변경한 후 비교했을때 부모노드 1은 2보다 작으므로 정렬 로직을 중단한다.
추출(pop)
1pop(){2if(this.size()===0)return;3if(this.size()===1)returnthis.heap.pop();45const value =this.heap[0];6this.heap[0]=this.heap.pop();7let currentIdx =0;89while(currentIdx <this.size()){10let left = currentIdx *2+1;11let right = left +1;1213if(!this.heap[left])break;1415let smaller =this.heap[right]!==undefined?(this.heap[left][1]<=this.heap[right][1]? left : right): left;1617if(this.heap[smaller][1]<this.heap[currentIdx][1]){18this.swap(smaller, currentIdx);19 currentIdx = smaller;20}else{21break;22}23}2425return value;26}27
추출은 삽입의 완벽한 반대 과정이다. 차이점이 있다면 탈출 조건이 0에서 마지막으로 변경된 것과 부모 인덱스가 아닌 자식 인덱스를 통해 비교한다는 점이다.위와 같은 힙에서 배열의 첫번째를 가져온 후 정렬하는 로직을 실행하자.
1const value =this.heap[0];2this.heap[0]=this.heap.pop();3let currentIdx =0;4
우선 배열의 0번째 인덱스를 가져온 후 배열의 마지막 값을 pop을 통해 제거 후 0번째 인덱스에 위치시킨다.
1while(currentIdx <this.size()){2let left = currentIdx *2+1;3let right = left +1;45//...6}7
이후 현재 인덱스의 좌우측 자식 노드의 인덱스를 계산한다.
1if(!this.heap[left])break;2
이때 좌측 인덱스 자식이 없는 경우 해당 노드가 현재 트리 분포의 끝이라는 의미이니 정렬을 종료한다.
1let smaller =this.heap[right]!==undefined?(this.heap[left][1]<=this.heap[right][1]? left : right): left;2
그리고 좌우측 자식 노드 중 더 작은 노드의 인덱스를 가져온다.
만약 우측 자식이 없을 시 왼쪽 자식을 할당하며 우측 자식이 있을 시 각 자식 노드의 값을 비교한다.