SPATH プログラムのデモ

Computer Today 誌（サイエンス社）では、「アルゴリズムの道具箱」という連載記事が 掲載されましたが、その中の1999年1月--12月（No.89 -- No. 94）の 6 回を 私が担当しました。これはその後、臨時別冊・数理科学「アルゴリズムの 道具箱」、戸川隼人・有澤誠（編）、サイエンス社、2000年1月、として出版 されています。この第４回目に最短路問題を解説しましたが、その中で、 Dijkstra 法のプログラム を与えました。（私のホームぺージからダウンロードできます。） また、ほとんど同じプログラムは、私の書いた教科書「Ｃによるアルゴリズム とデータ構造」（昭晃堂）にも載っています。

下のデモは、このアルゴリズムの動作の様子を視覚的に見るようにした ものです。柳浦睦憲先生が学生実験用に開発したプログラムをもとに、 土村展之氏に作って貰いました。実は、「アルゴリズム工学」 の活動の一環ですので、興味ある方は そちら も訪ねて下さい。そこの「アルゴリズムデータベース」という所を見ると、 SPATH や TSP 以外にもいろいろなアルゴリズムのデモが揃っています。

さて、この SPATH アルゴリズムは、 与えられたグラフの始点から他のすべての節点への最短路を計算し、 それらを最短路木として与えます。計算に用いている Dijkstra（ダイクストラ） 法は、最短路木（赤色の枝）を１節点ずつ成長させていきますが、 追加される節点には、その時点のラベル（最短路の候補となる路の長さ） が最小のものが選ばれます。すべての節点が最短路木に含まれると、 計算終了となります。このアルゴリズムによって正確に最短路木が計算できる理由は、 「道具箱」あるいは「Ｃによる...」をお読み下さい。

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

デモの開始


茨木研究室ホームページへ

< Last update: June, 2000 >