最も近いものから確定する — Dijkstra 法は負の辺が無いことを使う

Dijkstra の1959年の論文(Numerische Mathematik 1, 269–271)は、最短経路の問題(Problem 2)をこう書き出します。

Problem 2. Find the path of minimum total length between two given nodes P and Q. We use the fact that, if R is a node on the minimal path from P to Q, knowledge of the latter implies the knowledge of the minimal path from P to R. In the solution presented, the minimal paths from P to the other nodes are constructed in order of increasing length until Q is reached.

in order of increasing length(近い順)です。集合 A の定義も同じです。

A. the nodes for which the path of minimum length from P is known; nodes will be added to this set in order of increasing minimum path length from node P;

論文の全文に heap・priority・queue の語は1つもありません。書かれているのは集合の出し入れだけで、「いちばん近いもの」をどう探すかは決めていません。

手で確かめます。頂点6・有向辺9、重みが全部正のグラフ(A→B 7, A→C 9, A→F 14, B→C 10, B→D 15, C→D 11, C→F 2, D→E 6, F→E 9)で、A から始まる単純経路15本を全部たどった最小値と、heapq で書いた Dijkstra 法の結果を比べました(Python 3.14.6 / macOS arm64、2026-10-07 実行)。

graph1 V=6 E=9  simple paths enumerated: 15
bruteforce: {'A': 0, 'B': 7, 'C': 9, 'D': 20, 'E': 20, 'F': 11}
dijkstra(strict=True): {'A': 0, 'B': 7, 'C': 9, 'D': 20, 'E': 20, 'F': 11}  settle order=['A', 'B', 'C', 'F', 'D', 'E'] heappops=8 agree=True

一致しました。確定順は A, B, C, F, D, E で、距離は 0, 7, 9, 11, 20, 20 と小さい順に並んでいます。取り出し8回のうち2回は、積み直したあとに残った古い項目で、読み飛ばしています。heapq 公式の「Priority Queue Implementation Notes」も、ヒープの中で値を直さない方法の1つとしてこう挙げています(公式は削除の印、本文は確定済みの集合で読み飛ばす)。

Removing the entry or changing its priority is more difficult because it would break the heap structure invariants. So, a possible solution is to mark the entry as removed and add a new entry with the revised priority:

① 幅優先探索 — 重みが全部1の Dijkstra 法

第11期の『取り出す順序が、解ける問題を決める』は、幅優先が最短を返すのは辺の重みが等しい場合の性質で、あの1例は証明ではない、と断って止めていました。重みが全部1なら、暫定値は「何本の辺でたどり着いたか」です。いちばん近いものから確定すると、距離0、距離1、距離2……と層の順に確定します。先に入れたものから取り出すキューは、この順を比較なしで作ります。

上のグラフ1の重みを全部1にして、両方を走らせました(同じ環境、本教材で実行)。

BFS     order ['A', 'B', 'C', 'F', 'D', 'E'] dist [0, 1, 1, 1, 2, 2]
Dijkstra order ['A', 'B', 'C', 'F', 'D', 'E'] dist [0, 1, 1, 1, 2, 2]
same dist: True

距離は一致し、確定は層の順(0 → 1 → 2)に進みました。同じ層の中の順番は、同点をどう扱うか次第です。

② OSPF の SPF 計算 — 前提が仕様に書いてある

RFC 2328(OSPF Version 2)は、ルータが持つ最短経路の木をこう定義します(§6)。

Shortest-path tree The shortest-path tree for the area, with this router itself as root. Derived from the collected router-LSAs and network-LSAs by the Dijkstra algorithm (see Section 16.1).

§16.1 は、確定してよい理由まで書いています。

However, the paths to the candidate vertex that is closest to the root are guaranteed to be shortest; this vertex is added to the shortest-path tree, removed from the candidate list, and its adjacent vertices are examined for possible addition to/modification of the candidate list.

そして §9 のインタフェースのコストの定義に、前提そのものがあります。

The cost of an interface must be greater than zero.

コストを正に限ることで、前提をプロトコルが守っています。