最短経路問題

最短経路問題を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();
        }
    }
}