2009-10-12から1日間の記事一覧

最短経路問題

最短経路問題をLPでどう書くかを忘れたので復習.まずは,記号の準備をすると, 有向グラフ 枝の長さ からまでの最短路を求めたい. このとき,最短経路問題はのように記述できる.ここで,完全単模性よりは0,1変数であると考えてよい.は枝を選んだことを意…