[알고리즘] 다익스트라 최단 경로 알고리즘 (자바스크립트)

SLAM 과목에서 이동체의 경로를 맵핑할 때 스쳐 배웠던 경험이 있다. 다익스트라 알고리즘은 두 정점 사이에 존재하는 최단 경로를 찾는 알고리즘이다. 그래프 구조로 이루어져 있고, 이진 힙을 사용한 우선순위 큐로 작동한다. 실생활에서 굉장히 빈번하게 사용되고 있는 알고리즘이다.

 

다익스트라 알고리즘

가중 그래프

다익스트라 알고리즘을 구현하기 전에 가중치 그래프를 먼저 소개하려 한다. 그래프의 정점들에 대해 가중치를 부여해 경로의 상대적인 길이를 알 수 있다. 일반적으로 구현했던 그래프의 연결 관계를 담는 키-값 객체에서 가중치가 추가로 매겨지게 된다.

 

1. 시작점을 지정, 방문하여 다음 이동할 노드를 결정해야 한다. 이 때, 가장 작은 거리 가중치를 가진 노드를 선택한다.
2. 다음 노드로 이동한 후, 그 노드의 인접점들을 보면서 각각에 대해 시작점부터 인접점까지의 가중 합을 구한다.
3. 구한 가중 합이 현재 알고 있는 것보다 더 작다면, 해당 노드와 가중합을 새로운 최단 거리로 갱신한다.

class weightedGraph {
  constructor() {
    this.adjList = {};
  }
  addVertex(vertex) {
    if (!this.adjList[vertex]) this.adjList[vertex] = [];
  }

  addEdge(vertex1, vertex2) {
    this.adjList[vertex1].push({ node: vertex2, weight });
    this.adjList[vertex2].push({ node: vertex1, weight });
  }
  }
}

 

구현을 위해서는 정점마다 시작점 A로부터 최단 거리 값을 담은 테이블 (Distances), 방문한 정점을 담은 배열 (Visited), 정점마다 거쳐온 정점들을 담고 있는 객체 데이터 (Previous)가 필요하다.

 

우선순위 큐

앞에서도 잠깐 언급하였듯, 다익스트라 알고리즘을 구현하기 위해서는 우선순위 큐 구조가 필요하다. 아직 방문하지 않은 노드들 중, 가중합이 작은 노드를 찾는 과정에서 사용된다.

class PriorityQueue {
  constructor() {
    this.values = {};
  }
  enqueue() {
    this.values.push({ val, priority });
    this.sort();
  }

  dequeue() {
    return this.values.shift();
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority);
  }
}

본 클래스 메서드의 dequeue()를 통해 다음에 방문할 노드를 반환받을 수 있다. (= priorty 값이 작은 순, 즉 우선순위가 먼저인 노드) 또한 이 큐 방식은 O(N * log(N))의 시간 복잡도를 갖는다.

 

의사코드

1. 가중 그래프 메서드로  다익스트라 함수를 정의한다. 해당 함수는 시작점과 종료점을 입력으로 받는다.
2. 시작점부터의 누적 최단 거리 값을 담은 Distance 테이블 객체를 생성한다.
3. 직전에 방문한 정점 정보를 담은 Previous 객체를 생성한다. 초기값은 null이며 각 키에 대해 최단 거리가 결정될 때마다 바꿔준다.
4. 빈 상태의 새로운 우선순위 큐를 생성한다. 그 후 각 정점을 우선순위 큐에 저장해준다.
5. 시작점 A만 0의 우선순위를 부여하고, 나머지 모든 정점에 대해 Infinite의 우선순위를 부여한다.
6. 우선순위 큐에서 dequeue될 때 정렬된 상태이기 때문에, 0의 값을 갖는 A가 가장 먼저 나온다.
7. 우선순위 큐에 내용물이 있는 한 루프를 반복한다. 해당 큐는 우선순위가 높은(= A에서 가장 가까운 거리 값을 가진) 순으로 정렬되어 있으며, 시작점부터 원하는 정점에 도달할 때까지 정렬된 큐에 있는 정점을 Dequeue해준다.
8. Dequeue된 정점의 모든 인접점들에 대해 시작 정점으로부터의 거리를 계산한다. 계산한 합계가 현재 저장한 값보다 작은 경우 새로운 Distance 값으로 테이블을 갱신하고, Previous 객체의 정점 정보 또한 갱신해준다.

 

구현

  dijkstra(start, finish) {
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [];
    let smallest;

    for (let vertex in this.adjList) {
      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) {
        // 루프 탈출
        console.log(distances);
        console.log(previous);
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
      }
      if (smallest || distances[smallest] !== Infinity) {
        for (let neighbor in this.adjList[smallest]) {
          let nextNode = this.adjList[smallest][neighbor];
          console.log(nextNode);

          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;

          if (candidate < distances[nextNeighbor]) {
            distances[nextNeighbor] = candidate;
            previous[nextNeighbor] = smallest;
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    console.log(path);
    return path.concat(smallest).reverse();
  }