10.1 : 다익스트라(최단경로) 알고리즘 소개
다익스트라 알고리즘을 소개하는 대표적인 예시가 “가장 빠른 길 찾기”이다.
수원 한 지역에서 서울의 한 지역까지 어떻게 갈 수 있을까? 수 많은 길 중에서 가장 빠른 길은 무엇일까? 가장 빠른 길은 어떻게 계산하지? 이러한 과정을 처리하는것이 다익스트라 알고리즘이 하는 일이다.
요약하면 다익스트라 알고리즘은 가중 그래프에서 사용되어 한 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다.
아래 사진에서 A에서 E까지의 최단거리를 “다익스트라”알고리즘을 통하여 학습해보자.
그리고 One-To-All 의 구조를 가지므로 굳이 E가 아니더라도 A부터 다른 노드까지의 최단거리도 구하는것이 가능하다.
알기쉽게 표로 보자.
- 스타트 노드를 0으로 초기화 하고, 이외의 나머지 노드들은 무한(Infinity)으로 초기화한다.
- 새로운 노드를 방문할때마다 가장 작은 거리를 가지는 노드에 먼저 방문한다.
- 방문한 노드의 인접 노드를 탐색한다. (단, 이미 Visiited된 노드들은 제외한다.)
- 방문한 각 인접 노드들에 계산을 실시한다. (스타트 지점부터 해당 인접 노드까지 총거리)
- 만약에 이전 총거리보다 해당 인접 노드를 계산했을떄의 총거리가 더 적다면 해당하는것으로 갱신해준다.
- 만약 갱신이 된다면 Previous의 노드도 같이 갱신해주어야한다. 이걸로 경로를 백트래킹할 수 있기 떄문이다.
- 한 노드들에 대해서 이 과정을 모두 해주었다면 방문했다는 표시 Visited에 넣어준다.
A노드 방문했을때 인접노드인 B를 탐색하고있다. (B,C 중에서 알파벳순으로 B먼저 탐색했다.)
Infinity와 A부터 B까지의 거리인 4와 더 작은 값은 4이므로 4로 갱신한다.
또한 탐색한 B노드의 Previous 노드도 방문한 A노드로 설정한다.
A노드 방문했을때 인접노드인 C를 탐색하고있다.
Infinity와 A부터 C까지의 거리인 2와 더 작은 값은 2이므로 2로 갱신한다.
또한 탐색한 C노드의 Previous 노드도 방문한 A노드로 설정한다.
이러한 과정을 반복하여 그래프를 완성해간다.
전체적인 과정을 다시한번 정리해보자
- Visited 된 부분은 배경색을 빨간색으로 칠하고, 갱신되어야할 부분은 빨간색글자로 표시한다.
왼쪽 표가 갱신되기전, 오른쪽 표가 갱신된 이후
10.2 : 다익스트라(최단경로) 알고리즘 구현
쉽지는 않으므로 계속 반복해서 구현해보자.
class WeightedGraph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(vertex1,vertex2,weight) {
this.adjacencyList[vertex1].push({node:vertex2, weight : weight});
this.adjacencyList[vertex2].push({node:vertex1, weight : weight});
}
dijkstra(start, finish) {
const nodes = new PriorityQueue();
// start부터 해당노드까지의 최단거리
const distances = {};
// 백트래킹을 위한 previous 객체
const previous = {};
let path = []; // result를 위한 배열
let smallest;
// 스타트노드는 0, 나머지노드는 Infinity로 초기화하기
for(let vertex in this.adjacencyList) {
if(vertex === start) {
distances[vertex] = 0;
nodes.enqueue(vertex,0);
} else {
distances[vertex] = Infinity;
nodes.enqueue(vertex,Infinity);
}
previous[vertex] = null;
}
while(nodes.values.length) {
smallest = nodes.dequeue().val;
if(smallest === finish) {
// 끝 !
while(previous[smallest]) {
path.push(smallest);
smallest = previous[smallest];
}
break;
}
if(smallest || distances[smallest] !== Infinity) {
for(let neighnor in this.adjacencyList[smallest]) {
// 인접점 찾기
let nextNode = this.adjacencyList[smallest][neighnor];
// 인접점들에 대한 새로운 거리 계산
let candidate = distances[smallest] + nextNode.weight;
let nextNeighbor = nextNode.node;
if(candidate <distances[nextNode.node]) {
// 인접노드로 탐색할때 새로운 최단 거리를 바꿔주는 작업
distances[nextNeighbor] = candidate;
// 새로운 최단 거리로 갱신했을때 previous도 역시 갱신시켜주어야한다
// 어떻게 nighbor로 가는지를 알수있게끔
previous[nextNeighbor] = smallest;
// 우선순위 큐에 새로이 갱신해준다
nodes.enqueue(nextNeighbor,candidate);
}
}
}
}
return path.concat(smallest).reverse();
}
}
// 이진힙 사용
class PriorityQueue {
constructor(){
this.values = [];
}
enqueue(val, priority){
let newNode = new Node(val, priority);
this.values.push(newNode);
this.bubbleUp();
}
bubbleUp(){
let idx = this.values.length - 1;
const element = this.values[idx];
while(idx >0){
let parentIdx = Math.floor((idx - 1)/2);
let parent = this.values[parentIdx];
if(element.priority >= parent.priority) break;
this.values[parentIdx] = element;
this.values[idx] = parent;
idx = parentIdx;
}
}
dequeue(){
const min = this.values[0];
const end = this.values.pop();
if(this.values.length >0){
this.values[0] = end;
this.sinkDown();
}
return min;
}
sinkDown(){
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while(true){
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild,rightChild;
let swap = null;
if(leftChildIdx <length){
leftChild = this.values[leftChildIdx];
if(leftChild.priority <element.priority) {
swap = leftChildIdx;
}
}
if(rightChildIdx <length){
rightChild = this.values[rightChildIdx];
if(
(swap === null &&rightChild.priority <element.priority) ||
(swap !== null &&rightChild.priority <leftChild.priority)
) {
swap = rightChildIdx;
}
}
if(swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
var graph = new WeightedGraph()
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addVertex("F");
graph.addEdge("A","B",4);
graph.addEdge("A","C",2);
graph.addEdge("B","E",3);
graph.addEdge("C","D",2);
graph.addEdge("C","F",4);
graph.addEdge("D","E",3);
graph.addEdge("D","F",1);
graph.addEdge("E","F",1);
console.log(graph.dijkstra("A","E")); // [ 'A', 'C', 'D', 'F', 'E' ]
Developer