2022-10-01から1ヶ月間の記事一覧

コスト変化が変なときのダイクストラ法

概要通常の最短経路問題と違って、辺を通ったときのコストの変化のしかたが変な場合でも、ダイクストラ法で解けることがある。ダイクストラ法を適用できる条件は「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらな…