在CPLEX中求解最短路径问题

        最短路径问题顾名思义，即求问题的最短路。
        如有以下问题，图中有1-5五个结点，求node1到node4的最短路径。答案非常明显，即1->2->4.

        表示各个结点之间的路径需要一个二元矩阵。假设

        CPLEX中.mod代码如下：

range I=1..5;
int t[I][I]=...;
dvar boolean x[I][I];

constraint originNodeBalance;
constraint destinationNodeBalance;
constraint otherNodeBalance;

minimize sum(i in I,j in I) t[i][j]*x[i][j];

subject to
{
    originNodeBalance=sum(j in I) x[1][j]==1;
    destinationNodeBalance=sum(i in I) x[i][4]==1;
    otherNodeBalance=forall(j in I:j!=1&&j!=4) sum(i in I) x[i][j]-sum(k in I) x[j][k]==0;
}

        CPLEX中.dat代码如下：

SheetConnection sheet("traveltime.xlsx");
t from SheetRead(sheet,"Sheet1! B2:F6");

        这样CPLEX中的模型就建好了，看看运行结果：

        结果中的最短路径为1->2->4，和肉眼判断的结果一致。