A. 最短経路問題とは？
ここで述べる最短経路問題とは，複数の都市が存在し，それらの都市がいくつかの道で繋がっているとき，ある都市から目的とする都市へ向かう経路の内，最短となる経路及びその経路長を求める問題です．例えば，都市の数が 10 の場合は，以下に示すような経路を求めることになります．
B. 遊び方
パズルの実行を開始すると，以下に示すような画面が表示されます．
下に示すのは，10 都市，及び，20 都市に対する例です．この画面における円が都市に相当し，都市を結ぶ直線（都市を結ぶ道に相当）の近くに表示されている数字が都市間の距離を表し，実行する毎にランダムに変化します．
この画面において，適当な都市をクリックすると画面の下部に「 Next？」というメッセージが表示されますので，その都市と結びたい都市をクリックしてください．メッセージが消え，2 つの都市が太く赤い直線で結ばれます．ただし，その都市間が直線で結ばれていない（都市を結ぶ道が存在しない）場合は，結ぶことができません．メッセージが表示されなかったり，直線で結ばれなかった場合は，再度クリックしてください．なお，都市を結ぶ順序と都市の訪問順序は関係ありませんので，どのような順番で都市間を結んでも構いません．また，同じ都市を続けてクリックすれば，「 Next？」メッセージが消え，何もクリックしない状態に戻ります．さらに，不適切な都市間を結ぼうとすると，画面の下部に「 ***ルール違反です」というメッセージが表示されます． 結んだ直線を消したい場合は，その直線の両端の都市を順にクリックしてください．線を結ぶ場合と同じように，最初の都市をクリックすると画面の下部に「 Next？」というメッセージが表示され，次の都市をクリックすると直線が消去されます．
スタートからゴールまでの都市が正しく結ばれると，画面の下部に，その経路長が出力されます．その経路が最短である場合は，経路長の後ろに「 : 最短経路長です！」というメッセージが出力されます．なお，最短経路長は一つですが，経路は複数存在するかもしれません．
コメント