ループのない有向重み付きグラフにおける最短経路問題 - 純粋関数型雑記帳
昨日、問題Dにダイクストラを持ち出す必要がないことが分かって 驚愕した訳であるが、これをもうちょっと一般的に考えると、 ループのない有向重み付グラフにおける最短経路問題が 再帰+メモで解けることが分かった。 再帰的定義は、あるノードからのゴールまでの距離である。 これがすべてのノードにつき高々一回計算されれば良いので 非常に効率よく計算できる。 このアルゴリズムでは、全ノードからのあるノードへの距離が分かる。 ダイクストラ法ではあるノードから全ノードまでの距離が求まるわけであるが、 グラフの向きを逆にするとこれらは等価であることが分かる。 そういうわけで、グラフにループがなければこれからは ダイクストラは使わないことにする。 ダイクストラは効率の良い実装をしようと思うと なんだか色々と引っかかるところがあるのだ。 コードを持ち込むと言う手もあるが、 タイピング速度が遅いのであんまり紙から書
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
NFL JAPAN.COM｜新しいシーズン到来！導入された新しいものは？ ［河田 剛］
Slow renders when far away from origin
