자바스크립트 최단거리 알고리즘 (다익스트라 알고리즘, Dijkstra)

최단거리를 구하는 알고리즘은 다양한 방법으로 구현할 수 있다. 

최단거리 알고리즘은 코딩테스트에서도 많이 사용되고, 생각보다 최단거리를 구해야할 경우가 종종 있기에 이번 기회에 정리하도록 하였다.

이번에는 자바스크립트로 가장 기본적인 최단거리 알고리즘 방법인 다익스트라(Dijkstra) 알고리즘을 구현해보도록 하였다.

 

🥩 다익스트라 알고리즘은 최단거리를 구하는데 사용되는 대표적인 알고리즘 중 하나이지만, 그 외에도 벨만-포드 알고리즘, A* 알고리즘, 플로이드-워셜 알고리즘 등 다양한 알고리즘을 통해서 최단거리를 구할 수 있다.

🧀 알고리즘의 선택은 문제의 제약사항과 성능 요구사항에 따라 달라질 수 있다.

 

다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘으로 아래는 다익스트라 알고리즘의 구현 예시이다.

function dijkstra(graph, start) {
  const distances = {};
  const visited = {};
  const queue = [];

  // 출발점에서의 거리를 0으로 초기화
  distances[start] = 0;
  queue.push(start);

  while (queue.length) {
    const current = queue.shift(); // 현재 위치
    visited[current] = true; // 방문

    const neighbors = graph[current]; // 현재 위치에서 갈 수 있는 노드
    for (let neighbor in neighbors) {
      const distance = distances[current] + neighbors[neighbor]; // 출발점으로부터 현재 노드를 거쳐 다음 노드로 가는 거리
      if (!distances[neighbor] || distance < distances[neighbor]) { // 기존의 경로가 있을 때, 지금 계산한 새 경로가 더 빠르면 갱신
        distances[neighbor] = distance;
      }
      if (!visited[neighbor]) {
        queue.push(neighbor);
      }
    }
  }

  return distances;
}

위의 코드에서 `graph`는 그래프를 나타내는 인접리스트 형태의 객체로, 위의 예는 다음과 같은 그래프의 예제를 사용할 수 있다.

const graph = {
  A: { B: 5, C: 2 },
  B: { A: 5, D: 1 },
  C: { A: 2, D: 6 },
  D: { B: 1, C: 6 },
};

위의 그래프에서 각 정점은 객체의 키로 표현되고, 해당 정점과 인접한 정점들과의 거리는 값으로 표현된다.

이 경우 A 정점과 B 정점은 거리가 5이고, A 정점과 C 정점은 거리가 2이다.

위의 `dijkstra` 함수를 사용하여 출발점에서 각 정점까지의 최단거리를 계산하려면 다음과 같이 호출할 수 있다.

const distances = dijkstra(graph, 'A');
console.log(distances); // 출력 결과 { A: 4, B: 5, C: 2, D: 6 }

결과는 객체 형태로 반환되며, 각 정점과 출발점 사이의 최단거리가 저장된다.