経由地点あり最短路問題。

現在は、Point-to-Point（p2p:１対１）、Single-Source（ss:１対全）の２タイプの問題を扱っているのだが、「経由地点を入力する事は可能か」と質問をいただいた。確かに実際にナビゲーションとして用いる際には必要な機能になるのだが、実は驚くほど容易にできる。


たとえば、「Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｅ→Ｆ→Ｇ→Ｈ」という最短経路問題では、

クエリ数：７
Ａ→Ｂ、Ｂ→Ｃ、Ｃ→Ｄ、Ｄ→Ｅ、Ｅ→Ｆ、Ｆ→Ｇ、Ｇ→Ｈ

といった、P2P タイプのクエリを７つとけば良い。
クエリ間は独立しているために、並列に求解することが可能になる。


また、各枝長が対称（行き帰りが同じ長さ）であるなら、もう少し工夫する事も可能になる。

ダイクストラ法は１点から全点への最短路（ssタイプのこと）を求めることができるアルゴリズムであるので、以下のようにまとればクエリ数も半数程度となる。

クエリ数：４
Ｂを始点として、Ａ、Ｃのどちらにも到達したら終了
Ｄを始点として、Ｃ、Ｅのどちらにも到達したら終了
Ｆを始点として、Ｅ、Ｇのどちらにも到達したら終了
Ｇ→Ｈ


条件が増える事によって低速化してしまうことも考えられるが、１対全であっても高速に実行できるので、思い切って ss にしてしまってもよいだろう。

クエリ数：４
Ｂ、Ｄ、Ｆをそれぞれ始点とした１対全(ss)最短路問題
Ｇ→Ｈ



いずれこちらで公開する予定である。

Shortest Path Online Solver
http://opt.indsys.chuo-u.ac.jp/portal/