最短経路問題

出発地点から,その他すべての地点への最短経路を求めます. 2地点間の最短経路を求めるために, すべての経路を調べ尽くす必要はありません.出発地点から 「触手を伸ばすように」次々と近い方から順に他のすべての地点への 最短経路を決めていくことが可能です.

その様子を以下のデモ(地点数800)で見てみましょう.途中経過が わかるように,ゆっくりと表示しています.具体的なアルゴリズムの説明は 前のページをみてください.

ロードに時間がかかります

      --- 出発地点
      --- 出発地点以外の地点
      --- 出発地点からの最短経路が確定した地点
      --- 出発地点からの暫定的な最短経路を決めた(「触手」が触れた)地点
      --- 最短経路に使われる道路

前のページに戻る  最初のページに戻る