그래프O(E log V)

다익스트라 최단경로

가중치가 있으면 다익스트라예요. 우선순위 큐로 가장 가까운 곳부터 확정해요.

이럴 때 써요

간선마다 가중치(거리·시간·비용)가 있는 최단경로일 때
한 시작점에서 모든 정점까지의 최소 비용이 필요할 때
가중치가 있어 BFS의 '먼저 도착 = 최단'이 깨질 때

개념

BFS는 간선을 다 1칸으로 세서 가까운 곳부터 퍼져요. 그런데 가중치가 있으면, 간선 수가 적어도 비용은 더 클 수 있어요. A→B(비용 5) 하나보다 A→C→B(2+2=4) 두 개가 더 싼 것처럼요. 그래서 '칸 수'로 퍼지는 BFS가 아니라, 비용이 가장 작은 정점부터 꺼내는 다익스트라가 필요해요.핵심은 거리 배열 + 최소 힙이에요. dist를 전부 INF로 두고 시작점만 0으로 놔요. 힙에서 가장 가까운 정점을 꺼내면 그 정점의 최단거리는 거기서 확정돼요. 그 정점의 이웃마다 dist[u] + w < dist[v] 면 더 짧은 길을 찾은 거라 dist[v]를 줄이고(이완, relax) 힙에 넣어요.

"A에서 최단거리" — dist가 INF에서 줄어드는 과정
간선: A-B(1), A-C(4), B-C(2), B-D(6), C-D(3)
dist = [A:0, B:INF, C:INF, D:INF]
힙 = { (0,A) }
꺼냄 (0,A) → B:1, C:4 로 이완   dist=[0, 1, 4, INF]
꺼냄 (1,B) → C: 1+2=3 < 4 갱신, D:1+6=7   dist=[0, 1, 3, 7]
꺼냄 (3,C) → D: 3+3=6 < 7 갱신          dist=[0, 1, 3, 6]
꺼냄 (4,C) → 이미 확정된 3보다 큼, 스킵(stale)
꺼냄 (6,D) → 이웃 없음
→ dist = [A:0, B:1, C:3, D:6]

패턴 코드

다익스트라 (우선순위 큐)JS는 표준 힙이 없어 최소 힙을 직접 넣었어요. Python은 heapq를 그대로 써요. 둘 다 stale 거리를 꺼내면 건너뛰어요.

javascript
Copy code
class MinHeap {
  constructor() { this.a = []; } // 각 원소 = [거리, 정점]
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p][0] <= a[i][0]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    const top = a[0];
    const last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let s = i;
        const l = 2 * i + 1, r = 2 * i + 2;
        if (l < a.length && a[l][0] < a[s][0]) s = l;
        if (r < a.length && a[r][0] < a[s][0]) s = r;
        if (s === i) break;
        [a[s], a[i]] = [a[i], a[s]];
        i = s;
      }
    }
    return top;
  }
  get size() { return this.a.length; }
}
function dijkstra(graph, start) {
  // graph[u] = [[v, w], ...]
  const dist = new Array(graph.length).fill(Infinity);
  dist[start] = 0;
  const heap = new MinHeap();
  heap.push([0, start]);
  while (heap.size) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue; // stale, 건너뛰기
    for (const [v, w] of graph[u]) {
      const nd = d + w;
      if (nd < dist[v]) { // 이완
        dist[v] = nd;
        heap.push([nd, v]);
      }
    }
  }
  return dist;
}

이 유형으로 풀어보기

← DFS·BFS 완전탐색 유니온 파인드 — 그룹·사이클 판정 →