ループのない有向重み付きグラフにおける最短経路問題

昨日、問題Dにダイクストラを持ち出す必要がないことが分かって
驚愕した訳であるが、これをもうちょっと一般的に考えると、
ループのない有向重み付グラフにおける最短経路問題が
再帰+メモで解けることが分かった。
再帰的定義は、あるノードからのゴールまでの距離である。
これがすべてのノードにつき高々一回計算されれば良いので
非常に効率よく計算できる。
このアルゴリズムでは、全ノードからのあるノードへの距離が分かる。
ダイクストラ法ではあるノードから全ノードまでの距離が求まるわけであるが、
グラフの向きを逆にするとこれらは等価であることが分かる。
そういうわけで、グラフにループがなければこれからは
ダイクストラは使わないことにする。
ダイクストラは効率の良い実装をしようと思うと
なんだか色々と引っかかるところがあるのだ。
コードを持ち込むと言う手もあるが、
タイピング速度が遅いのであんまり紙から書き写すということをしたくない。


ちなみに、グラフにループがある場合は
再帰的な計算もループしてしまうので簡単には出来そうにない。
とりあえず今のところ、こういう場合はダイクストラを実装しなければ
仕方がないかなぁ、と思っているが、
なにかうまい方法がないかもう少し考えてみることにする。