다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘(Dijkstra’s Algorithm)은 그래프의 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.

음의 가중치가 없는 그래프에서만 동작하며 대표적인 최단 경로 탐색 알고리즘입니다.

Table of Contents

다익스트라 알고리즘 예제

우선순위 큐 사용 예제

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

  isEmpty() {
    return this.values.length === 0;
  }
}

function dijkstra(graph, start) {
  const distances = {};
  const pq = new PriorityQueue();
  const previous = {};

  // 초기화
  for (let node in graph) {
    distances[node] = Infinity;
    previous[node] = null;
  }

  distances[start] = 0;
  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { val: currentNode } = pq.dequeue();

    for (let neighbor of graph[currentNode]) {
      const { node: neighborNode, weight } = neighbor;
      const newDist = distances[currentNode] + weight;

      if (newDist < distances[neighborNode]) {
        distances[neighborNode] = newDist;
        previous[neighborNode] = currentNode;
        pq.enqueue(neighborNode, newDist);
      }
    }
  }

  return distances;
}

예제 그래프

const graph = {
  A: [{ node: "B", weight: 1 }, { node: "C", weight: 4 }],
  B: [{ node: "C", weight: 2 }, { node: "D", weight: 5 }],
  C: [{ node: "D", weight: 1 }],
  D: []
};

console.log(dijkstra(graph, "A"));
// 출력: { A: 0, B: 1, C: 3, D: 4 }

PriorityQueue는 간단한 배열 기반 구현입니다. 성능이 중요한 경우는 최소 힙(Min Heap)을 사용하는 게 더 효율적입니다.
distances 객체는 각 노드까지의 최단 거리를 저장합니다.
previous 객체를 이용하면 경로 추적도 할 수 있습니다.

다익스트라 알고리즘 설명

PriorityQueue는 다익스트라 알고리즘에서 가장 가까운 노드를 선택하기 위해 사용됩니다.

이번 예제에서는 배열 정렬을 사용하지만 성능이 중요한 상황에서는 최소 힙 구조를 쓰는 게 더 좋습니다.

distances는 A에서 각 노드까지의 최소 거리를 기록합니다.

previous는 각 노드에 도달했을 때의 이전 노드를 저장하며 이를 기반으로 최단 경로를 복원할 수 있습니다.

시작노드 거리만 0으로 설정하고 나머지는 무한대로 시작합니다.

while 루프에서는 우선순위 큐에서 현재 가장 가까운 노드를 꺼낸 후, 그 노드의 이웃 노드에 대해 거리 계산을 해보고 지금까지 알려진 거리보다 짧으면 갱신합니다.

갱신된 노드는 큐에 다시 넣어 탐색 대상이 되고 이 방법을 반복하여 모든 노드를 탐색했다면 distances에는 각 노드까지의 최단 거리가 남게됩니다.

용어 정리

정점(Vertex): 노드
간선(Edge): 노드 간 연결
가중치(Weight): 간선에 부여된 비용
최단 경로(Distance): 한 정점에서 다른 정점까지의 최소 비용 경로

기본 개념

가장 가까운 정점부터 차례대로 최단 경로를 확정해 나가는 방식으로 탐욕적(Greedy) 기법에 기반을 둠
방문하지 않은 정점들 중에서 현재까지의 거리가 가장 짧은 정점을 선택하고 이웃 노드들의 거리 값을 갱신

전제 조건

가중치(간선 비용)는 0 이상의 정수여야 함 (음의 가중치가 있는 경우에는 벨만-포드 알고리즘 사용)
그래프는 연결되어 있을 수도 있고 아닐 수도 있음
우선순위 큐를 사용하면 시간 복잡도 개선 가능

다익스트라 알고리즘 단계 (우선순위 큐 사용)

입력:

그래프 𝐺 = ( 𝑉 , 𝐸 )
시작 정점 𝑠

초기화:

모든 정점의 거리를 무한대로 설정
시작 정점의 거리는 0으로 설정
우선순위 큐에 (거리, 정점) 형태로 삽입

반복:

큐에서 거리가 가장 짧은 정점 𝑢를 꺼냄
𝑢의 모든 이웃 정점 𝑣에 대해:
- 현재까지의 거리 dist[𝑣]와
- 𝑢를 거쳐 가는 거리 dist[𝑢] + 𝑤(𝑢, 𝑣)를 비교
- 더 짧은 경로를 찾으면 갱신하고, 우선순위 큐에 갱신된 거리로 삽입

종료:

모든 정점에 대해 최단 거리 계산이 완료되면 종료

시간복잡도

우선순위 큐를 힙(Heap)으로 구현할 경우:

𝑂((𝑉 + 𝐸) log 𝑉)

→ V는 정점 수, E는 간선 수

장점

간단하고 직관적
효율적 (우선순위 큐 사용 시)

단점

음의 가중치가 있는 그래프에서는 사용 불가
모든 정점에 대해 최단 경로를 구하므로 단일 목적지 탐색엔 비효율적임

알고리즘 튜토리얼

다익스트라 알고리즘 (Dijkstra’s Algorithm)