グラフの最短路問題はダイクストラ法等で解くのが普通ですが、
今回も線形計画法で解いてみたいと思います。(あえてね)
↓その1です。
inarizuuuushi.hatenablog.com
が定式化となります。(とするとが続いているところは無視してください)
路の制約として、フロー整合条件を使用しました。
この定式化では最短路長とそれを実現する最短路がすぐに求まります。
また、枝に関する制約を付け加えやすい形になっていますね。
フロー整合条件についてですが、
上の性質がスタートとゴール以外で成立していればスタートからゴールまでの路が存在します。(量が1のフローがスタートからゴールに流れているということになります)
