荷物・渋滞・時間をひとつの重みに束ねて最適ルートを求める — 配達・物量のイメージで学ぶ重み付き最短経路（Antigravity SSSP 拡張）

使い方（最初の一通り）

1. ZIP を展開し、中の拡張パッケージをエディタの「VSIX からのインストール」で入れる。
2. 左の Antigravity SSSP を開き、「比較パネルを開く」で大きい画面を出す。
3. 頂点数を選び、「比較する」を押す（大きいほど待ち時間が伸びます）。
4. 棒グラフ・表・地図で、合成重み（ルートの総コスト）とミリ秒（計算の速さ）を眺める。
5. 頂点数が 5,000 を超える（5,001 以上）ときは、地図でドラッグしてゾーンを置き、「ゾーンを反映して再計測」で変化を試す。

起動と画面の位置

左端の Activity Bar に Antigravity SSSP があります。そこを開くと説明付きのサイドバーが出ます。上の 「比較パネルを開く」 を押すと、地図とグラフが並ぶ大きな作業画面が開きます（一覧の歯車アイコンからも同じパネルを開けます）。

地図のイメージ（裏で何が起きているか）

画面の格子は、細い近道のつながりに加えて、横や縦に少し飛ぶ「幹線」のようなつながりも持つ人工の道路網です。同じ「頂点数」を選べば、同じ迷路の形になります（試し直しやすいよう、ランダムは毎回ぶれないように決め打ちされています）。

各リンクには、距離・所要時間・渋滞・運転のしづらさ・天気・積載の余裕などがランダムで付き、それらを係数付きで足し合わせて、一本の整数のコストにまとめています。渋滞や悪天候の項が効きやすいので、「遠くても楽な道」と「近くてもしんどい道」が分かれやすい設定です。

「比較する」を押すと

選んだ頂点数の地図を用意したあと、5 通りの計算方法それぞれを何度か走らせ、平均の計算時間（ミリ秒）を棒グラフにします。ゾーンを変えて「ゾーンを反映して再計測」すると、コストやステップ、速さがどう変わったかが差分パネルにまとまり、下には再計測の履歴が溜まります。頂点数の上限はおおよそ 300 万までです（大きいほど重くなります）。

ゾーン（赤＝避けたい・緑＝通りたい）

地図上でドラッグすると矩形のゾーンが置けます。赤（避ける）は該当辺の重みに +500、緑（通りたい）は −220 が加わる設定です（いずれも通行禁止ではなく偏好）。まわり道の方がトータルで安ければ、避けゾーンを横切るルートも選ばれます。ゾーンのドラッグは頂点数が 5,000 を超えるときだけ有効です（5,001 頂点以上。それ以下ではゾーン行が出ず操作できません）。種類は画面上の切り替えから選び、「ゾーンを反映して再計測」で地図を作り直してから、もう一度比較します。

5 つの計算の名前と違い（用語）

画面上の名前	ユーザー目線でのイメージ
Dijkstra（ヒープ）	非負のコストなら正しい答えが出る、いちばん定番のやり方。地図上の青い経路の基準にもなります。
A*（ヒューリスティック）	ゴールの方角を見積もって探索を絞るやり方。条件が合えば答えは定番と同じになります。
双方向 Dijkstra	出発とゴールの両方から同時に広げて、途中でつなげるイメージ。一本のルートを求める向きです。
Bucket (Dial)	コストが整数にまとまっているとき向け。桶に地点を分けて進める古典的手法で、棒グラフでは速く出やすいことがあります。
実験・4 分岐ヒープ Dijkstra	中身は定番に近いが、並べ替えの内部の形を変えた比較用。速さは PC や地図の大きさで変わります。

画面の用語（図4を読むとき）

表示	意味
ms（棒・メトリクス）	各手法を 3 回計測した計算時間の平均（ブラウザ内の処理時間。移動時間ではない）。
コスト／合成重み	終点までの経路上の辺の重み w の合計（ゾーン適用後）。
ステップ数	経路上の辺の本数。
出発・到着	常に地点 0からいちばん大きい番号の地点（n−1）へ。
整合性パネル	各手法の到達可否・コスト・ステップ・Dijkstra との差。
要因の表	各手法が自分の経路について距離・時間・渋滞などを積み上げたもの（経路が違えば行ごとに数値も変わる）。
合成重みの内訳バー	Dijkstra の経路を前提にした比率。各辺は floor 済みの w なので、バーの近似と総コストがすこしズレることがある（パネル下の注記どおり）。
再計測パネル・差分表	ゾーン反映の前後で、コスト・ms・ステップがどう変わったか。
再計測履歴	ゾーン操作ごとのスナップショット一覧。
概略地図とゾーン	5,000 を超えると概略キャンバス＋ゾーン。それ以下は網の目に近い全頂点描画が中心。

整合性パネルで手法ごとのコストが食い違う場合、拡張側の説明では整数化・双方向の打ち切り・A* のヒューリスティックなどが原因として挙げられています。同じコストでも経路の形が違うことはあり、そのとき要因の表は手法ごとに読み分けてください。

新しい研究との関係（ざっくり）

長いあいだ、「最短経路を速く求めるには並べ替えのような処理が要る」と考えられてきました。一方で、コストがきちんと整数にまとまる世界では、桶（バケット）に地点を分ける古典的なやり方が、定番と対照的な速さの出方を見せます。この拡張の Bucket (Dial) は、その系統を体感で比べるための一枚です。

2025 年に arXiv で紹介された Breaking the Sorting Barrier for Directed Single-Source Shortest Paths は、もっと難しい設定で「並べ替えの壁」を緩める理論の一例です。この拡張がその論文そのものを再現しているわけではありません。あくまで、ニュースで聞く「最短経路の新しい話」と、手元の棒グラフをざっくり結びつけるための入口だと捉えてください。

現実の配達・物量とどうつなぐか

地点は交差点やエリアのイメージ、線は移動のつながり、一本化されたコストは「今日はこれを優先して通りたい」度合いのようなものです。ゾーンは本番のジオフェンスのように硬い禁止ではなく、コストをまとめて上げ下げするやわらかい偏好として読むと分かりやすいです。実務の時間窓付き配車や在庫まで扱うわけではありませんが、ルートを数値で語る練習として触れる価値があります。