다익스트라(Dijkstra) 알고리즘 - 자바스크립트 코드 예제

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 참고로 거리가 양수일 때만 사용할 수 있다. 

 

다익스트라 알고리즘은 다이나믹 프로그래밍 문제이기도 하는데, 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. 

다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 

 

다익스트라 알고리즘은 그래프와, 우선순위 큐(이진 힙 버전) 개념을 알고 있어야 한다. 

 

 

작동과정

---

1. 출발 노드를 설정한다.

2. 출발 노드를 기준으로 각 노드의 최소 거리을 저장한다.

3. 방문하지 않은 노드 중에서 가장 거리가 작은 노드를 선택한다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 거리를 갱신한다. 

• 각 이웃 노드에 대해 시작 노드에서부터 현재 보고 있는 노드까지 이어지는 전체 거리를 합산한다.
• 현재 보고 있는 노드까지의 새로운 거리가 기존에 최단거리로 기록된 값보다 작으면, 새로운 더 짧은 거리를 저장한다. 

5. 3 ~ 4번을 반복한다. 

 

 

가중 그래프

---

예를 들어 A 장소(vertex1)와 B 장소(vertex2) 사이의 거리(weight)를 간선에 추가해줘야 한다.

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 });
    this.adjacencyList[vertex2].push({ node: vertex1, weight });
  }
}

 

 

우선순위 큐

---

단순히 배열로 우선순위 큐를 구현한 코드다.

class PriorityQueue {
  constructor() {
    this.values = [];
  }
  enqueue(val, priority) {
    this.values.push({ val, priority });
    this.sort();
  }
  dequeue() {
    return this.values.shift();
  }
  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

 

프로그래머스 예제

---

 

프로그래머스

위의 예제로 다익스트라 알고리즘을 연습해보자! 자세한 해설은 따로 블로깅해두었다. 

 

참고자료

---

• 유투브
• blog
• velog
• github.io

---

질문이나 잘못된 점은 댓글로 남겨주세요 :)💖

반응형