← 21주차 · 최단 경로와 위상 정렬
보통그래프다익스트라힙

다익스트라 최단 경로

정점 개수 n, 방향 간선 목록 edges, 시작 정점 start가 주어져요. 정점은 0번부터 n-1번까지 있고, edges의 각 원소 [u, v, w]는 u에서 v로 가는 비용 w인 간선이에요. 비용은 모두 0 이상이에요.

start에서 각 정점까지의 최단 거리를 배열로 반환해요. i번째 값은 start에서 i까지의 최단 거리이고, start 자신은 0이에요. 갈 수 없는 정점은 -1로 표시해요.

BFS와 발상은 같지만 큐 대신 힙을 써서 '아직 확정 안 된 정점 중 가장 가까운 것'을 꺼내요. 힙에서 꺼낸 거리가 기록된 거리보다 크면 낡은 항목이니 건너뛰어요.

JavaScript는 스타터의 MinHeap을, 파이썬은 heapq를 써요.

예시

예시 1
입력
n = 5, edges = [[0, 1, 2], [0, 2, 5], [1, 2, 1], [1, 3, 2], [2, 3, 3], [3, 4, 1]], start = 0
출력
[0, 2, 3, 4, 5]
설명
0→1(2)→2(1)이 2까지 3, 1→3(2)로 3까지 4, 3→4(1)로 4까지 5예요.
예시 2
입력
n = 3, edges = [[0, 1, 4]], start = 0
출력
[0, 4, -1]
설명
2번 정점으로는 갈 수 없어요.

제한 사항

  • 1 ≤ n ≤ 100,000
  • 0 ≤ edges.length ≤ 300,000
  • 0 ≤ u, v, start < n, 0 ≤ w ≤ 10,000
인접 리스트를 만들고 거리 배열을 무한대로, 시작점을 0으로 둬요. [거리, 정점]을 힙에 넣고 가장 가까운 것을 꺼내요. 꺼낸 거리가 기록보다 크면 건너뛰고, 아니면 이웃의 거리를 줄일 수 있을 때 갱신해 힙에 넣어요. 끝나고 무한대는 -1로 바꿔 반환해요.
javascript
class MinHeap {
  /** @param {(a: any, b: any) => number} [compare] 음수면 a가 먼저 나옵니다. */
  constructor(compare) {
    this.items = [];
    this.compare = compare ?? ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }
​
  get size() {
    return this.items.length;
  }
​
  peek() {
    return this.items.length > 0 ? this.items[0] : null;
  }
​
  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[parent], a[i]) <= 0) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
​
  pop() {
    const a = this.items;
    if (a.length === 0) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let small = i;
        if (l < a.length && this.compare(a[l], a[small]) < 0) small = l;
        if (r < a.length && this.compare(a[r], a[small]) < 0) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}
​
function dijkstra(n, edges, start) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) graph[u].push([v, w]);
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  const heap = new MinHeap((a, b) => a[0] - b[0]);
  heap.push([0, start]);
  while (heap.size > 0) {
    const [d, v] = heap.pop();
    if (d > dist[v]) continue;
    for (const [next, w] of graph[v]) {
      if (dist[v] + w < dist[next]) {
        dist[next] = dist[v] + w;
        heap.push([dist[next], next]);
      }
    }
  }
  return dist.map((x) => (x === Infinity ? -1 : x));
}
이전 문제편집 거리
다음 문제음수 간선이 있는 최단 경로
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.