最短経路アルゴリズム — ダイクストラは負の重みで壊れる

最短経路アルゴリズム。複数の道がある小さな路線模型と目的地のピン、虫眼鏡。

ダイクストラは負の重みで壊れます。最短経路のアルゴリズムを実装して、使える条件を確かめます。

前回: グラフとBFS・DFS — 循環参照で探索が止まらない

これは【深掘り】の記事です。本線の順路ではありません。 このシリーズはアルゴリズムの名前を覚える回にしません。 全部、手元で書いて、走らせて、出た数字を見ます。 飛ばしても本線は進めます。 計算量の考え方そのものは、本線の 1万件で100倍になる — 計算量とO記法を測る にあります。

この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。VM の立て方は VMを29台溜めた話 — Ubuntu Serverの立て方 にあります。


前の回まででこう理解していました。

「つながっているか」「何本で届くか」を知りたいなら BFS。 重みが全部同じなら、BFS が返す経路が最短。

これは正しいです。ただし「重みが全部同じなら」が付きます。

そして現実のグラフは、ほぼ全部、重みが違います。

  • 路線図は、区間ごとに所要時間が違う
  • 配送ルートは、区間ごとに運賃が違う
  • ネットワークは、リンクごとに遅延が違う

私はここで一度、はっきり間違えました。乗り換え案内のようなものを作ろうとして、BFS を使ったのです。

出てきた答えは「中央 → 空港、乗り換え0回」でした。正しそうに見えました。 実際にはそれは40分かかる各駅停車で、乗り換え2回のルートなら21分で着きました。

BFS は「区間の本数」を最小にしただけです。「時間」を最小にしたつもりは一度もありません。

BFS は嘘をついていません。私が、違う問題の答えを受け取って喜んでいただけです。

この記事では、「どのアルゴリズムを使うか」を暗記ではなく、条件で選べるようにします。 条件は3つだけです。負の重みがあるか。全点間が要るか。ゴールが1つで、その方向が分かるか。

そして山場は④です。ダイクストラは負の重みで壊れます。 例外も投げず、警告も出さず、平気な顔で間違った数字を返します。 それを実際に出力して見ます。

対象レベル: 中級〜上級 / 区分: 発展

目次

この記事でわかること

  • BFS が最短を返すのは「重みが全部同じとき」だけ。 重みが違うと、別の問題の答えが返る
  • ダイクストラがやっているのは1つだけ。「未確定の中で、いま一番近いところを確定させる」を繰り返す
  • ダイクストラは負の重みで静かに壊れる。 エラーにならないので、気づくのは本番の請求書
  • 壊れる理由は「一度確定させたものを二度と見直さないから」。 高速さと引き換えに捨てた前提
  • ベルマン・フォードは「全部の辺を V-1 回ゆるめるだけ」。 遅い代わりに負の重みを扱え、負の閉路まで検出できる
  • 為替の裁定取引の検出は、負の閉路の検出そのもの
  • A* は「ダイクストラ + ゴールの方向へのヒント」でしかない。 別のアルゴリズムではない
  • ヒントが本当の距離を超えると、A* は速くなる代わりに間違える
  • 最小全域木は最短経路とは別の問題。 「全部を最小コストで繋ぐ」であって「最短で行く」ではない
  • クラスカル法とプリム法は、同じ総コストを、違う辺の組み合わせで出すことがある

この記事でやること

  1. 実験用フォルダ ~/cslab/path を作り、この記事の作業を全部そこに閉じ込める
  2. 10駅の路線図を作り、BFS とダイクストラの答えを並べて出す
  3. ダイクストラを書いて、確定の様子を1行ずつ表示する。 経路も駅名で復元する
  4. 頂点1000〜20000で、素朴な実装とヒープ版を実測して比べる
  5. 負の重みを1本だけ入れて、ダイクストラが静かに間違えるところを出力する
  6. ベルマン・フォードで正しい答えを出し、負の閉路の検出と裁定取引の検出まで作る
  7. 格子迷路を作り、ダイクストラ / A* / BFS / DFS の「調べたマスの数」を数えて比べる
  8. 最小全域木を、クラスカル法(Union-Find つき)とプリム法の両方で解く

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
重み(コスト)辺に付いた数。所要時間・運賃・遅延など。「1本」ではなく「何分」
緩和(relax)「そこを経由したほうが近いなら、記録を書き換える」こと。最短経路の全アルゴリズムがこれしかしていない
確定(settle)その頂点までの最短がもう変わらないと決めること。ここが負の重みで崩れる
prev 配列「その頂点に、どこから来たか」の記録。逆にたどると経路が出る
負の閉路一周すると合計が減る輪。回るほど小さくなるので、最短経路が存在しない
ヒューリスティックゴールまでの見積り。A\* が使う「ヒント」
許容的(admissible)ヒントが本当の距離を絶対に超えないこと。これが崩れると A* の答えが狂う
マンハッタン距離縦の差 + 横の差。斜めに進めない格子での最短距離
全域木全部の頂点を繋ぐ、輪の無い辺の集まり。頂点が V 個なら辺は必ず V-1 本
Union-Find「この2つは、もう繋がっているか?」だけを高速に答える道具

① 題材を作る — 同じグラフで BFS とダイクストラを比べる

実験用のフォルダを作ります。最後に消します。

bash
$ mkdir -p ~/cslab/path
$ cd ~/cslab/path
$ node -v
v22.14.0

node が無ければ、「1」と 1 は等しい — JavaScriptの基本 を先に見てください。

10駅の路線図を作ります。 区間ごとに所要時間(分)が違います。

bash
$ nano graph.mjs
// 路線図: 10駅と、所要時間(分)つきの区間。線路は両方向に行ける。
export const EDGES = [
  ["中央", "北口", 3],
  ["中央", "東町", 5],
  ["中央", "空港", 40],
  ["北口", "大学前", 5],
  ["東町", "大学前", 2],
  ["大学前", "港", 6],
  ["港", "空港", 8],
  ["東町", "西谷", 9],
  ["西谷", "空港", 12],
  ["北口", "山手", 7],
  ["山手", "南台", 4],
  ["南台", "港", 5],
  ["東町", "桜坂", 3],
  ["桜坂", "南台", 6],
];

// 隣接リスト: { 駅名: [{ to, w }, ...] }
export function buildGraph(edges = EDGES) {
  const g = {};
  for (const [a, b, w] of edges) {
    (g[a] ??= []).push({ to: b, w });
    (g[b] ??= []).push({ to: a, w });
  }
  return g;
}

// prev から経路を復元する
export function restore(prev, goal) {
  if (!(goal in prev)) return null;
  const path = [];
  for (let v = goal; v !== null && v !== undefined; v = prev[v]) path.push(v);
  return path.reverse();
}

// 経路の合計時間を出す(答え合わせ用)
export function pathCost(g, path) {
  let sum = 0;
  for (let i = 0; i + 1 < path.length; i++) {
    const e = g[path[i]].find((x) => x.to === path[i + 1]);
    if (!e) return Infinity;
    sum += e.w;
  }
  return sum;
}

注目してほしいのは3行目の ["中央", "空港", 40] です。

中央から空港へ、乗り換え無しで行ける線があります。ただし40分かかります。

これが罠です。図にするとこうです。

中央 ─3─ 北口 ─5─ 大学前 ─6─ 港 ─8─ 空港
 │        └─7─ 山手 ─4─ 南台 ─5─ 港
 ├─5─ 東町 ─2─ 大学前
 │      ├─9─ 西谷 ─12─ 空港
 │      └─3─ 桜坂 ─6─ 南台
 └─40─ 空港                        ← 直通。ただし40分

同じ駅名が何度も出てきますが、駅は10個です。 正は graph.mjs の EDGES です。

BFS とダイクストラを、同じグラフで走らせます。

bash
$ nano compare.mjs
import { buildGraph, restore, pathCost } from "./graph.mjs";

// BFS: 重みを見ない。区間の「本数」だけを最小にする
function bfs(g, start, goal) {
  const prev = { [start]: null };
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const v = queue[head++];
    if (v === goal) break;
    for (const { to } of g[v]) {
      if (to in prev) continue;
      prev[to] = v;
      queue.push(to);
    }
  }
  return restore(prev, goal);
}

// ダイクストラ: 重みを足した合計を最小にする
function dijkstra(g, start, goal) {
  const dist = {}, prev = {}, done = {};
  for (const v of Object.keys(g)) dist[v] = Infinity;
  dist[start] = 0;
  prev[start] = null;
  for (;;) {
    let u = null;
    for (const v of Object.keys(g)) {
      if (done[v]) continue;
      if (u === null || dist[v] < dist[u]) u = v;
    }
    if (u === null || dist[u] === Infinity) break;
    done[u] = true;
    for (const { to, w } of g[u]) {
      if (dist[u] + w < dist[to]) { dist[to] = dist[u] + w; prev[to] = u; }
    }
  }
  return restore(prev, goal);
}

const g = buildGraph();
for (const [name, fn] of [["BFS      ", bfs], ["ダイクストラ", dijkstra]]) {
  const p = fn(g, "中央", "空港");
  console.log(`${name} 経路: ${p.join(" → ")}`);
  console.log(`${name} 区間数: ${p.length - 1} 本 / 合計: ${pathCost(g, p)} 分`);
}
bash
$ node compare.mjs
BFS       経路: 中央 → 空港
BFS       区間数: 1 本 / 合計: 40 分
ダイクストラ 経路: 中央 → 東町 → 大学前 → 港 → 空港
ダイクストラ 区間数: 4 本 / 合計: 21 分

これが、私が最初に踏んだ間違いそのものです。

経路区間数合計時間
BFS中央 → 空港1本(最小)40分
ダイクストラ中央 → 東町 → 大学前 → 港 → 空港4本21分(最小)

どちらも「最短」を返しています。何の最短かが違うだけです。

  • BFS が最小にしたのは「区間の本数」。乗り換えを減らしたいならこれで正しい
  • ダイクストラが最小にしたのは「合計時間」

「乗り換えの少ない順」と「早い順」が乗り換え案内アプリに両方あるのは、この2つが別の問題だからです。

BFS は「重みが全部1のダイクストラ」です。 だから重みが全部同じなら一致し、違えばずれます。

BFS が使っているキューと、DFS が使っているスタックの違いは、call stack size exceeded の正体 — コンピュータ科学深掘り にあります。


② ダイクストラ法 — 「いま一番近いところ」を確定させるだけ

ダイクストラは、たった1つのことを繰り返しています。

まだ確定していない頂点の中で、いま一番近いものを選ぶ。それを確定させる。 そこを経由したほうが近くなる隣を、書き換える。

これだけです。「なぜそれで正しいのか」を先に書きます。

未確定の中で一番近い頂点 u を考えます。 u より近い未確定の頂点はもうありません。 すべての重みが0以上なら、これから先どこを回っても距離は増えるだけです。 だから u にこれより短い行き方は存在しません。確定させてよい。

「すべての重みが0以上なら」。ここに全部が乗っています。 ④で崩します。

動きが見えるように、確定するたびに表示します。

bash
$ nano dijkstra.mjs
import { buildGraph, restore } from "./graph.mjs";

// 素朴なダイクストラ。毎回「未確定の中で一番近いもの」を全部から探す = O(V^2)
export function dijkstra(g, start, trace = false) {
  const dist = {}, prev = {}, done = {};
  for (const v of Object.keys(g)) dist[v] = Infinity;
  dist[start] = 0;
  prev[start] = null;

  for (;;) {
    // ① 未確定の中で一番近い頂点を選ぶ
    let u = null;
    for (const v of Object.keys(g)) {
      if (done[v]) continue;
      if (u === null || dist[v] < dist[u]) u = v;
    }
    if (u === null || dist[u] === Infinity) break;

    // ② それを「確定」させる。二度と見直さない
    done[u] = true;
    if (trace) console.log(`確定: ${u} (${dist[u]}分)`);

    // ③ そこを経由したほうが近くなる隣を、緩める(relax)
    for (const { to, w } of g[u]) {
      if (done[to]) continue;
      if (dist[u] + w < dist[to]) {
        dist[to] = dist[u] + w;
        prev[to] = u;
        if (trace) console.log(`    └ ${to} を ${dist[to]}分 に更新`);
      }
    }
  }
  return { dist, prev };
}

const g = buildGraph();
const { dist, prev } = dijkstra(g, "中央", true);
console.log("--- 中央からの所要時間 ---");
for (const v of Object.keys(g).sort((a, b) => dist[a] - dist[b])) {
  console.log(`${v.padEnd(4, " ")} ${String(dist[v]).padStart(3)}分  ${restore(prev, v).join(" → ")}`);
}
bash
$ node dijkstra.mjs
確定: 中央 (0分)
    └ 北口 を 3分 に更新
    └ 東町 を 5分 に更新
    └ 空港 を 40分 に更新
確定: 北口 (3分)
    └ 大学前 を 8分 に更新
    └ 山手 を 10分 に更新
確定: 東町 (5分)
    └ 大学前 を 7分 に更新
    └ 西谷 を 14分 に更新
    └ 桜坂 を 8分 に更新
確定: 大学前 (7分)
    └ 港 を 13分 に更新
確定: 桜坂 (8分)
    └ 南台 を 14分 に更新
確定: 山手 (10分)
確定: 港 (13分)
    └ 空港 を 21分 に更新
確定: 西谷 (14分)
確定: 南台 (14分)
確定: 空港 (21分)
--- 中央からの所要時間 ---
中央     0分  中央
北口     3分  中央 → 北口
東町     5分  中央 → 東町
大学前    7分  中央 → 東町 → 大学前
桜坂     8分  中央 → 東町 → 桜坂
山手    10分  中央 → 北口 → 山手
港     13分  中央 → 東町 → 大学前 → 港
西谷    14分  中央 → 東町 → 西谷
南台    14分  中央 → 東町 → 桜坂 → 南台
空港    21分  中央 → 東町 → 大学前 → 港 → 空港

スクリーンショットを撮ってください: 01_dijkstra_trace.png 確定の順番が 0 → 3 → 5 → 7 → 8 → 10 → 13 → 14 → 14 → 21 と、必ず増えていくのが見える画面。

この出力の読みどころは4つあります。

1つ目。確定した距離は必ず増えていきます。 0, 3, 5, 7, 8, 10, 13, 14, 14, 21。 これは偶然ではありません。「未確定の中で最小」を取り続けているのだから、必ず単調に増えます。 逆に言えば、この単調性が崩れたらダイクストラは壊れます。 ④で見ます。

2つ目。大学前 が2回書き換わっています。

確定: 北口 (3分)
    └ 大学前 を 8分 に更新     ← 中央 → 北口 → 大学前
確定: 東町 (5分)
    └ 大学前 を 7分 に更新     ← 中央 → 東町 → 大学前 のほうが速い

確定する前なら、何度でも書き換わります。 確定した瞬間から書き換わりません。

3つ目。空港 は最初 40分 でした。 直通があるからです。 そして最後に 港 が確定したとき、21分に上書きされました。 「一番安いと思っていた案が、後から更新される」のが緩和です。

4つ目。経路は prev を逆にたどるだけで出ます。

for (let v = goal; v !== null; v = prev[v]) path.push(v);
return path.reverse();

距離だけ求めて経路を出せないコードを、私は一度書きました。 dist は「いくらか」しか持っていません。「どこから来たか」を1行足すだけで経路が出るので、最初から入れておきます。

「一番近い」を毎回全部から探している

このコードの弱点は、明らかに ① の部分です。

for (const v of Object.keys(g)) { ... }   // 毎回 V 個ぜんぶ見る

頂点1つを確定させるたびに V 個を見るので、全体で O(V²)。 駅10個なら誰も困りません。 頂点が数万になると困ります。 次で測ります。


③ 優先度付きキューで速くする

「未確定の中で一番小さいものを取り出す」。 これは前の回でヒープを書いたときの動作そのものです。

10件欲しいだけで100万件ソート — コンピュータ科学深掘り で作った最小ヒープが、そのまま使えます。

bash
$ nano heap.mjs
// 最小ヒープ。[優先度, 中身] を入れて、いつでも一番小さいものが取り出せる
export class MinHeap {
  constructor() { this.a = []; }
  get size() { return this.a.length; }
  push(pri, val) {
    this.a.push([pri, val]);
    let i = this.a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p][0] <= this.a[i][0]) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  pop() {
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) {
      this.a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1, r = l + 1;
        let m = i;
        if (l < this.a.length && this.a[l][0] < this.a[m][0]) m = l;
        if (r < this.a.length && this.a[r][0] < this.a[m][0]) m = r;
        if (m === i) break;
        [this.a[m], this.a[i]] = [this.a[i], this.a[m]];
        i = m;
      }
    }
    return top;
  }
}

ヒープを使ったダイクストラで、1つだけ気をつける点があります。

「距離が縮んだら、ヒープに入れ直す」。古いほうは消さない。取り出したとき無視する。

ヒープの途中の要素を書き換えるのは面倒です。 だから入れっぱなしにして、確定済みなら捨てるという手抜きをします。これが標準的なやり方です。

bash
$ nano bench-heap.mjs
import { MinHeap } from "./heap.mjs";

// 頂点 V 個、1頂点あたり平均 deg 本の辺を持つランダムなグラフを作る
function randomGraph(V, deg) {
  const g = Array.from({ length: V }, () => []);
  for (let v = 0; v < V; v++) {
    for (let k = 0; k < deg; k++) {
      const to = Math.floor(Math.random() * V);
      if (to === v) continue;
      const w = 1 + Math.floor(Math.random() * 100);
      g[v].push({ to, w });
      g[to].push({ to: v, w });
    }
  }
  return g;
}

// 素朴版: 毎回 V 個ぜんぶを見て最小を探す → O(V^2 + E)
function dijkstraNaive(g, start) {
  const V = g.length;
  const dist = new Float64Array(V).fill(Infinity);
  const done = new Uint8Array(V);
  dist[start] = 0;
  for (let n = 0; n < V; n++) {
    let u = -1;
    for (let v = 0; v < V; v++) if (!done[v] && (u === -1 || dist[v] < dist[u])) u = v;
    if (u === -1 || dist[u] === Infinity) break;
    done[u] = 1;
    for (const { to, w } of g[u]) if (dist[u] + w < dist[to]) dist[to] = dist[u] + w;
  }
  return dist;
}

// ヒープ版: 最小を取り出すのが O(log V) → O((V + E) log V)
function dijkstraHeap(g, start) {
  const V = g.length;
  const dist = new Float64Array(V).fill(Infinity);
  const done = new Uint8Array(V);
  dist[start] = 0;
  const h = new MinHeap();
  h.push(0, start);
  while (h.size) {
    const [d, u] = h.pop();
    if (done[u]) continue;      // 古い情報。捨てる
    done[u] = 1;
    for (const { to, w } of g[u]) {
      if (d + w < dist[to]) { dist[to] = d + w; h.push(dist[to], to); }
    }
  }
  return dist;
}

function bench(fn, runs = 7) {
  const t = [];
  for (let i = 0; i < runs; i++) {
    const t0 = performance.now();
    fn();
    t.push(performance.now() - t0);
  }
  t.sort((a, b) => a - b);
  return t[t.length >> 1];
}

for (const V of [1000, 5000, 20000]) {
  const g = randomGraph(V, 5);
  const E = g.reduce((s, a) => s + a.length, 0) / 2;
  const a = dijkstraNaive(g, 0), b = dijkstraHeap(g, 0);
  let same = true;
  for (let i = 0; i < V; i++) if (a[i] !== b[i]) same = false;
  const tn = bench(() => dijkstraNaive(g, 0));
  const th = bench(() => dijkstraHeap(g, 0));
  console.log(`V=${String(V).padStart(5)} E=${String(E).padStart(6)}  素朴 ${tn.toFixed(1).padStart(8)}ms  ヒープ ${th.toFixed(1).padStart(6)}ms  ${(tn / th).toFixed(1)}倍  答えは${same ? "一致" : "不一致"}`);
}
bash
$ node bench-heap.mjs
V= 1000 E=  4994  素朴      4.1ms  ヒープ    2.9ms  1.4倍  答えは一致
V= 5000 E= 24998  素朴     98.2ms  ヒープ   12.5ms  7.8倍  答えは一致
V=20000 E= 99993  素朴   2486.1ms  ヒープ  137.6ms  18.1倍  答えは一致

まず答えが一致していることを確認しました。 速い実装を作ったら、必ず遅い実装と突き合わせます。

そのうえで、増え方を見ます。

V素朴ヒープ素朴が V=1000 の何倍かヒープが V=1000 の何倍か
1,0004.1ms2.9ms1倍1倍
5,00098.2ms12.5ms24倍4.3倍
20,0002486.1ms137.6ms606倍47倍

頂点を20倍にしたら、素朴版は606倍になりました。 20² = 400 に近い増え方です。O(V²) の形です。 ヒープ版は47倍。 辺も20倍に増えているので、E log V におおよそ沿っています。

注意: V=1000 では1.4倍しか違いません。 小さいうちは差が出ない。 「速い実装に書き換えたのに速くならない」ときは、まずデータが小さすぎないかを疑います。 データが10倍で100倍遅くなる — コンピュータ科学深掘り で見た通りです。

辺が少ない(疎な)グラフではヒープ版が圧勝します。 逆にほとんど全部の頂点が繋がっている(密な)グラフでは、素朴版のほうが速いこともあります。 E ≈ V² なら O(V²) と O(V² log V) の勝負になるからです。


④ ダイクストラは負の重みで、エラーも出さずに間違える

ここが、この記事で一番伝えたいところです。

「負の重み」は、実務にふつうに出てきます。

  • 補助金・キャッシュバックのある配送区間
  • ポイント還元のある決済経路
  • 利益の出る取引(後で見る為替)

そういうグラフでダイクストラを使うと、どうなるか。 4地点のグラフで見ます。

bash
$ nano routes.mjs
// 一方通行の配送ルート。単位は万円。倉庫B→倉庫A だけ補助金が出て「-3」
export const ROUTES = [
  ["拠点", "倉庫A", 1],
  ["拠点", "倉庫B", 2],
  ["倉庫B", "倉庫A", -3],
  ["倉庫A", "納品先", 1],
];
export const NODES = ["拠点", "倉庫A", "倉庫B", "納品先"];

// 一方通行の隣接リストを作る
export function directed(edges) {
  const g = {};
  for (const [a, b, w] of edges) {
    (g[a] ??= []).push({ to: b, w });
    g[b] ??= [];
  }
  return g;
}

目で見て答えを出しておきます。

拠点 → 倉庫A → 納品先          = 1 + 1        = 2
拠点 → 倉庫B → 倉庫A → 納品先  = 2 + (-3) + 1 = 0   ← 本当の最安

答えは 0 です。 では、ダイクストラは何と言うか。

bash
$ nano negative.mjs
import { ROUTES, directed } from "./routes.mjs";

function dijkstra(g, start) {
  const dist = {}, done = {};
  for (const v of Object.keys(g)) dist[v] = Infinity;
  dist[start] = 0;
  for (;;) {
    let u = null;
    for (const v of Object.keys(g)) {
      if (done[v]) continue;
      if (u === null || dist[v] < dist[u]) u = v;
    }
    if (u === null || dist[u] === Infinity) break;
    done[u] = true;
    console.log(`確定: ${u} (${dist[u]})`);
    for (const { to, w } of g[u]) {
      if (done[to]) { console.log(`    × ${to} は確定済み。${dist[u] + w} でも見直さない`); continue; }
      if (dist[u] + w < dist[to]) { dist[to] = dist[u] + w; console.log(`    └ ${to} → ${dist[to]}`); }
    }
  }
  return dist;
}

// 全部の経路を総当たりで数える(正解を出す遅い版)
function bruteForce(g, start, goal) {
  let best = Infinity, bestPath = null;
  const walk = (v, cost, path) => {
    if (v === goal && best > cost) { best = cost; bestPath = [...path]; }
    for (const { to, w } of g[v]) {
      if (path.includes(to)) continue;      // 同じ地点を2度通らない
      path.push(to);
      walk(to, cost + w, path);
      path.pop();
    }
  };
  walk(start, 0, [start]);
  return { best, bestPath };
}

const g = directed(ROUTES);
const dist = dijkstra(g, "拠点");
console.log("--- ダイクストラの答え ---");
console.log(dist);
const { best, bestPath } = bruteForce(g, "拠点", "納品先");
console.log("--- 総当たりで出した本当の答え ---");
console.log(`納品先まで ${best}: ${bestPath.join(" → ")}`);
bash
$ node negative.mjs
確定: 拠点 (0)
    └ 倉庫A → 1
    └ 倉庫B → 2
確定: 倉庫A (1)
    └ 納品先 → 2
確定: 倉庫B (2)
    × 倉庫A は確定済み。-1 でも見直さない
確定: 納品先 (2)
--- ダイクストラの答え ---
{ '拠点': 0, '倉庫A': 1, '倉庫B': 2, '納品先': 2 }
--- 総当たりで出した本当の答え ---
納品先まで 0: 拠点 → 倉庫B → 倉庫A → 納品先

ダイクストラは「2」と答えました。本当の答えは「0」です。

例外は投げていません。警告も出していません。Infinity でもありません。それらしい数字が返っています。

これが一番怖い壊れ方です。 落ちてくれるバグは気づけますが、正しい形の間違った数字は気づけません。

なぜ壊れたのか。 出力の1行が全部を語っています。

    × 倉庫A は確定済み。-1 でも見直さない

順番を追います。

  1. 拠点 を確定(0)。隣を更新して 倉庫A = 1、倉庫B = 2
  2. 未確定の中で一番近いのは 倉庫A(1)。 だから 倉庫A を確定させる
  3. 倉庫A から 納品先 = 2
  4. 倉庫B(2)を確定。ここで 倉庫B → 倉庫A が -3 なので 2 - 3 = -1
  5. でも 倉庫A はもう確定済み。二度と見直さない

ダイクストラの正しさは、②で書いた1行に全部乗っていました。

「これから先どこを回っても距離は増えるだけ」だから、いま一番近いものを確定させてよい。

負の重みがあると、この前提が消えます。 遠回りしたほうが安くなるからです。 「いま一番近い」は「最終的に一番近い」ではなくなりました。

つまり、これは実装のバグではありません。前提が満たされていないところにアルゴリズムを使った、という間違いです。

「じゃあ全部の重みに一律で足せばいいのでは?」

私が最初に考えた回避策です。 一番小さい重みが -3 なら、全部の辺に +3 すれば全部0以上になる。

これは間違いです。 理由は1行で言えます。

辺の本数が違う経路には、足される量が違うから。

  • 拠点 → 倉庫A → 納品先 は 2本 なので +6 されて 2 → 8
  • 拠点 → 倉庫B → 倉庫A → 納品先 は 3本 なので +9 されて 0 → 9

ひっくり返りました。 辺の多い経路ほど不利になるので、答えが変わります。 (すべての経路の辺の本数が同じと保証できるなら成立しますが、そんなグラフはめったにありません。)


⑤ ベルマン・フォード法 — 全部の辺を V-1 回ゆるめるだけ

負の重みを扱えるアルゴリズムは、驚くほど単純です。

全部の辺を順に見て、縮むなら縮める。それを V-1 回繰り返す。

優先順位という考えがありません。「確定」もありません。 だから確定の前提が壊れる心配もありません。

なぜ V-1 回で足りるのか。

  • 最短経路が同じ頂点を2回通ることはない(負の閉路が無いなら)
  • だから最短経路の辺は最大 V-1 本
  • 1周ごとに、最短経路の辺が少なくとも1本ずつ正しく確定していく
bash
$ nano bellman.mjs
import { ROUTES, NODES } from "./routes.mjs";
import { restore } from "./graph.mjs";

// ベルマン・フォード: 全部の辺を V-1 回ゆるめるだけ。優先順位という考えが無い
export function bellmanFord(edges, vertices, start) {
  const dist = {}, prev = {};
  for (const v of vertices) dist[v] = Infinity;
  dist[start] = 0;
  prev[start] = null;

  for (let i = 1; i <= vertices.length - 1; i++) {
    let changed = false;
    for (const [a, b, w] of edges) {
      if (dist[a] === Infinity) continue;
      if (dist[a] + w < dist[b]) { dist[b] = dist[a] + w; prev[b] = a; changed = true; }
    }
    console.log(`${i}周目: ${JSON.stringify(dist)}`);
    if (!changed) { console.log(`${i}周目で変化なし。ここで打ち切れる`); break; }
  }

  // V 周目でまだ縮むなら、負の閉路がある = 最短経路は存在しない
  for (const [a, b, w] of edges) {
    if (dist[a] !== Infinity && dist[a] + w < dist[b]) {
      return { dist, prev, negativeCycle: [a, b, w] };
    }
  }
  return { dist, prev, negativeCycle: null };
}

const r = bellmanFord(ROUTES, NODES, "拠点");
console.log("--- ベルマン・フォードの答え ---");
console.log(r.dist);
console.log("経路:", restore(r.prev, "納品先").join(" → "));
console.log("負の閉路:", r.negativeCycle ?? "なし");
bash
$ node bellman.mjs
1周目: {"拠点":0,"倉庫A":-1,"倉庫B":2,"納品先":0}
2周目: {"拠点":0,"倉庫A":-1,"倉庫B":2,"納品先":0}
2周目で変化なし。ここで打ち切れる
--- ベルマン・フォードの答え ---
{ '拠点': 0, '倉庫A': -1, '倉庫B': 2, '納品先': 0 }
経路: 拠点 → 倉庫B → 倉庫A → 納品先
負の閉路: なし

納品先: 0。総当たりの答えと一致しました。 経路も 拠点 → 倉庫B → 倉庫A → 納品先 で正解です。

changed が false なら途中で打ち切っています。 上限は V-1 回ですが、実際にはもっと早く落ち着くことがほとんどです。この一行で実用的な速さになります。

代わりに遅い

ベルマン・フォードは O(V × E) です。

計算量負の重み使いどころ
ダイクストラ(ヒープ)O((V+E) log V)不可重みが全部0以上。ほとんどの場合
ベルマン・フォードO(V × E)可負の重みがある / 負の閉路を検出したい

③で測った V=20000・E=100000 のグラフで比べると、V × E = 20億。 ヒープ版のダイクストラは (V+E) log V ≈ 170万 相当でした。1000倍以上の差です。

負の重みが無いなら、絶対にベルマン・フォードを選ばない。

負の閉路 — 「最短経路が存在しない」を検出する

負の重みには、もう一段面倒な話があります。

回るたびに合計が減る輪があると、最短経路は「存在しません」。

無限に回れば、いくらでも小さくできるからです。 下限がありません。

bash
$ nano cycle.mjs
import { bellmanFord } from "./bellman.mjs";

// 回るたびに合計が -1 ずつ減る輪を混ぜたグラフ
const EDGES = [
  ["拠点", "X", 0],
  ["X", "Y", 1],
  ["Y", "Z", -3],
  ["Z", "X", 1],
  ["Z", "出口", 2],
];
const r = bellmanFord(EDGES, ["拠点", "X", "Y", "Z", "出口"], "拠点");
console.log("--- 結果 ---");
if (r.negativeCycle) {
  const [a, b, w] = r.negativeCycle;
  console.log(`負の閉路を検出: ${a} → ${b} (${w}) がまだ縮む`);
  console.log("この向きに最短経路は存在しない(回るほど小さくなるので下限が無い)");
} else {
  console.log(r.dist);
}

bellman.mjs は読み込まれた時点で自分の実験も走ります。 出力の後半だけを見てください。

bash
$ node cycle.mjs
1周目: {"拠点":0,"X":-1,"Y":1,"Z":-2,"出口":0}
2周目: {"拠点":0,"X":-2,"Y":0,"Z":-3,"出口":-1}
3周目: {"拠点":0,"X":-3,"Y":-1,"Z":-4,"出口":-2}
4周目: {"拠点":0,"X":-4,"Y":-2,"Z":-5,"出口":-3}
--- 結果 ---
負の閉路を検出: X → Y (1) がまだ縮む
この向きに最短経路は存在しない(回るほど小さくなるので下限が無い)

1周ごとに、全部の値が 1 ずつ減り続けています。 X が -1, -2, -3, -4。止まりません。

検出のしかたは1行です。「V-1 回まわしたあと、もう1回まわしてまだ縮むなら、負の閉路がある」。

輪の合計は 1 + (-3) + 1 = -1。 一周するたびに -1 されます。

実例 — 為替の裁定取引の検出は、これそのもの

「通貨を順に交換して元の通貨に戻ってきたとき、増えていたら儲かる」。 これを裁定(アービトラージ)と言います。

問題の形はこうです。

辺の重みは「掛け算」(レート)。輪を一周した積が 1 を超えたら儲かる。

でも最短経路のアルゴリズムは足し算しか扱えません。 ここで対数を使います。

積 r1 × r2 × r3 > 1
両辺の log を取る:  log r1 + log r2 + log r3 > 0
符号を反転:        (-log r1) + (-log r2) + (-log r3) < 0

重みを -log(レート) にすれば、「儲かる輪」が「負の閉路」になります。 掛け算が足し算に変わりました。

bash
$ nano arbitrage.mjs
// 為替レート: FROM 1単位 = TO いくら
const RATES = [
  ["USD", "JPY", 150.0],
  ["JPY", "EUR", 0.0062],
  ["EUR", "USD", 1.09],
  ["JPY", "USD", 1 / 150.5],
  ["EUR", "JPY", 160.0],
  ["USD", "EUR", 0.915],
];
const NODES = ["USD", "JPY", "EUR"];

// 掛け算を足し算に変える。-log を重みにすると「積 > 1」が「和 < 0」になる
const edges = RATES.map(([a, b, r]) => [a, b, -Math.log(r)]);

const dist = {}, prev = {};
for (const v of NODES) dist[v] = 0;   // どこから始めても良いので全部0にする
for (let i = 1; i <= NODES.length - 1; i++) {
  for (const [a, b, w] of edges) {
    if (dist[a] + w < dist[b] - 1e-12) { dist[b] = dist[a] + w; prev[b] = a; }
  }
}

let hit = null;
for (const [a, b, w] of edges) if (dist[a] + w < dist[b] - 1e-12) hit = b;

if (!hit) {
  console.log("裁定の輪は見つかりませんでした");
} else {
  for (let i = 0; i < NODES.length; i++) hit = prev[hit];   // 確実に輪の上に乗せる
  const cycle = [hit];
  for (let v = prev[hit]; v !== hit; v = prev[v]) cycle.push(v);
  cycle.push(hit);
  cycle.reverse();
  let mul = 1;
  for (let i = 0; i + 1 < cycle.length; i++) {
    mul *= RATES.find(([a, b]) => a === cycle[i] && b === cycle[i + 1])[2];
  }
  console.log("負の閉路を検出:", cycle.join(" → "));
  console.log("1単位が", mul.toFixed(6), "単位になる(1を超えたら儲かる輪)");
}
bash
$ node arbitrage.mjs
負の閉路を検出: JPY → EUR → USD → JPY
1単位が 1.013700 単位になる(1を超えたら儲かる輪)

1円が 1.0137 円になる輪が見つかりました。

これは架空のレートです。 現実の市場では、こうした差は数秒で消えます。ここで確かめたのは「儲け方」ではなく、「掛け算の問題を足し算に変換して既存のアルゴリズムに載せた」という一点です。

問題を解くのではなく、既に解ける形に変形する。 これは競技プログラミングでも実務でも一番よく使う手です。

- 1e-12 を入れているのは、0.1+0.2が0.3にならない — コンピュータ科学深掘り の話そのままです。 log を足すと誤差が出るので、ぴったり0の比較をしないようにしています。これを入れないと、儲からない輪を「儲かる」と誤検出しました。


⑥ A\* — ダイクストラに「ゴールの方向へのヒント」を足しただけ

ダイクストラの弱点は、目的地が1つでも分かります。

ダイクストラは「ゴールがどっちにあるか」を一切知りません。 だから全方向に均等に広がります。

「ゴールは南東にある」と分かっているなら、北西を調べるのは無駄です。 それを組み込んだのが A\* です。

違いは、優先度に足す1項だけです。

ダイクストラ: 優先度 = g            (g = ここまでの実費)
A*:          優先度 = g + h(v)     (h = そこからゴールまでの見積り)

h が常に 0 なら、A\ はダイクストラそのものです。 つまりダイクストラは A\ の特別な場合です。

格子迷路で確かめます。

bash
$ nano maze.mjs
// 迷路を作る。乱数の種を固定するので、何度走らせても同じ迷路が出る
let seed = 20261003;
const rnd = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;

export const W = 31, H = 21;   // 奇数にする

export function makeMaze() {
  const m = Array.from({ length: H }, () => new Array(W).fill("#"));
  const stack = [[1, 1]];
  m[1][1] = ".";
  while (stack.length) {                       // 穴を掘って一本道の迷路を作る
    const [x, y] = stack[stack.length - 1];
    const dirs = [[2, 0], [-2, 0], [0, 2], [0, -2]].sort(() => rnd() - 0.5);
    let moved = false;
    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (nx <= 0 || ny <= 0 || nx >= W - 1 || ny >= H - 1) continue;
      if (m[ny][nx] === ".") continue;
      m[y + dy / 2][x + dx / 2] = ".";
      m[ny][nx] = ".";
      stack.push([nx, ny]);
      moved = true;
      break;
    }
    if (!moved) stack.pop();
  }
  // 壁をいくつか壊して「回り道」を作る。一本道のままだと どのやり方でも同じ答えになる
  let broken = 0;
  while (broken < 60) {
    const x = 1 + Math.floor(rnd() * (W - 2));
    const y = 1 + Math.floor(rnd() * (H - 2));
    if (m[y][x] !== "#") continue;
    m[y][x] = ".";
    broken++;
  }
  return m;
}

export const START = [1, 1];
export const GOAL = [W - 2, H - 2];

export function show(m, path = [], seen = null) {
  const g = m.map((r) => [...r]);
  if (seen) for (const k of seen) {
    const [x, y] = k.split(",").map(Number);
    if (g[y][x] === ".") g[y][x] = "+";
  }
  for (const [x, y] of path) g[y][x] = "o";
  g[START[1]][START[0]] = "S";
  g[GOAL[1]][GOAL[0]] = "G";
  return g.map((r) => r.join("")).join("\n");
}

export function neighbors(m, x, y) {
  const out = [];
  for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
    const nx = x + dx, ny = y + dy;
    if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
    if (m[ny][nx] === "#") continue;
    out.push([nx, ny]);
  }
  return out;
}

乱数の種を固定しています。 毎回違う迷路だと、アルゴリズムの差なのか迷路の差なのか分からなくなるからです。

迷路を見ておきます。

bash
$ nano showmaze.mjs
import { makeMaze, show } from "./maze.mjs";
console.log(show(makeMaze()));
bash
$ node showmaze.mjs
###############################
#S....#.......................#
#####.#..#.##..###.###.######.#
#...#...#...#...............#.#
#.#.###.#.#.##.####.#.#.#.###.#
#.#.......#.........#.#.......#
#.#.###...#..#.##.###.#...#####
#.....#.#...........#.........#
#.###.#.#.####......#.###.#####
#.#.....#.....#.......#.......#
#.#...#.###.#..#...###..#...#.#
#.#.#.#.#.....#.#...........#.#
#.#.#...#.##..#.##.##.#####.#.#
#.....#.#...#.#.#...........#.#
#.#.###.#...#.#.#..####.##.##.#
#.......#.......#.....#.#.....#
#.##.####.###.###.#.#.#.#..##.#
#.#...#...#.......#.#.#.#.....#
#.#.#.#####.###.#...#.#.###.#.#
#...................#.......#G#
###############################

左上が S、右下が G。 壁を60箇所壊してあるので、行き方が何通りもあります。

探索の本体を書きます。ダイクストラも A* も同じ関数です。ヒント h を差し替えるだけです。

bash
$ nano search.mjs
import { MinHeap } from "./heap.mjs";
import { neighbors, START, GOAL } from "./maze.mjs";

const key = ([x, y]) => `${x},${y}`;

function path(prev, goal) {
  const out = [];
  for (let k = key(goal); k; k = prev[k]) out.push(k.split(",").map(Number));
  return out.reverse();
}

// ダイクストラ = 「ゴールの方向」を一切知らない。ヒントが常に0のA*と同じ
// A*         = f = ここまでの実費 g + ゴールまでの見積り h
export function search(m, h, label) {
  const g = { [key(START)]: 0 };
  const prev = { [key(START)]: null };
  const done = new Set();
  const open = new MinHeap();
  open.push(h(...START), START);
  let popped = 0;

  while (open.size) {
    const [, cur] = open.pop();
    const k = key(cur);
    if (done.has(k)) continue;
    done.add(k);
    popped++;
    if (k === key(GOAL)) break;
    for (const nb of neighbors(m, ...cur)) {
      const nk = key(nb);
      const ng = g[k] + 1;                    // 1マス進むコストは1
      if (nk in g && g[nk] <= ng) continue;
      g[nk] = ng;
      prev[nk] = k;
      open.push(ng + h(...nb), nb);
    }
  }
  const p = path(prev, GOAL);
  console.log(`${label.padEnd(22)} 経路の長さ ${String(p.length - 1).padStart(3)}  調べたマス ${String(popped).padStart(4)}`);
  return { p, done };
}

3種類のヒントで走らせます。

bash
$ nano astar.mjs
import { search } from "./search.mjs";
import { makeMaze, show, GOAL } from "./maze.mjs";

const m = makeMaze();
const zero = () => 0;                                   // ヒント無し = ダイクストラ
const manhattan = (x, y) => Math.abs(x - GOAL[0]) + Math.abs(y - GOAL[1]);
const tooBig = (x, y) => manhattan(x, y) * 3;           // わざと大きすぎるヒント

const d = search(m, zero, "ダイクストラ(h=0)");
const a = search(m, manhattan, "A* (マンハッタン)");
const b = search(m, tooBig, "A* (ヒント3倍)");

console.log("--- ダイクストラが調べた範囲 (+ が調べたマス) ---");
console.log(show(m, d.p, d.done));
console.log("--- A* が調べた範囲 ---");
console.log(show(m, a.p, a.done));
bash
$ node astar.mjs
ダイクストラ(h=0)            経路の長さ  46  調べたマス  359
A* (マンハッタン)            経路の長さ  46  調べたマス  140
A* (ヒント3倍)             経路の長さ  48  調べたマス   55

3行の中に、この節の全部が入っています。

ヒント経路の長さ調べたマス判定
h = 0(ダイクストラ)46(最短)359正しい。ただし全方向を調べた
h = マンハッタン距離46(最短)140正しくて、しかも 2.6分の1しか調べていない
h = マンハッタン距離 × 348(最短ではない)55速いが間違い

調べた範囲を目で見ます。

--- ダイクストラが調べた範囲 (+ が調べたマス) ---
###############################
#Soooo#+++++++++++++++++++++++#
#####o#++#+##++###+###+######+#
#+++#ooo#+++#+++++++++++++++#+#
#+#+###o#+#+##+####+#+#+#+###+#
#+#++++ooo#+++++++++#+#+++++++#
#+#+###++o#++#+##+###+#+++#####
#+++++#+#ooooooo++++#+++++++++#
#+###+#+#+####+o++++#+###+#####
#+#+++++#+++++#oooo+++#+++++++#
#+#+++#+###+#++#++o###++#+++#+#
#+#+#+#+#+++++#+#+oooo++++++#+#
#+#+#+++#+##++#+##+##o#####+#+#
#+++++#+#+++#+#+#++++oooooo+#+#
#+#+###+#+++#+#+#++####+##o##+#
#+++++++#+++++++#+++++#+#+oooo#
#+##+####+###+###+#+#+#+#++##o#
#+#+++#+++#+++++++#+#+#+#++++o#
#+#+#+#####+###+#+++#+#+###+#o#
#+++++++++++++++++++#+++++++#G#
###############################
--- A* が調べた範囲 ---
###############################
#Soooo#.......................#
#####o#..#.##..###.###.######.#
#...#ooo#...#...............#.#
#.#.###o#.#.##.####.#.#.#.###.#
#.#....oo+#.........#.#.......#
#.#.###+oo#..#.##.###.#...#####
#.....#+#ooooooo++++#.........#
#.###.#+#+####+o+.++#.###.#####
#.#....+#+++++#oooo+++#.......#
#.#...#+###+#++#++o###..#...#.#
#.#.#.#+#..+++#.#+oooo+++...#.#
#.#.#..+#.##++#.##+##o#####.#.#
#.....#+#...#+#.#.+++oooooo.#.#
#.#.###+#...#+#.#.+####+##o##.#
#......+#....+++#.++++#+#.oooo#
#.##.####.###+###.#+#+#+#.+##o#
#.#...#...#..+++++#+#+#+#.+++o#
#.#.#.#####.###+#+++#+#+###+#o#
#..............+++++#+++++++#G#
###############################

スクリーンショットを撮ってください: 02_astar_vs_dijkstra.png 上の2枚を並べて撮ってください。ダイクストラが盤面をほぼ全部塗り、A* が左上から右下への帯だけを塗っているのが一目で分かります。

ダイクストラは、右上の何もない領域まで全部調べています。 ゴールが右下にあることを知らないからです。 A* は帯状にしか塗っていません。同じ答えを、4割の手間で出しました。

ヒントが大きすぎると、静かに間違える

h = マンハッタン距離 × 3 の行をもう一度見ます。

A* (ヒント3倍)             経路の長さ  48  調べたマス   55

調べたマスは 55。ダイクストラの 1/6.5 です。速い。 でも経路の長さが 48 になりました。最短は 46 です。

これも、エラーを出さずに間違えるタイプです。

なぜか。A* が最短を保証する条件は1つだけです。

h が、そこからゴールまでの本当の距離を、絶対に超えないこと。(許容的/admissible)

マンハッタン距離は、壁を無視した直線距離です。 壁があれば実際はもっと遠回りになります。 だから「絶対に超えない」を満たします。 これが安全なヒントである理由です。

3倍すると、この保証が消えます。 「そっちは遠い」と嘘をつかれた枝が、実は最短だった。 それを調べる前に、A\* はゴールに着いてしまいます。

ヒント性質結果
h = 0常に安全(そのままダイクストラ)最短。ただし遅い
h が本当の距離より小さい許容的最短が保証される。しかも速い
h が本当の距離ぴったり許容的の限界最短。一直線にしか調べない(理想)
h が本当の距離より大きい許容的でない速いが、最短の保証が消える

格子で h に「ユークリッド距離(斜めの直線距離)」を使うのは、斜めに進めないなら安全(小さすぎる方向)です。 逆に、単位を間違えて「メートルの距離」と「分のコスト」を足すと、簡単に大きすぎるヒントになります。 私はこれで一度やらかしました。

A* を疑うときは、まず h を 0 にしてみる。 それで答えが変われば、犯人はヒントです。


⑦ 同じ迷路を BFS / DFS / A\* で解く

⑥と同じ迷路で、BFS と DFS も走らせます。

bash
$ nano solve.mjs
import { makeMaze, neighbors, show, START, GOAL } from "./maze.mjs";
import { search } from "./search.mjs";

const key = ([x, y]) => `${x},${y}`;
const m = makeMaze();

function restore(prev, from) {
  const out = [];
  for (let k = from; k; k = prev[k]) out.push(k.split(",").map(Number));
  return out.reverse();
}

// BFS: 近いところから順に、輪のように広げる。重みが全部1なら最短が出る
function bfs() {
  const prev = { [key(START)]: null };
  const q = [START];
  let head = 0, popped = 0;
  while (head < q.length) {
    const cur = q[head++];
    popped++;
    if (key(cur) === key(GOAL)) break;
    for (const nb of neighbors(m, ...cur)) {
      if (key(nb) in prev) continue;
      prev[key(nb)] = key(cur);
      q.push(nb);
    }
  }
  return { p: restore(prev, key(GOAL)), popped };
}

// DFS: 行けるところまで行って、行き止まりで戻る。見つかるが最短とは限らない
function dfs() {
  const prev = { [key(START)]: null };
  const st = [START];
  let popped = 0;
  while (st.length) {
    const cur = st.pop();
    popped++;
    if (key(cur) === key(GOAL)) break;
    for (const nb of neighbors(m, ...cur)) {
      if (key(nb) in prev) continue;
      prev[key(nb)] = key(cur);
      st.push(nb);
    }
  }
  return { p: restore(prev, key(GOAL)), popped };
}

const b = bfs();
const d = dfs();
console.log("やり方          経路の長さ  調べたマス");
console.log(`BFS               ${String(b.p.length - 1).padStart(3)}       ${String(b.popped).padStart(4)}`);
console.log(`DFS               ${String(d.p.length - 1).padStart(3)}       ${String(d.popped).padStart(4)}`);
const manhattan = (x, y) => Math.abs(x - GOAL[0]) + Math.abs(y - GOAL[1]);
const a = search(m, manhattan, "A*");
console.log("--- DFS が見つけた経路 ---");
console.log(show(m, d.p));

BFS と DFS の違いは、q[head++] か st.pop() かの1行だけです。 前から取ればキュー(BFS)、後ろから取ればスタック(DFS)。 それだけで挙動が変わります。

bash
$ node solve.mjs
やり方          経路の長さ  調べたマス
BFS                46        359
DFS               142        264
A*                     経路の長さ  46  調べたマス  140
やり方経路の長さ調べたマス最短か
BFS46359⭕ 重みが全部1なので最短
DFS142264❌ 3倍の遠回り。でも解は見つけた
A\*46140⭕ 最短で、一番少ない手間

DFS が見つけた経路を見ます。

###############################
#Soooo#oooo...ooooo...........#
#####o#o.#o##.o###o###.######.#
#...#ooo#oo.#.o...oooo.ooo..#.#
#.#.###.#o#.##o####.#o#o#o###.#
#.#......o#...oooo..#o#o.o....#
#.#.###..o#..#.##o###o#o.o#####
#.....#.#o.......oo.#ooo.o....#
#.###.#.#o####....o.#.###o#####
#.#.....#ooo..#...o...#..o.ooo#
#.#...#.###o#..#..o###..#o.o#o#
#.#.#.#.#ooo..#.#.o..ooooo.o#o#
#.#.#...#o##..#.##o##o#####o#o#
#.....#.#o..#.#.#oo..ooo..oo#o#
#.#.###.#o..#.#.#o.####o##o##o#
#.......#ooooo..#o....#o#.o..o#
#.##.####.###o###o#.#.#o#.o##o#
#.#...#...#ooo.ooo#.#.#o#.oo.o#
#.#.#.#####o###o#...#.#o###o#o#
#..........ooooo....#..ooooo#G#
###############################

迷路の中を、うねうねと蛇行しています。 DFS は「行けるところまで行く」ので、たまたま繋がった長い道をそのまま経路にします。

大事なのは「DFS が悪い」ではありません。

向いている用途
BFS最短が欲しい(重みが同じなら)。近い順に処理したい
DFSとにかく1つ解が欲しい。全部を列挙したい。メモリを節約したい

DFS が調べたマスは 264 で BFS の 359 より少ないのに、答えは3倍悪い。 「速く終わった=良い答え」ではありません。

DFS は再帰で書くとスタックが溢れます。 大きな迷路では明示的なスタックに書き換える必要があります。理由は call stack size exceeded の正体 — コンピュータ科学深掘り にあります。

全点間が要るとき — ワーシャル・フロイド法

ここまでは全部「1点から他の全部へ」でした。

「全部の駅から全部の駅への所要時間の表が欲しい」なら、話が変わります。

bash
$ nano floyd.mjs
import { EDGES, buildGraph } from "./graph.mjs";

const V = Object.keys(buildGraph());
const d = {};
for (const a of V) { d[a] = {}; for (const b of V) d[a][b] = a === b ? 0 : Infinity; }
for (const [a, b, w] of EDGES) { d[a][b] = Math.min(d[a][b], w); d[b][a] = Math.min(d[b][a], w); }

// 3重ループ。「k を経由したほうが近いか?」を全部の組で試すだけ
for (const k of V)
  for (const i of V)
    for (const j of V)
      if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

V.forEach((v, i) => console.log(`${i}: ${v}`));
console.log("     " + V.map((_, j) => String(j).padStart(4)).join(""));
V.forEach((i, n) => console.log(String(n).padStart(4) + " " + V.map((j) => String(d[i][j]).padStart(4)).join("")));
console.log("負の閉路の検出:", V.some((v) => d[v][v] < 0) ? "あり" : "なし");
bash
$ node floyd.mjs
0: 中央
1: 北口
2: 東町
3: 空港
4: 大学前
5: 港
6: 西谷
7: 山手
8: 南台
9: 桜坂
        0   1   2   3   4   5   6   7   8   9
   0    0   3   5  21   7  13  14  10  14   8
   1    3   0   7  19   5  11  16   7  11  10
   2    5   7   0  16   2   8   9  13   9   3
   3   21  19  16   0  14   8  12  17  13  19
   4    7   5   2  14   0   6  11  12  11   5
   5   13  11   8   8   6   0  17   9   5  11
   6   14  16   9  12  11  17   0  22  18  12
   7   10   7  13  17  12   9  22   0   4  10
   8   14  11   9  13  11   5  18   4   0   6
   9    8   10   3  19   5  11  12  10   6   0
負の閉路の検出: なし

0行目を見ると、②のダイクストラの結果と一致しています。(中央から空港が21分)

このアルゴリズムの中身は、3重ループの5行だけです。

これも「一度確定させて見直さない」をしていないので、負の重みが混ざっていても正しく動きます。 負の閉路の検出も1行です。d[v][v] < 0(自分から自分へ戻ると縮む)なら閉路があります。

計算量使いどころ
ダイクストラ × V回O(V(V+E) log V)辺が少ない大きなグラフ。負の重みは不可
ワーシャル・フロイドO(V³)V が数百まで。 書くのが5行。負の重みも可

O(V³) は、V=1000 で10億回です。 全点間が要るのは、たいてい頂点が少ないときです。


⑧ 最小全域木 — これは最短経路とは別の問題です

ここで問題が変わります。 最初に混ざりやすいところなので、はっきり書きます。

問題聞いていること
最短経路A から B へ行くのに一番安いのは?
最小全域木(MST)全部の頂点を繋ぐのに、辺の合計を最小にするには?

全然違います。

最小全域木の上を通っても、2点間の最短経路にはなりません。

実例で言えばこうです。

  • 最短経路: 中央から空港まで、一番早い行き方
  • 最小全域木: 全部の駅に光ファイバーを通したい。ケーブルの総延長を最小にするには、どの区間に敷くか

MST には、覚えておく性質が1つあります。

頂点が V 個なら、選ぶ辺は必ず V-1 本。 どんなやり方で解いても、この本数は変わりません。

クラスカル法 — 安い辺から採り、輪ができるなら捨てる

やることは1行で言えます。

辺を安い順に並べて、上から見ていく。輪ができないなら採用する。

「輪ができるか」の判定に道具が要ります。 それが Union-Find です。

Union-Find は「この2つは、もう繋がっているか?」だけを答える道具です。 既に繋がっている2点を繋ぐと、必ず輪ができます。 だから「繋がっているなら捨てる」でよい。

bash
$ nano mst.mjs
import { EDGES, buildGraph } from "./graph.mjs";
import { MinHeap } from "./heap.mjs";

// Union-Find: 「この2つは、もう繋がっているか?」だけを高速に答える道具
class UnionFind {
  constructor(items) {
    this.parent = {};
    for (const v of items) this.parent[v] = v;
  }
  find(x) {                                  // 代表を探す。途中を付け替えて次から速くする
    while (this.parent[x] !== x) x = this.parent[x] = this.parent[this.parent[x]];
    return x;
  }
  union(a, b) {                              // 繋いだら true、もう繋がっていたら false
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    this.parent[ra] = rb;
    return true;
  }
}

// クラスカル法: 辺を安い順に見て、輪ができないなら採用する
function kruskal(vertices, edges) {
  const uf = new UnionFind(vertices);
  const chosen = [];
  let total = 0;
  for (const [a, b, w] of [...edges].sort((x, y) => x[2] - y[2])) {
    if (uf.union(a, b)) {
      chosen.push([a, b, w]);
      total += w;
      console.log(`採用 ${w.toString().padStart(2)}: ${a} — ${b}`);
    } else {
      console.log(`  却下 ${w.toString().padStart(2)}: ${a} — ${b}(もう繋がっている)`);
    }
  }
  return { chosen, total };
}

// プリム法: 1点から始めて、いま繋がっている塊に一番近い頂点を足していく
function prim(g, start) {
  const inTree = new Set([start]);
  const chosen = [];
  let total = 0;
  const h = new MinHeap();
  for (const { to, w } of g[start]) h.push(w, [start, to, w]);
  while (h.size && inTree.size < Object.keys(g).length) {
    const [, [a, b, w]] = h.pop();
    if (inTree.has(b)) continue;             // もう入っている = 輪になる
    inTree.add(b);
    chosen.push([a, b, w]);
    total += w;
    for (const e of g[b]) if (!inTree.has(e.to)) h.push(e.w, [b, e.to, e.w]);
  }
  return { chosen, total };
}

const vertices = Object.keys(buildGraph());
console.log("=== クラスカル法 ===");
const k = kruskal(vertices, EDGES);
console.log(`辺 ${k.chosen.length} 本 / 総コスト ${k.total}`);

console.log("=== プリム法(中央から育てる)===");
const p = prim(buildGraph(), "中央");
for (const [a, b, w] of p.chosen) console.log(`採用 ${w.toString().padStart(2)}: ${a} — ${b}`);
console.log(`辺 ${p.chosen.length} 本 / 総コスト ${p.total}`);

console.log("=== 比べる ===");
console.log(`頂点の数 ${vertices.length} / 辺は必ず ${vertices.length - 1} 本`);
console.log(`総コストは ${k.total === p.total ? "一致" : "不一致"}`);
const setK = new Set(k.chosen.map(([a, b]) => [a, b].sort().join("-")));
const setP = new Set(p.chosen.map(([a, b]) => [a, b].sort().join("-")));
const same = setK.size === setP.size && [...setK].every((e) => setP.has(e));
console.log(`選んだ辺そのものは ${same ? "同じ" : "違う"}`);
bash
$ node mst.mjs
=== クラスカル法 ===
採用  2: 東町 — 大学前
採用  3: 中央 — 北口
採用  3: 東町 — 桜坂
採用  4: 山手 — 南台
採用  5: 中央 — 東町
  却下  5: 北口 — 大学前(もう繋がっている)
採用  5: 南台 — 港
採用  6: 大学前 — 港
  却下  6: 桜坂 — 南台(もう繋がっている)
  却下  7: 北口 — 山手(もう繋がっている)
採用  8: 港 — 空港
採用  9: 東町 — 西谷
  却下 12: 西谷 — 空港(もう繋がっている)
  却下 40: 中央 — 空港(もう繋がっている)
辺 9 本 / 総コスト 45
=== プリム法(中央から育てる)===
採用  3: 中央 — 北口
採用  5: 中央 — 東町
採用  2: 東町 — 大学前
採用  3: 東町 — 桜坂
採用  6: 桜坂 — 南台
採用  4: 南台 — 山手
採用  5: 南台 — 港
採用  8: 港 — 空港
採用  9: 東町 — 西谷
辺 9 本 / 総コスト 45
=== 比べる ===
頂点の数 10 / 辺は必ず 9 本
総コストは 一致
選んだ辺そのものは 違う

スクリーンショットを撮ってください: 03_mst_kruskal_prim.png 「総コストは 一致 / 選んだ辺そのものは 違う」の2行が入るように撮ってください。

この出力の読みどころは4つです。

1つ目。クラスカル法は、辺を安い順に見ているだけです。 採用の順が 2, 3, 3, 4, 5, 5, 6, 8, 9 と、必ず増えていきます。 これは「安い順に見ている」のだから当たり前です。

2つ目。プリム法は、安い順になっていません。 3, 5, 2, 3, 6, 4, 5, 8, 9。 「いま育っている木に一番近い頂点」を選ぶので、木の形に引きずられます。

3つ目。総コストはどちらも 45。一致しました。

4つ目。選んだ辺は違います。

理由は重み6の辺が2本あるからです。

  • クラスカル法は 大学前 — 港 (6) を採用し、桜坂 — 南台 (6) を却下した
  • プリム法は 桜坂 — 南台 (6) を採用した

重みが同じ辺が複数あると、最小全域木は1つに決まりません。 総コストだけが必ず一致します。 「実装を変えたら答えが変わった」と焦る前に、総コストを比べます。

5つ目。中央 — 空港 (40) が最後に却下されています。 ①で私を騙した直通路線です。 最短経路では「40分の直通より21分の乗り換え」でした。MST でも「40のケーブルは要らない」。理由は全然違いますが、どちらも捨てられました。

どちらを使うか

やり方計算量向いている形
クラスカル法辺を安い順に見るO(E log E)辺が少ない(疎な)グラフ。実装が短い
プリム法1点から育てるO(E log V)辺が多い(密な)グラフ。ダイクストラとほぼ同じ形

プリム法とダイクストラの違いは、優先度に入れる値だけです。

ダイクストラ: 優先度 = 始点からの合計距離  (dist[u] + w)
プリム法:     優先度 = その辺1本の重み      (w)

「始点から」を「1本の辺」に変えただけで、別の問題を解く道具になりました。 ここは覚える価値があります。

実例

場面何が最小全域木か
ネットワーク配線全拠点を繋ぐケーブルの総延長を最小に
電力網・水道網全戸に届く配管の総コストを最小に
クラスタリングMST を作って、高い辺から k-1 本切ると k 個のグループになる(単連結法)
画像の領域分割隣り合う画素を辺にして MST。似ている画素だけが繋がる

クラスタリングの使い方は美しいので覚えておく価値があります。 「全部繋いでから、高いところで切る」。 グループ数を後から決められます。

触れるだけ — 最大流(フォード・ファルカーソン法)

この記事では実装しません。 「何を解く問題か」だけ知っておくと、必要になったとき探せます。

パイプの太さ(容量)が決まっているとき、始点から終点へ最大どれだけ流せるか。

最短経路とは、辺に付いた数の意味が違います。

辺の数が意味するもの求めるもの
最短経路通るのにかかるコスト合計コストの最小
最小全域木敷くのにかかるコスト全部繋ぐ合計の最小
最大流一度に流せる量の上限(容量)流せる量の最大

解き方の骨だけ書いておきます。

まだ余裕のある経路を探して、流せるだけ流す。それを、経路が見つからなくなるまで繰り返す。

面白いのは、この問題が「一見関係ない問題」に化けることです。

  • マッチング問題: 「応募者と求人を、最大何組つけられるか」

→ 左に応募者、右に求人を並べ、容量1の辺を張る。最大流がそのまま最大の組数

  • シフト表: 「誰をどの枠に入れれば、埋まる枠が最大になるか」
  • 最小カット: 最大流の値は「ネットワークを2つに切り離す最小コスト」と必ず一致する(最大流最小カット定理)

「割り当ての最大化」に見えたら、最大流を疑う。 ここまで覚えておけば十分です。


判断表 — どれを使うかを、条件で決める

この記事で一番持ち帰ってほしいのは、この表です。名前を覚える必要はありません。

条件使うもの計算量ひとこと
重みが無い(全部同じ)・1点からBFSO(V+E)重みが違うなら使わない。別の問題の答えが出る
とにかく1つ解が欲しい / 全部列挙したいDFSO(V+E)最短にはならない
重みが全部0以上・1点からダイクストラ(ヒープ)O((V+E) log V)9割はこれ
負の重みがあるベルマン・フォードO(V×E)遅い。負の重みが無いなら選ばない
負の閉路があるか知りたいベルマン・フォードO(V×E)「最短が存在しない」を検出できる唯一の道具
全点間が要る・頂点が数百までワーシャル・フロイドO(V³)5行で書ける。負の重みも可
全点間・辺が少ない・重みが0以上ダイクストラを V 回O(V(V+E) log V)疎なグラフならこちらが速い
ゴールが1つ・座標などの見積りが作れるA\*ダイクストラ以下h は絶対に本当の距離を超えないこと
全部を最小コストで繋ぎたい・辺が少ないクラスカル法(Union-Find)O(E log E)最短経路ではない
全部を最小コストで繋ぎたい・辺が多いプリム法O(E log V)ダイクストラの優先度を「辺の重み」に変えただけ
容量の上限つきで最大どれだけ流せるか最大流実装による割り当て問題に化ける

判断の順番は、上から3つの質問だけです。

Q1. 辺に重みはある?
    無い → BFS で終わり
Q2. 負の重みはある?
    ある → ベルマン・フォード(閉路の検出もできる)
    無い → ダイクストラ
Q3. ゴールが1つで、方向の見積りが作れる?
    作れる → A*(h は本当の距離を超えないこと)

つまずいたところ

乗り換え案内を BFS で作って、40分の直通を「最短」として出した。 これが導入で書いた失敗です。BFS はバグっていませんでした。私が「区間の本数の最小」を「時間の最小」だと思い込んでいただけです。アルゴリズムを選ぶ前に、「何を最小にしたいのか」を日本語で1行書くようになりました。

負の重みでダイクストラが間違ったとき、実装を疑って半日溶かした。 例外も警告も出ないので、コードのバグだと思い込みました。 総当たりの実装と突き合わせて初めて「実装は合っている。前提が違う」と分かりました。速い実装を書いたら、必ず遅い正解と突き合わせる。前の回と同じ結論です。

「全部の重みに一律で足せば負が消える」を本気で実装しかけた。 辺の本数が違う経路には足される量が違うので、答えがひっくり返ります。 4地点の例で手で計算して、書く前に気づきました。思いついた回避策は、まず一番小さい例で手計算する。

ヒープ版に書き換えたのに、頂点1000では1.4倍しか速くならなかった。 「実装が悪いのか」と直し始めそうになりました。V=20000 まで増やしたら18倍でした。 計算量の差は、データが小さいうちは出ません。 測る規模を間違えていました。

ヒープ版で done の判定を入れ忘れて、同じ頂点を何度も処理した。 答えは合うのに、遅い。距離が縮むたびにヒープへ入れ直しているので、古い情報が残っています。 if (done[u]) continue; の1行が要ります。

A* のヒントに、単位の違う値を足した。 マスの数(コスト)に対して、ピクセル単位の距離を h にしていました。数十倍の大きすぎるヒントになり、経路が最短でなくなりました。それでも動くので気づきません。h = 0 にして答えが変われば、犯人はヒント、という切り分けを覚えました。

A* の h を「これくらい大きいほうが速い」と調整して、最短でなくなった。実は用途によっては、これは正しい判断です。ゲームの敵の移動なら「だいたい最短」で十分で、速いほうが価値があります。問題は、間違うと知らずにやっていたことです。

MST で「クラスカルとプリムで違う辺が選ばれた」と焦った。 重みが同じ辺が複数あると、最小全域木は1つに決まりません。 総コストだけが必ず一致します。答えを比べるときは、何が一意で何がそうでないかを先に確かめる。

Union-Find の find で経路圧縮を書かず、木が一直線になった。 駅10個では気づきません。x = this.parent[x] = this.parent[this.parent[x]] の1行があるかどうかで、大きいグラフでの速度が変わります。 木が一直線になると、前の回で見たのと同じで、O(log n) のつもりが O(n) になります。

bellman.mjs を cycle.mjs から読み込んだら、bellman.mjs の実験も一緒に走った。 ES モジュールは、読み込まれた瞬間にトップレベルのコードが走ります。 出力に余計な行が混ざって混乱しました。ライブラリと実験は別ファイルに分けるべきでした。


後片づけ

実験用フォルダを消します。

bash
$ cd ~
$ rm -rf ~/cslab/path
$ ls ~/cslab

path が消えていれば完了です。

~/cslab そのものは消していません。 前の回のフォルダが残っていれば、そちらもまとめて片づけてください。


まとめ — 理解できたこと

  • BFS が最短を返すのは「重みが全部同じとき」だけ。 重みが違うと別の問題の答えが返る。実測で 1本40分 vs 4本21分
  • BFS は「重みが全部1のダイクストラ」。 特別な場合であって、別物ではない
  • ダイクストラがしているのは1つだけ。 「未確定の中で一番近いものを確定させ、隣を緩和する」
  • 確定した距離は必ず増えていく。 0 → 3 → 5 → 7 → 8 → 10 → 13 → 14 → 14 → 21。この単調性が正しさの根拠
  • 経路は prev を1行足すだけで出る。 dist だけ作って後悔しない
  • 一番大事: ダイクストラは負の重みで壊れる。 例外も警告も出さず、それらしい数字を返す。実測で 本当は0なのに2
  • 壊れる理由は「一度確定させたものを二度と見直さないから」。 遠回りが安くなる世界では、「いま一番近い」が「最終的に一番近い」ではない
  • 「全部の重みに一律で足す」は間違い。 辺の本数が違う経路には足される量が違い、答えがひっくり返る
  • ベルマン・フォードは「全部の辺を V-1 回ゆるめる」だけ。 確定という考えが無いので壊れない。代わりに O(V×E) で遅い
  • 「V 回目でまだ縮むなら負の閉路」。 最短経路が存在しないことを検出できる唯一の道具
  • 為替の裁定取引の検出は、-log(レート) を重みにした負の閉路の検出そのもの。 掛け算を足し算に変形して既存の道具に載せた
  • ヒープ版に変えると、V=20000 で 18倍。 V=1000 では1.4倍しか違わない。差が出る規模で測る
  • A* はダイクストラに h を足しただけ。 h = 0 ならダイクストラそのもの。実測で 調べたマス 359 → 140
  • h が本当の距離を超えると、A* は速くなる代わりに間違える。 実測で 3倍のヒントにしたら 46 → 48
  • A* を疑うときは h を 0 にする。 答えが変われば犯人はヒント
  • DFS は解を見つけるが最短ではない。 実測で BFS 46 に対して DFS 142。調べたマスは DFS のほうが少ない。「早く終わった」は「良い答え」ではない
  • 全点間で頂点が数百までなら、ワーシャル・フロイドの3重ループ5行。 負の重みも扱える
  • 最小全域木は最短経路とは別の問題。 「全部を最小コストで繋ぐ」であって「最短で行く」ではない
  • 頂点が V 個なら、全域木の辺は必ず V-1 本
  • クラスカルは辺を安い順に見て、Union-Find で輪を弾く。プリムは1点から育てる。 総コストは必ず一致するが、選ぶ辺は違うことがある
  • プリムとダイクストラの差は、優先度に入れるのが「始点からの合計」か「辺1本の重み」かだけ
  • 最大流は「容量の上限つきで最大どれだけ流せるか」。 割り当て・マッチング問題に化ける
  • 結論: アルゴリズム名を暗記しない。 「重みはあるか」「負はあるか」「ゴールの方向は分かるか」の3問で決める

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 14 / 25 本目です。

記事
← 前の記事グラフとBFS・DFS — 循環参照で探索が止まらない
→ 次の記事再帰とメモ化 — メモを1行足したら一瞬で終わった

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Shortest Path & MST
  • ダイクストラは負の重みで壊れる
  • A* / クラスカル / プリム

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次