최단 경로 찾기 : 다익스트라(Dijkstra) 알고리즘

다익스트라

 

 

들어가며

 

지난 포스트에서는 그래프를 탐색하는 두 가지 방법인 DFS와 BFS에 대해서 알아보았습니다. 이번에는 그래프 상의 최단 경로를 찾는 알고리즘 중 하나인 다익스트라(Dijkstra, 또는 데이크스트라) 알고리즘에 대해서 알아보겠습니다.

 

다익스트라 알고리즘은 1972년도에 튜링상을 수상했던 에츠허르 데이크스트라(Edsger Wybe Dijkstra)가 1956년에 고안한 알고리즘으로, 암스테르담에서 약혼녀와 쇼핑을 하다가 카페 테라스에서 잠깐 쉬어가던 중 "한 도시에서 다른 도시로 가는 가장 짧은 길이 무엇일까?" 를 생각하며 고안하게 되었다고 하네요.

 

이 알고리즘은 그래프 상의 최단 경로를 찾는 알고리즘으로, DFS나 BFS와 같이 정점과 간선으로 이루어진 구조에서 사용됩니다. 그 중에서도 간선의 가중치가 음수가 아닌 그래프에서 사용되는데, 이러한 특징 때문에 네비게이션이나 지도 어플리케이션과 같이 실생활에서 최단 거리를 구하는 기능을 구현할때 응용되곤 합니다.

 

 

길찾기 알고리즘으로 널리 사용되는 다익스트라

 

 

동작 원리

 

다익스트라 알고리즘의 동작 과정은 다음과 같습니다.

 

1. 최단 경로 초기화
   • 먼저 최단 경로 정보를 초기화합니다.
   • 시작 정점은 0으로, 그 외의 다른 모든 정점의 최단 경로는 무한대로 설정합니다.
2. 방문 여부를 기록하며 탐색
   • 시작 정점을 방문한 정점으로 간주하고, 해당 정점에 인접한 모든 정점들까지의 거리를 갱신합니다.
   • 갱신한 정점까지의 거리 중 시작 정점으로부터 가장 짧은 거리의 정점을 선택합니다.
   • 선택한 정점을 방문한 정점으로 간주하고, 다시 위의 과정을 반복합니다

 

위 과정을 거치면 모든 순간에서 항상 짧은 거리만을 선택하게 되므로, 시작 정점으로부터 모든 정점까지의 최단 거리 정보를 구할 수 있게 됩니다.

 

 

탐색 과정에서 반복적으로 가장 짧은 거리를 선택해 나가는 것을 통해 유추할 수 있는 한 가지 특성이 있습니다. 바로 다익스트라 알고리즘이 탐욕적 알고리즘이라고 부르는 그리디(greedy)의 특성을 가진다는 점입니다.

 

다익스트라 알고리즘은 그리디를 기반으로 하기 때문에 시작 정점에서부터 현재 정점까지의 거리가 계속해서 증가한다는, 즉 가중치가 양수라는 특징이 있습니다. 그리디 알고리즘 덕분에 매 순간 가장 짧은 선택을 하는 것으로 최단 거리임을 보장할 수 있지만, 정점과 정점 사이의 거리가 반드시 음수가 아니어야만 한다는 점을 유의해야 합니다.

 

만약 가중치가 음수인 그래프에서 최단 거리를 구해야한다면, 다익스트라 알고리즘이 아닌 벨만 포드 알고리즘을 사용해야합니다.

 

 

 

구현

 

다음은 자바스크립트를 이용해 다익스트라 알고리즘을 구현한 코드입니다.

 

/* 입력은 아래와 같습니다.
    const graph = {
      1: [[2, 2], [3, 3]],
      2: [[3, 4], [4, 5]],
      3: [[4, 6]],
      4: [],
      5: [[1, 1]],
    };
*/

function dijkstra(graph, start) {
  const distances = {};
  const visited = {};
  const nodes = Object.keys(graph);
  
  // 1. 최단 정보 초기화
  nodes.forEach((node) => {
    distances[node] = Infinity;
  });
  distances[start] = 0;

  // 2. 방문 여부를 기록하며 탐색
  while (nodes.length) {
    let minNode = null;
    nodes.forEach((node) => {
      if (!minNode || distances[node] < distances[minNode]) {
        minNode = node;
      }
    });

    const weight = distances[minNode];
    const neighbors = graph[minNode];
    
    neighbors.forEach((neighbor) => {
      const [node, edgeWeight] = neighbor;
      const totalWeight = weight + edgeWeight;
      if (distances[node] > totalWeight) {
        distances[node] = totalWeight;
      }
    });

    visited[minNode] = true;
    nodes.splice(nodes.indexOf(minNode), 1);
  }

  return distances;
};

 

 

입력받은 graph에 따라 총 정점의 갯수를 구하고, 인접한 정점들을 구해 최단 거리를 찾는 과정을 반복합니다. while문에서 정점의 수만큼, 내부의 forEach에서 정점의 수만큼 반복이 중첩되어 일어나기 때문에 이 코드의 시간 복잡도는 O(N^2)입니다.

 

시간복잡도가 결코 작은 편이 아니기 때문에 이런 경우 정점의 갯수가 많아질수록 실행 시간이 길어질 수 있다는 문제가 있습니다. 때문에 최단 거리를 찾는 로직에서 우선순위 큐를 사용하면 이러한 문제점을 개선할 수 있습니다. 기존의 순회가 O(N)의 시간 복잡도를 갖는데 반해, 우선순위 큐의 최소 힙은 O(log N)의 시간 복잡도를 가지므로 우선순위 큐를 사용하여 구현한 다익스트라의 알고리즘의 경우 O(N * log N)의 시간 복잡도를 갖게 됩니다.

 

알고리즘에서 많이 사용하는 C++ 언어의 경우 표준 라이브러리 중 <queue>에서 priority_queue라는 이름으로 우선순위 큐를 지원하고 있습니다. 다만 자바스크립트에서는 기본으로 지원하는 자료형이 아니기 때문에 직접 구현해주어야 합니다. 알고리즘 대회나 코딩 테스트 대비가 아닌 이상, 되도록이면 직접 구현보다는 라이브러리를 사용할 것을 권장합니다 :)

 

 

다음은 우선순위 큐를 사용하여 구현한 다익스트라 코드입니다. 우선순위 큐는 따로 구현하지 않았습니다.

 

 

function dijkstra(graph, start) {
  const distances = {};
  const visited = {};
  const queue = new PriorityQueue();
  
  // 1. 최단 정보 초기화
  Object.keys(graph).forEach((node) => {
    distances[node] = Infinity;
  });
  distances[start] = 0;
  queue.enqueue(start, 0);

  // 2. 방문 여부를 기록하며 탐색
  while (!queue.isEmpty()) {
    const currentNode = queue.dequeue();
    
    if (visited[currentNode]) {
      continue;
    }
    visited[currentNode] = true;
    
    const neighbors = graph[currentNode];
    neighbors.forEach((neighbor) => {
      const [nextNode, distance] = neighbor;
      const totalDistance = distances[currentNode] + distance;

      if (totalDistance < distances[nextNode]) {
        distances[nextNode] = totalDistance;
        queue.enqueue(nextNode, totalDistance);
      }
    });
  }

  return distances;
};

 

 

 

마치며

이번 포스트에서는 다익스트라 알고리즘과 구현에 따른 시간 복잡도에 대해서 알아보았습니다.

다음 시간에는 이번과 마찬가지로 그래프를 탐색하는 방법인 플로이드-와셜에 대해 알아보겠습니다.

 

읽어주셔서 감사합니다.