最短経路問題
最短経路問題をLPでどう書くかを忘れたので復習.
まずは,記号の準備をすると,
- 有向グラフ
- 枝の長さ
- からまでの最短路を求めたい.
このとき,最短経路問題は
のように記述できる.ここで,完全単模性よりは0,1変数であると考えてよい.は枝を選んだことを意味する.
さらに,双対問題について考えてみると次のようなLPとなる.
はポテンシャルを表す.
相補性原理から,はを意味する
おまけ.java+lpsolveで実装してみるとこんな感じ.
import static java.lang.Math.*; import static java.util.Arrays.*; import java.util.*; import java.io.*; import lpsolve.*; public class ShortestPath { private static final String IN_FILE = "sp_test.txt"; private Scanner sc; int v,e,s,t; int[] from, to; double[] weight; public static void main(String[] args) { new ShortestPath().run();} public void run(){ init(); System.out.println("primal"); primal(); System.out.println("dual"); dual(); } private void init(){ try{ sc = new Scanner(new File(IN_FILE)); }catch(FileNotFoundException e){ e.printStackTrace();} v = sc.nextInt(); e = sc.nextInt(); s = sc.nextInt(); t = sc.nextInt(); from = new int[e]; to = new int[e]; weight = new double[e]; for(int i=0;i<e;++i){ from[i]=sc.nextInt(); to[i]=sc.nextInt(); weight[i]=sc.nextDouble(); } } void primal(){ try { LpSolve solver = LpSolve.makeLp(v+e, e);//constraints, variables solver.setOutputfile("debug"); for(int i=0;i<v;++i){ String c = ""; for(int j=0;j<e;++j){ if(from[j]==i)c+= "1 "; else if(to[j]==i)c+= "-1 "; else c+="0 "; } if(i==s)solver.strAddConstraint(c, LpSolve.EQ, 1); else if(i==t)solver.strAddConstraint(c, LpSolve.EQ, -1); else solver.strAddConstraint(c, LpSolve.LE, 0); } for(int i=0;i<e;++i){ String c = ""; for(int j=0;j<e;++j)c+=(i==j)?"1 ":"0 "; solver.strAddConstraint(c, LpSolve.GE, 0); } solver.setMinim(); String obj = ""; for(int i=0;i<e;++i)obj+=weight[i]+" "; solver.strSetObjFn(obj); solver.solve(); System.out.println("distance from "+s+" to "+t+" is " + solver.getObjective()); solver.deleteLp(); } catch (LpSolveExceptionerr) { err.printStackTrace(); } } void dual(){ try { LpSolve solver = LpSolve.makeLp(e, v);//constraints, variables solver.setOutputfile("debug"); for(int i=0;i<e;++i){ String c = ""; for(int j=0;j<v;++j){ if(j==from[i])c+="-1 "; else if(j==to[i])c+="1 "; else c+="0 "; } solver.strAddConstraint(c, LpSolve.LE, weight[i]); } solver.setMaxim(); String obj = ""; for(int i=0;i<v;++i){ if(i==s)obj+="-1 "; else if(i==t)obj+="1 "; else obj+="0 "; } solver.strSetObjFn(obj); solver.solve(); System.out.println("distance from "+s+" to "+t+" is " + solver.getObjective()); solver.deleteLp(); } catch (LpSolveException err) { err.printStackTrace(); } } }