ダイクストラ法の最短経路計算

ダイクストラ法は、辺の重みが負でないグラフで、1つのノードから他のすべてのノードへの最短経路を求めます。経路案内、ネットワークのルーティング、多くの教科書の演習問題の基礎になっているアルゴリズムです。辺をリストで入力して開始ノード（任意で終了ノード）を選ぶと、この計算ツールがすべての最短距離と経路、そして手作業で追うときのように、どのノードを訪問してどの距離を更新したかを示すステップごとの表を出力します。

使い方

1. 1行に1本ずつ、始点・終点・重みを入力します（A B 4）。
2. 一方向の辺なら「有向」をオンに、双方向ならオフのままにします。
3. 開始ノードと、必要なら終了ノードを入力します。
4. 距離と経路、全ノードの表、ステップごとの過程を確認します。

計算式

繰り返し：未訪問ノードのうちd(u)が最小のuを訪問 · u → vの辺（重みw）ごとに、d(u) + w < d(v)ならd(v) = d(u) + w、prev(v) = u

開始ノード（0）を除くすべての距離は∞から始まります。ノードを訪問するとその距離は確定しますが、これは重みが負でない場合にのみ保証されるため、負の重みは受け付けません（ベルマン–フォード法なら扱えます）。経路は、prevをたどって開始ノードまで遡って復元します。同順位の場合は先に書いたノードが優先されます。並行する辺も許可され、安いほうが採用されます。

計算例

サンプルは『Introduction to Algorithms』（CLRS）の図24.6の有向グラフです。sから出発すると、訪問順はs（0）、y（5）、z（7）、t（8）、x（9）です。xまでの最短経路はs → y → t → x、長さ9（5 + 3 + 1）です。直接つながっているように見えるs → tの辺（10）は、s → y → t（8）に負けます。