使用YALMIP+gurobi求解最短路径问题

最短路径问题是指从一个起点到一个终点，经过若干个中间节点，使得路径上的边权之和最小。本文将介绍如何使用YALMIP和gurobi求解最短路径问题。

首先，需要安装YALMIP和gurobi，并将它们与MATLAB集成。然后，定义问题的变量和约束条件。假设有n个节点和m条边，其中边e的起点为i(e)，终点为j(e)，权重为w(e)。定义变量x(e)表示边e是否在路径中出现，即x(e)=1表示边e在路径中，x(e)=0表示边e不在路径中。则问题可以表示为：

minimize ∑e∈E w(e)·x(e)
subject to
x(e)∈{0,1} for all e∈E
∑e∈δ+(i) x(e) - ∑e∈δ-(i) x(e) = {1 if i=s, -1 if i=t, 0 otherwise} for all i∈V-{s,t}

其中，E表示边集，V表示节点集，s表示起点，t表示终点，δ+(i)表示以节点i为起点的边集，δ-(i)表示以节点i为终点的边集。

然后，需要使用YALMIP来定义问题，并使用gurobi求解。代码如下：

% 定义变量和参数
n = 5; % 节点数
m = 7; % 边数
s = 1; % 起点
t = 5; % 终点
i = [1 1 2 2 3 4 4]; % 边的起点
j = [2 3 3 4 5 5 3]; % 边的终点
w = [2 1 3 2 1 3 1]; % 边的权重

x = binvar(m,1); % 定义变量x(e)
obj = w*x; % 定义目标函数
constr = [];
for k = 1:n
    if k == s % 起点
        constr = [constr, sum(x(find(i==k))) - sum(x(find(j==k))) == 1];
    elseif k == t % 终点
        constr = [constr, sum(x(find(i==k))) - sum(x(find(j==k))) == -1];
    else % 中间节点
        constr = [constr, sum(x(find(i==k))) - sum(x(find(j==k))) == 0];
    end
end

% 定义问题
ops = sdpsettings('solver','gurobi');
optimize(constr,obj,ops);

% 输出结果
value(obj)
value(x)

运行上述代码，可以得到最优解为4，路径为1->2->4->5。