YOI 768：最短の道が何本もあるとき、一本を選んでいるのは最適化ではなく、ずれの入れ方である

論文768 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/768 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23015253）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi768,
  author = {Yamagishi, Yuuki},
  title = {When There Are Many Shortest Paths, What Picks One Is Not the Optimisation but How the Tie Is Broken},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/768},
  doi = {10.5281/zenodo.23015253},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

最短経路の計算は、一本の答を返す。けれど最短の道がいくつもあるとき、その一本を選んだのは計算ではない。同点の数と、同点を崩すずれが選ぶ道の種類を数える。新しい定理も法則も主張しない。

第一に、格子では最短の道が数えきれないほどある。$10\times10$ で長さ $20$ の道が $184756$ 本、どれも同じ長さ（第2節）。

第二に、小さなずれを足すと、最短は一本に決まる。重さに $10^{-9}$ の乱数を足すと、$1000$ 回とも最短は $1$ 本（第2節）。

第三に、これが本稿の芯である。決まった一本は、ずれの入れ方で毎回変わる。$1000$ 通りの足し方で選ばれた経路は $998$ 種類（第2節）。

第四に、規則の違いは、道を丸ごと変える。「右を先に」と「上を先に」の経路が共有する辺は $0$ 本（第3節）。

第五に、同点は整数の重さで起き、実数の重さでは起きない。$\{1,2\}$ の重さで最短が複数ある割合 $\mathbf{0.973000}$、$[1,2]$ の実数で $\mathbf{0.000000}$（第3節）。

第六に、分離子は、重さが整数のように同点を許すか、実数のように同点が起きないかである。「最適解を求めた」は、同点があるかを言うまで、その一本に意味があるかが決まらない（第4節）。

キーワード：最短経路、経路の非一意性、同点の崩し方、二項係数、摂動、格子の経路

Abstract

A shortest-path computation returns one answer. But when many paths are equally short, that one was not picked by the computation.The number of ties, and the variety of paths picked by perturbations that break them, are counted.No new theorem or law is claimed.

First, a grid has a vast number of shortest paths、$184756$ paths of length $20$ on $10\times10$, all equally long (Section 2).

Second, a small perturbation makes the shortest path unique、adding random amounts of $10^{-9}$ gave exactly $1$ shortest path all $1000$ times (Section 2).

Third, and this is the core. The unique path changes with how the perturbation is added、$1000$ ways of adding it selected $998$ different paths (Section 2).

Fourth, a different rule changes the path entirely、“right first” and “up first” share $0$ edges (Section 3).

Fifth, ties arise with integer weights, not with real ones、several shortest paths in a share $\mathbf{0.973000}$ of instances with weights in $\{1,2\}$, and $\mathbf{0.000000}$ with real weights in $[1,2]$ (Section 3).

Sixth, the separator is whether the weights allow ties, as integers do, or rule them out, as real numbers do、“the optimum was found” does not say whether that one path means anything until one says whether ties exist (Section 4).

Keywords: shortest path, non-uniqueness of paths, tie-breaking, binomial coefficient, perturbation, grid paths

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/768/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/768 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ