ダイクストラは負の重みで壊れます。最短経路のアルゴリズムを実装して、使える条件を確かめます。
前回: グラフと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* は速くなる代わりに間違える
- 最小全域木は最短経路とは別の問題。 「全部を最小コストで繋ぐ」であって「最短で行く」ではない
- クラスカル法とプリム法は、同じ総コストを、違う辺の組み合わせで出すことがある
この記事でやること
- 実験用フォルダ
~/cslab/pathを作り、この記事の作業を全部そこに閉じ込める - 10駅の路線図を作り、BFS とダイクストラの答えを並べて出す
- ダイクストラを書いて、確定の様子を1行ずつ表示する。 経路も駅名で復元する
- 頂点1000〜20000で、素朴な実装とヒープ版を実測して比べる
- 負の重みを1本だけ入れて、ダイクストラが静かに間違えるところを出力する
- ベルマン・フォードで正しい答えを出し、負の閉路の検出と裁定取引の検出まで作る
- 格子迷路を作り、ダイクストラ / A* / BFS / DFS の「調べたマスの数」を数えて比べる
- 最小全域木を、クラスカル法(Union-Find つき)とプリム法の両方で解く
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 重み(コスト) | 辺に付いた数。所要時間・運賃・遅延など。「1本」ではなく「何分」 |
| 緩和(relax) | 「そこを経由したほうが近いなら、記録を書き換える」こと。最短経路の全アルゴリズムがこれしかしていない |
| 確定(settle) | その頂点までの最短がもう変わらないと決めること。ここが負の重みで崩れる |
prev 配列 | 「その頂点に、どこから来たか」の記録。逆にたどると経路が出る |
| 負の閉路 | 一周すると合計が減る輪。回るほど小さくなるので、最短経路が存在しない |
| ヒューリスティック | ゴールまでの見積り。A\* が使う「ヒント」 |
| 許容的(admissible) | ヒントが本当の距離を絶対に超えないこと。これが崩れると A* の答えが狂う |
| マンハッタン距離 | 縦の差 + 横の差。斜めに進めない格子での最短距離 |
| 全域木 | 全部の頂点を繋ぐ、輪の無い辺の集まり。頂点が V 個なら辺は必ず V-1 本 |
| Union-Find | 「この2つは、もう繋がっているか?」だけを高速に答える道具 |
① 題材を作る — 同じグラフで BFS とダイクストラを比べる
実験用のフォルダを作ります。最後に消します。
v22.14.0
node が無ければ、「1」と 1 は等しい — JavaScriptの基本 を先に見てください。
10駅の路線図を作ります。 区間ごとに所要時間(分)が違います。
// 路線図: 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 とダイクストラを、同じグラフで走らせます。
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)} 分`);
}
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以上なら」。ここに全部が乗っています。 ④で崩します。
動きが見えるように、確定するたびに表示します。
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(" → ")}`);
}
確定: 中央 (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万件ソート — コンピュータ科学深掘り で作った最小ヒープが、そのまま使えます。
// 最小ヒープ。[優先度, 中身] を入れて、いつでも一番小さいものが取り出せる
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つだけ気をつける点があります。
「距離が縮んだら、ヒープに入れ直す」。古いほうは消さない。取り出したとき無視する。
ヒープの途中の要素を書き換えるのは面倒です。 だから入れっぱなしにして、確定済みなら捨てるという手抜きをします。これが標準的なやり方です。
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 ? "一致" : "不一致"}`);
}
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,000 | 4.1ms | 2.9ms | 1倍 | 1倍 |
| 5,000 | 98.2ms | 12.5ms | 24倍 | 4.3倍 |
| 20,000 | 2486.1ms | 137.6ms | 606倍 | 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地点のグラフで見ます。
// 一方通行の配送ルート。単位は万円。倉庫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 です。 では、ダイクストラは何と言うか。
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(" → ")}`);
確定: 拠点 (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 でも見直さない
順番を追います。
拠点を確定(0)。隣を更新して倉庫A = 1、倉庫B = 2- 未確定の中で一番近いのは
倉庫A(1)。 だから倉庫Aを確定させる 倉庫Aから納品先 = 2倉庫B(2)を確定。ここで倉庫B → 倉庫Aが-3なので2 - 3 = -1- でも
倉庫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本ずつ正しく確定していく
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 ?? "なし");
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倍以上の差です。
負の重みが無いなら、絶対にベルマン・フォードを選ばない。
負の閉路 — 「最短経路が存在しない」を検出する
負の重みには、もう一段面倒な話があります。
回るたびに合計が減る輪があると、最短経路は「存在しません」。
無限に回れば、いくらでも小さくできるからです。 下限がありません。
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 は読み込まれた時点で自分の実験も走ります。 出力の後半だけを見てください。
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(レート) にすれば、「儲かる輪」が「負の閉路」になります。 掛け算が足し算に変わりました。
// 為替レート: 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を超えたら儲かる輪)");
}
負の閉路を検出: 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\ の特別な場合です。
格子迷路で確かめます。
// 迷路を作る。乱数の種を固定するので、何度走らせても同じ迷路が出る
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;
}
乱数の種を固定しています。 毎回違う迷路だと、アルゴリズムの差なのか迷路の差なのか分からなくなるからです。
迷路を見ておきます。
import { makeMaze, show } from "./maze.mjs";
console.log(show(makeMaze()));
###############################
#S....#.......................#
#####.#..#.##..###.###.######.#
#...#...#...#...............#.#
#.#.###.#.#.##.####.#.#.#.###.#
#.#.......#.........#.#.......#
#.#.###...#..#.##.###.#...#####
#.....#.#...........#.........#
#.###.#.#.####......#.###.#####
#.#.....#.....#.......#.......#
#.#...#.###.#..#...###..#...#.#
#.#.#.#.#.....#.#...........#.#
#.#.#...#.##..#.##.##.#####.#.#
#.....#.#...#.#.#...........#.#
#.#.###.#...#.#.#..####.##.##.#
#.......#.......#.....#.#.....#
#.##.####.###.###.#.#.#.#..##.#
#.#...#...#.......#.#.#.#.....#
#.#.#.#####.###.#...#.#.###.#.#
#...................#.......#G#
###############################
左上が S、右下が G。 壁を60箇所壊してあるので、行き方が何通りもあります。
探索の本体を書きます。ダイクストラも A* も同じ関数です。ヒント h を差し替えるだけです。
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種類のヒントで走らせます。
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));
ダイクストラ(h=0) 経路の長さ 46 調べたマス 359
A* (マンハッタン) 経路の長さ 46 調べたマス 140
A* (ヒント3倍) 経路の長さ 48 調べたマス 55
3行の中に、この節の全部が入っています。
| ヒント | 経路の長さ | 調べたマス | 判定 |
|---|---|---|---|
h = 0(ダイクストラ) | 46(最短) | 359 | 正しい。ただし全方向を調べた |
h = マンハッタン距離 | 46(最短) | 140 | 正しくて、しかも 2.6分の1しか調べていない |
h = マンハッタン距離 × 3 | 48(最短ではない) | 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 も走らせます。
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)。 それだけで挙動が変わります。
やり方 経路の長さ 調べたマス
BFS 46 359
DFS 142 264
A* 経路の長さ 46 調べたマス 140
| やり方 | 経路の長さ | 調べたマス | 最短か |
|---|---|---|---|
| BFS | 46 | 359 | ⭕ 重みが全部1なので最短 |
| DFS | 142 | 264 | ❌ 3倍の遠回り。でも解は見つけた |
| A\* | 46 | 140 | ⭕ 最短で、一番少ない手間 |
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点から他の全部へ」でした。
「全部の駅から全部の駅への所要時間の表が欲しい」なら、話が変わります。
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) ? "あり" : "なし");
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点を繋ぐと、必ず輪ができます。 だから「繋がっているなら捨てる」でよい。
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 ? "同じ" : "違う"}`);
=== クラスカル法 ===
採用 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点から | BFS | O(V+E) | 重みが違うなら使わない。別の問題の答えが出る |
| とにかく1つ解が欲しい / 全部列挙したい | DFS | O(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 モジュールは、読み込まれた瞬間にトップレベルのコードが走ります。 出力に余計な行が混ざって混乱しました。ライブラリと実験は別ファイルに分けるべきでした。
後片づけ
実験用フォルダを消します。
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問で決める
参考リンク
- roadmap.sh — Computer Science
- MDN — JavaScript のガイド
- MDN — Math.log
- MDN — Set
- MDN — performance.now
- Node.js — Performance measurement APIs
- Node.js — ECMAScript modules
- Red Blob Games — Introduction to A\*
- Red Blob Games — Heuristics for grid maps
- OSRM — オープンソースの経路探索エンジン
次に読む
この記事は 【深掘り】コンピュータ科学 の 14 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | グラフとBFS・DFS — 循環参照で探索が止まらない |
| → 次の記事 | 再帰とメモ化 — メモを1行足したら一瞬で終わった |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- ダイクストラは負の重みで壊れる
- A* / クラスカル / プリム
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント