4.11Dijkstra's Algorithm

가중 그래프에서 최단 거리를 계산하는 다익스트라 알고리즘 구현하기

Dijkstra's Shortest Path Algorithm

다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘으로, 고안자 Edsger Dijkstra의 이름을 따서 이름이 지어졌다.

다익스트라 알고리즘은 오늘날 수많은 분야에서 쓰인다.

GPS: 최단 거리를 찾는다.
네트워크 라우팅: 데이터를 전송할 수 있는 가장 짧은 라우트를 찾는다.
생물학: 바이러스가 사람들에게 어떻게 퍼질지 예측하는 모델에 쓰인다.
비행기 티켓: 목적지에 갈 수 있는 가장 싼 경로를 찾는데 쓰인다.
기타 등등...

가중 그래프 구현하기

현실적으로 우리가 구하고자 하는 최단 거리 문제는, 대개 각 정점 간의 거리가 다른 가중 그래프(Weighted Graph) 기반이다. 따라서 우선 가중 그래프를 구현해보자.

우리가 이전까지의 포스팅에서 구현했던 정점은 {"A": ["B", "C"], "B": ["A", "D"], ...} 식이었다. 가중 그래프를 만들려면 인접 목록에 정점과 해당 정점까지의 거리(가중치)를 포함한 객체를 추가해야한다. 즉, ["A": {"node": "B", "weight": 9}]과 같은 형태다.

javascript
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})
  }
}

다익스트라 알고리즘의 원리

예를 들어, 아래와 같은 가중 그래프의 A에서 E로 가는 최단 거리를 구하는 문제를 푼다고 해보자.

다익스트라 알고리즘의 원리는 대략적으로 이렇다.

새로운 노드를 방문하는 경우, 그 노드로 갈 수 있는 알려진 최단 거리로 간다.
새로운 노드로 방문했으면, 그것의 이웃 노드를 확인한다.
이웃 노드들 각각에 대해, 시작 노드로부터 얼마나 떨어진 노드인지 거리를 확인한다.
이전에 알려진 최단 거리보다 이 거리가 더 짧으면, 이 거리를 최단으로 갱신한다.

이 원리를 구현하려면, 우선 시작 노드로부터 다른 모든 노드의 거리를 Infinity로 가정하고 갱신해 나간다. 예를 들어, 위의 이미지와 같은 그래프에서 A에서 E로 가는 방법을 구할때 우선은 A에서 B 또는 C로 갈 수 있는데, B로 가는 최단 거리는 우선은 Infinity다. 그리고 가장 단순하게 찾을 수 있는 방법은 직접 가는 것으로, 4의 거리가 있고 이는 Inifinity보다 작으므로 4로 알려진 최단 거리를 갱신한다.

이렇게 최단 거리를 갱신했으면, 방문한 노드들을 기록해두는 배열에 그 노드로 가기 위해 이전에 있었던 노드를 추가하고(여기선 우선 A), 방문한 노드로 가는 최단 거리를 위해 이전에 들러야하는 노드를 기록해둔다. 즉, 여기서 B를 방문하기 위해서 이전에 A를 들러야 A에서 B로 가는 최단 거리로 갈 수 있음을 기록하는 것이다. 같은 방식으로, C로 가는 최단 거리도 2로 갱신한다.

이렇게 했을 경우, A에서 갈 수 있는 두 곳 중 더 가까운 곳은 C로 가는 2이다. 그러면 C에서 다음으로 갈 수 있는 D와 F를 비교한다. D로 가면 2가 추가된다. 따라서 A에서 D로 가는 가장 짧은 거리는 2 + 2로 4다. F는 4가 추가되어 6이다.

그러면 D로 가는 4, F로 가는 6, B로 가는 4를 비교한다. D와 B가 같이 4이므로 우선 D부터 살펴본다. D에서 E로 가는 길은 3이 추가되어 7, F로 가는 길은 1이 추가되어 5다. 이런 식으로 계속 반복하며 갱신하면, 시작 정점에서 각 정점으로 가는 최단 거리들과 해당 정점으로 최단거리로 가기 위한 직전 노드도 알 수 있다.

우선 순위 큐 활용하기

우리는 우선 순위 큐를 활용해, 다음 노드로 가는 최단 거리를 빠르게 찾을 것이다. 간단하게 구현한 우선 순위 큐의 코드는 아래와 같다. 더 효율적으로 제대로 작성한 코드는 이전 포스팅에서 확인할 수 있다.

javascript
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);
  };
}

다익스트라 알고리즘 구현하기

수도코드를 아래와 같이 작성할 수 있다:

시작 정점과 끝 정점을 받아 최단 경로를 구하는 함수를 선언한다.
각 정점까지의 최단거리를 저장하는 객체를 만들고, 각 정점들을 key로 초기값 Infinity를 할당한다. 시작 정점은 0의 거리를 가진다.
우선 순위 큐를 만든다. 역시 각 정점을 키로 하고 우선순위가 Infinity다.
특정 정점으로 최단거리로 가기 위해 직전에 들러야 하는 정점들을 저장하는 객체를 만든다. 값들은 우선은 모두 null을 할당한다.
우선 순위 큐에 뭔가 있으면 아래를 루프한다:
- 우선 순위 큐에서 정점을 dequeue한다.
- 해당 정점이 만약 우리가 목표로 했던 끝 정점과 같다면, 루프를 종료한다.
- 그렇지 않다면, 해당 정점의 인접 목록들을 순회한다.
  - 시작 정점으로부터 해당 정점까지의 거리를 계산한다.
  - 거리가 현재 저장된 정점까지의 최단거리를 저장하는 객체에 있는 거리보다 짧다면 업데이트한다.
  - 직전에 들러야 하는 정점들을 저장하는 객체에 해당 정점을 업데이트한다.
  - 해당 정점과 거리를 최단거리를 저장하는 객체에 업데이트한다.
끝까지 가는 경로(거쳐야 하는 정점들을 포함한 배열) 반환한다.

아래는 앞서 작성한 WeightedGraph 클래스와 PriorityQueue를 활용해서 작성한 다익스트라 알고리즘 코드다.

javascript
class WeightedGraph {
  constructor(){
    this.adjacencyList = {};
  }
  Dijkstra(start, finish){
    const nodes = new PriorityQueue();
    const distances = {};
    const previous = {};
    let path = [];
    let smallest;

    // 초기값 설정
    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 neighbor in this.adjacencyList[smallest]){
          // 인접 노드 찾기
          let nextNode = this.adjacencyList[smallest][neighbor];
          // 인접 노드까지의 거리 계산 및 필요시 업데이트
          let candidate = distances[smallest] + nextNode.weight;
          let nextNeighbor = nextNode.node;
          if(candidate < distances[nextNeighbor]){
            distances[nextNeighbor] = candidate;
            previous[nextNeighbor] = smallest;
            nodes.enqueue(nextNeighbor, candidate);
          }
        }
      }
    }
    // path는 도착점에서부터 역순으로 어떻게 해당 노드에 도착했는지를 담고 있다.
    // 시작점을 끝에 추가하고 뒤집으면 시작점부터 도착점까지 어떻게 가야하는지가 순서대로 배열에 담긴다.
    return path.concat(smallest).reverse();
  }
}

PreviousGraph Traversal

Algorithm

NextNo next post