TypeScriptでダイクストラ法を実装する：最小ヒープの「古い候補」を捨てる理由とテスト

重みが負でないグラフの最短経路は、ダイクストラ法で求められます。実装でつまずきやすいのは、距離が更新された頂点を最小ヒープ内でどう扱うかです。

この記事では decrease-key を実装せず、新しい候補を追加して古い候補を捨てる 方針を採ります。ヒープ実装を小さく保ちながら、正しさを不変条件と実行可能なテストで確認します。

この実装で守ること

• 辺の重みは 0 以上です。負の重みがある場合は Bellman-Ford 法などを選びます。
• dist[v] は開始頂点から v までに見つかった最小コストです。
• ヒープから取り出した候補のコストが dist[v] と違えば、その候補は古いので展開しません。
• 到達できない頂点の距離は Infinity のままです。

「ヒープに同じ頂点が複数回入る」ことはバグではありません。たとえば A -> B をコスト 4 で登録した後、A -> C -> B をコスト 3 で見つけると、B の候補は 4 と 3 の二つになります。先に 3 を処理し、後で 4 を取り出した時点で捨てれば十分です。

最小ヒープ

ヒープは { vertex, cost } だけを保持します。頂点番号を配列の添字にし、距離表は別配列に置くため、候補の比較はコストだけで済みます。

type Edge = { to: number; weight: number };
type Entry = { vertex: number; cost: number };

class MinHeap {
  private data: Entry[] = [];

  get size() {
    return this.data.length;
  }

  push(entry: Entry) {
    this.data.push(entry);

    let i = this.data.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.data[parent].cost <= entry.cost) break;
      this.data[i] = this.data[parent];
      i = parent;
    }
    this.data[i] = entry;
  }

  pop(): Entry | undefined {
    const first = this.data[0];
    const last = this.data.pop();

    if (!first || !last || this.data.length === 0) return first;

    let i = 0;
    while (i * 2 + 1 < this.data.length) {
      let child = i * 2 + 1;

      if (
        child + 1 < this.data.length &&
        this.data[child + 1].cost < this.data[child].cost
      ) {
        child++;
      }

      if (last.cost <= this.data[child].cost) break;
      this.data[i] = this.data[child];
      i = child;
    }

    this.data[i] = last;
    return first;
  }
}

pop() の「要素が一つだけ」のケースは見落としやすい点です。先頭を取り出した後の配列が空なら、最後の要素を戻してはいけません。

ダイクストラ法本体

辺を緩和して距離が短くなったときだけ、新しい候補をヒープに追加します。decrease-key は不要です。

function dijkstra(graph: Edge[][], start: number): number[] {
  const dist = Array<number>(graph.length).fill(Infinity);
  const heap = new MinHeap();

  dist[start] = 0;
  heap.push({ vertex: start, cost: 0 });

  while (heap.size > 0) {
    const current = heap.pop()!;

    // より短い候補が既に見つかっている。
    if (current.cost !== dist[current.vertex]) continue;

    for (const edge of graph[current.vertex]) {
      if (edge.weight < 0) {
        throw new Error("Dijkstra requires non-negative weights");
      }

      const nextCost = current.cost + edge.weight;
      if (nextCost >= dist[edge.to]) continue;

      dist[edge.to] = nextCost;
      heap.push({ vertex: edge.to, cost: nextCost });
    }
  }

  return dist;
}

ここで current.cost === dist[current.vertex] なら、その頂点をこのコストで確定してよい状態です。すべての辺が非負なので、後からもっと小さい経路が現れることはありません。

動かして確認する

次のグラフでは、頂点 1 へ直接行くコストは 4 ですが、頂点 2 を経由すると 3 になります。さらに、頂点 4 は孤立させて Infinity も確認します。

const graph: Edge[][] = [
  [{ to: 1, weight: 4 }, { to: 2, weight: 1 }],
  [{ to: 3, weight: 1 }],
  [{ to: 1, weight: 2 }, { to: 3, weight: 5 }],
  [],
  [],
];

const result = dijkstra(graph, 0);

console.assert(
  JSON.stringify(result.slice(0, 4)) === JSON.stringify([0, 3, 1, 4]),
);
console.assert(result[4] === Infinity);

let negativeWeightError: unknown;
try {
  dijkstra([[{ to: 0, weight: -1 }]], 0);
} catch (error) {
  negativeWeightError = error;
}
console.assert(negativeWeightError instanceof Error);

console.log("all tests passed");

Bun 1.3.14 で実行し、all tests passed を確認しました。

計算量と使い分け

距離が短くなるたびに候補を追加するため、候補数は高々緩和回数です。この実装の計算量は O((V + E) log E)、単純グラフとして扱う場合は通常 O((V + E) log V) と見なせます。距離表は O(V)、隣接リストとヒープを含めた追加領域は O(V + E) です。

面接や実務の説明では、次の三点を先に伝えると設計意図が伝わります。

1. 負の辺を許さないので、確定済みの最短距離は後戻りしません。
2. decrease-key を省き、古い候補の破棄でヒープを単純にしています。
3. 到達不能・負の重み・単一要素ヒープをテストに含めています。

この三点をコードと一緒に説明できれば、アルゴリズムの暗記ではなく、実装上の境界まで理解していることを示せます。