サブロウ丸

大学生です

最短路問題を線形計画法で解く2

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、
今回も線形計画法で解いてみたいと思います。(あえてね)

f:id:inarizuuuushi:20170707214114j:plain:w600
f:id:inarizuuuushi:20170707223123p:plain:w600

が定式化となります。(とするとが続いているところは無視してください)
路の制約として、フロー整合条件を使用しました。
この定式化では最短路長とそれを実現する最短路がすぐに求まります。
また、枝に関する制約を付け加えやすい形になっていますね。

フロー整合条件についてですが、
f:id:inarizuuuushi:20170707215159j:plain:w600

上の性質がスタートとゴール以外で成立していればスタートからゴールまでの路が存在します。(量が1のフローがスタートからゴールに流れているということになります)