Shortest path パネルが解くもの
Shortest path パネルは同じ重み付きグラフ上で 4 つのアルゴリズムを実行します。Dijkstra、A*、Bellman–Ford、Floyd–Warshall です。各結果行は手法を明示し、距離と経路を出力します。また、追跡を行う 2 つの単一始点探索では、頂点が確定した順序も示します。グラフは共有のグラフ理論ワークベンチで構築し、Directed トグル、辺の重み、隣接行列の貼り付けボックスがすべて適用されます。
各アルゴリズムの実行方法
- 01グラフを読み込んで端点を設定します。プリセットを構築するか隣接行列を貼り付け、Source と Target を選びます。プリセットの構築では最初と最後のノードにリセットされます。
- 02Dijkstraは距離、経路、確定順を答え、負の辺を含むグラフを拒否します — エラーはその辺を名指しして Bellman–Ford を指します。
- 03A\はヒューリスティック選択(manhattan / euclidean / zero)を追加し、Dijkstra と比べた展開ノード数、実際に使われたヒューリスティックのスケール、ヒューリスティックが整合的でゆえに最適かを報告します。
- 04Bellman–Fordは緩和ラウンドを報告し、ノードごとの最終距離を列挙し、負の閉路があれば印を付けます。
- 05Floyd–Warshallは 1 つの始点から距離行列を埋め、負閉路ノードをマークし、同じ表で任意の始点/終点ペアに答えられます。
計算例
パネルから読み取った値:
| 設定 |
計算結果 |
| 6 ノードの既定グラフ、Dijkstra A → F |
距離 13、経路 A → C → B → D → E → F、確定順 A → C → B → D → E → F、d[B] 3、d[C] 2、d[D] 8、d[E] 10 |
| Grid 4 × 5、Dijkstra 1-1 → 4-5 |
距離 7、確定順は 20 ノードすべてを列挙、経路 1-1 → 1-2 → 2-2 → 3-2 → 3-3 → 3-4 → 3-5 → 4-5 |
| 既定グラフ、A* と euclidean |
距離 13、同じ経路、展開ノード 6 / Dijkstra 6、ヒューリスティックスケール 0.01346、整合的最適 Yes |
| Negative weights プリセット、S からの Bellman–Ford |
3 ラウンドの緩和、d[S] 0、d[A] 3、d[B] 5、d[C] 0、d[D] 3、負の閉路 None |
| Negative weights プリセット、Floyd–Warshall S → D |
距離 3、経路 S → B → A → C → D、負閉路ノード None |
Dijkstra の d[C] = 2 は直接辺 A–C から、d[B] = 3 は A → C → B から来ており、重い方の辺 A–B(重み 4)からではありません。Bellman–Ford は −3 の辺があるグラフでも同じ値に達し、Floyd–Warshall は負の辺と正の辺を連結して S → B → A → C → D を見つけます。
A\* がスケールを出力する理由
キャンバス座標と辺の重みは別の量なので、A* はレイアウト上でヒューリスティックを測り、各弧で h(u) ≤ w(u,v) + h(v) を保つ最大の係数でスケールします。既定グラフでは euclidean のスケールが 0.01346 で、3 つのヒューリスティックはすべて Dijkstra と同じ 6 ノードを展開します。整合的最適の行は、返される距離が正確であるという約束です。
限界
- Dijkstra と A\* には非負の重み。
- どちらも大きすぎる距離を返す代わりに負の辺を拒否します。Negative weights プリセットには同じパネルで Bellman–Ford に切り替えてください。
- 1 回の実行に 1 つの始点。
- マルチソース Dijkstra も Johnson の全点対もありません。Floyd–Warshall が全点対の選択肢で、立方コストです。パネルはファイルから辺リストを読んだり経路を書き出したりもしません — 隣接行列をワークスペースに書き出し、matrix tools、最も安い配線には Spanning tree パネル、容量の問いには Flow & matching に持っていってください。
負の辺の境界
Negative weights プリセット(S → A 4、S → B 5、A → C −3、B → A −2、B → C 4、C → D 3)を構築し、Source S で Dijkstra を押します。パネルは、もっともらしい誤った数値ではなく、メッセージ "Edge 3 has weight -3. Dijkstra cannot handle negative weights (a settled distance could still be lowered) — use Bellman–Ford instead" で拒否します。アルゴリズムを Bellman–Ford に切り替えると S → C は 0 と読め、Dijkstra の貪欲な確定では決して生み出せなかった距離です。A* も同じ拒否を備え、そのメッセージも Bellman–Ford を指します。
活用場面
ツアーの最適性の証明
Dijkstra の確定順は、最終距離が正しいことの証明です。各頂点は一度だけ確定し、二度と再訪されません。既定グラフでは直接辺 A–B の重みが 4 ですが C 経由の経路は 3 で、順序 A → C → B → D → E → F は C が B より先に確定したことを示します — パネルは自らの正しさの論証を表示しています。
ヒューリスティックをスケールすべき理由を教える
A* を zero ヒューリスティックにすると、実行は帳簿付きの Dijkstra になります(スケール 1)。レイアウトされた既定グラフで euclidean にするとスケールは 0.01346 に下がり、経路を正確に保ったまま、推定値が真のコストを超えることはありません。
計画における負のコスト
Negative weights プリセットは 2 段階間のクレジットをモデル化します。Bellman–Ford は S → D を 3 と答え、Floyd–Warshall も同じ値を確認し、どちらも負の閉路を報告しないので、改善の連鎖 S → B → A → C → D は終了します。
プライバシー
グラフの編集とすべての shortest path の実行はブラウザ内で行われ、何もアップロードされません。
参考文献
- Wikipedia, Dijkstra's algorithm, en.wikipedia.org (访问日期:2026-10-07)— 貪欲な確定と非負の重み。
- Wikipedia, Bellman–Ford algorithm, en.wikipedia.org (访问日期:2026-10-07)— 緩和ラウンドと負閉路検出。
- Wikipedia, Floyd–Warshall algorithm, en.wikipedia.org (访问日期:2026-10-07)— 全点対の動的計画法。
- Wikipedia, A* search algorithm, en.wikipedia.org (访问日期:2026-10-07)— 許容的で整合的なヒューリスティック。
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— 単一始点最短経路。
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
- Updated