알고리즘 준비하기 - 다익스트라

🎯 다익스트라

다익스트라 알고리즘은 하나의 시작 지점으로부터 모든 다른 지점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. ‘매번 경로의 길이가 짧은 노드를 선택하는 과정’을 반복하기 때문이다.

🎯 다익스트라 알고리즘의 과정

시작 정점을 설정하고, 시작 정점의 거리 값을 0으로 설정한다. 시작 정점을 제외한 모든 정점의 거리 값을 무핟내로 설정한다.
현재까지 방문하지 않은 정점 중에서 출발점에서 가장 가까운 정점을 선택한다.
해당 정점의 이웃 정점에 대해서, 출발점에서 해당 이웃 정점까지의 거리를 계산한다.
계산된 거리가 해당 이웃 정점의 현재 거리 값보다 작다면, 해당 이웃 정점의 거리 값을 갱신한다.
모든 정점을 방문할 때까지 위 과정을 반복한다.

🎯 다익스트라 알고리즘 구현

다익스트라 알고리즘은 Min Heap을 사용하여 구현한다. 우선순위 큐를 사용하면 구현이 더 빠르고 간단해진다. 큐에서 뽑힌 정점은 해당 정점에서부터 가장 짧은 거리로 도달할 수 있는 정점 중 가장 가까운 정점이기 때문에 이후의 경로는 해당 정점을 거쳐갈 필요가 없다.

우선순위 큐와 관련된 내용과 코드는 알고리즘 준비하기 - MinHeap를 참고하면 된다.

function Dijkstra(n, start, paths) {
  const graph = Array.from({ length: n + 1 }, () => []);

  for (let [a, b, c] of paths) {
    graph[a].push([b, c]);
    graph[b].push([a, c]);
  }

  const pq = new MinHeap();
  const distance = new Array(n + 1).fill(Infinity);

  pq.add([start, 0]);
  distance[start] = 0;

  while (pq.size()) {
    let [node, dist] = pq.poll();

    if (distance[node] < dist) continue;

    for (const [nextNode, weight] of graph[node]) {
      const cost = dist + weight;

      if (cost < distance[nextNode]) {
        distance[nextNode] = cost;
        pq.add([nextNode, cost]);
      }
    }
  }
  return distance;
}

🎯 최단경로 문제 TIP

최단 경로 문제를 해결할 때 혹시 위의 코드가 시간초과가 발생한다면 MinHeap에 들어가는 도착 노드와 거리의 위치를 변경하면 해결이 된다.

(Node, 거리) 쌍으로 넣게 되면 기준이 Node가 된다. 하지만 Dijkstra알고리즘은 거리가 가장 짧은 간선을 먼저 사용해야 하기에 기준이 거리가 되어야 하고, 따라서 (거리, Node) 쌍으로 넣어 주어야 한다.

📑 Reference

참돔 블로그 - 다익스트라 알고리즘이란?

🎯 다익스트라
🎯 다익스트라 알고리즘의 과정
🎯 다익스트라 알고리즘 구현
🎯 최단경로 문제 TIP
📑 Reference