このデモでは、与えられたグラフの始点から他のすべての節点への最短路を計算し、 それらを最短路木として与えます。 計算に用いている Dijkstra（ダイクストラ） 法は、 最短路木（赤色の枝）を１節点ずつ成長させていきますが、 追加される節点には、その時点のラベル （最短路の候補となる路の長さ）が最小のものが選ばれます。 すべての節点が最短路木に含まれると、計算終了となります。

　アルゴリズムの動作は、１ステップずつ実行することもできますし、 自動的に最後まで走らせることもできます。 動作のスピードも調節できます。 なんと動作を逆にたどることもできます。 あれこれ試して、楽しみながらアルゴリズムを理解して下さい。

（茨木 俊秀）

---

プログラムは 茨木俊秀先生(京都大学) の 最短路問題のソースプログラム を元に作りました。

画面表示は 柳浦睦憲先生(京都大学) の グラフアルゴリズムのアニメーション を元に作りました。