글을 시작하며

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘입니다.

이번 글에서는 다익스트라 알고리즘이 무엇인지, 어떻게 동작하는지, 그리고 이를 직접 구현하는 방법까지 단계별로 알아보고자 합니다.

다익스트라 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 가중 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 최단 경로 탐색 문제에서 자주 사용되며, 주로 음의 가중치가 없는 그래프에서 활용됩니다.

이 알고리즘은 우선순위 큐(Priority Queue)를 활용해 현재까지의 최단 거리 정보를 기반으로 탐색을 진행하는 것이 핵심입니다.

가중 그래프(Weighted Graph): 각 간선(edge)에 비용(weight)이 존재하는 그래프.
우선순위 큐(Priority Queue): 현재 최단 거리로 방문할 정점을 빠르게 찾기 위해 사용.
음의 가중치(negative weight)가 없는 경우에만 적용 가능

다익스트라 알고리즘의 핵심 아이디어는 시작 정점으로부터 각 정점까지의 최단 거리를 점진적으로 찾아가는 것입니다.

1. 아직 방문하지 않은 정점 중 시작점으로부터 가장 가까운 정점을 선택합니다.
2. 선택한 정점과 인접한 모든 정점에 대해, 시작점에서 현재 정점을 거쳐 인접 정점으로 가는 거리가 이전에 계산된 거리보다 짧은지 확인합니다.
3. 더 짧은 경로가 발견되면 해당 정점까지의 거리를 업데이트합니다.

다익스트라 알고리즘의 구현 (JavaScript)

// 간단하게 우선순위 큐 구현
class MinHeap {
  constructor() {
    this.heap = [];
  }
  push(node) {
    this.heap.push(node);
    this.heap.sort((a, b) => a[0] - b[0]); // 비용 기준 정렬
  }
  pop() {
    return this.heap.shift();
  }
  size() {
    return this.heap.length;
  }
}

function dijkstra(graph, start) {
  const heap = new MinHeap();
  let dist = new Array(graph.length).fill(Infinity);

  dist[start] = 0;
  heap.push([0, start]); // [비용, 노드]

  while (heap.size()) {
    const [cost, node] = heap.pop();

    if (cost > dist[node]) continue;

    for (const [next, weight] of graph[node]) {
      // 현재 노드를 거쳐 이웃 노드로 가는 거리 계산
      const newCost = cost + weight;

      // 더 짧은 경로가 발견되면 업데이트
      if (newCost < dist[next]) {
        dist[next] = newCost;
        heap.push([newCost, next]);
      }
    }
  }
  return dist;
}

1. 출발 노드(시작점)를 설정하고, 모든 정점까지의 거리를 무한대로 초기화한다. 단, 출발 노드의 거리는 0으로 설정한다.
2. 우선순위 큐를 이용해 현재 최단 거리의 정점을 선택한다.
3. 선택된 정점과 인접한 노드의 최단 거리를 업데이트한다.
4. 위 과정을 반복하며 모든 정점을 탐색한다.
5. 최종적으로, 출발지에서 목적지까지의 최단 경로가 구해진다.

적용할 수 있는 문제

• 백준 1753: 최단경로
• 백준 1504: 특정한 최단 경로
• 백준 1916: 최소비용 구하기
• 백준 1238: 파티

결론

다익스트라 알고리즘은 최단 경로 문제에서 가장 널리 사용되는 알고리즘 중 하나입니다. 이번 포스팅에서는 다익스트라 알고리즘의 개념, 동작 과정, 그리고 JavaScript 구현을 살펴보았습니다. 이를 통해 다익스트라 알고리즘이 어떻게 사용되는지 이해하고, 실제 문제에서 적용해 볼 수 있길 바랍니다!