最短路问题的整数编程模型

最短路问题是指在一个有向带权图中，找到一个起点到终点的路径，使得路径上边的权值之和最小。整数规划是指变量必须取整数值的线性规划问题。下面是最短路问题的整数规划模型：

假设有向带权图 $G=(V,E)$，$s$ 是起点，$t$ 是终点。设 $x_e$ 表示边 $e \in E$ 是否被选中，如果被选中，则 $x_e=1$，否则 $x_e=0$。设 $w_e$ 表示边 $e$ 的权值。则最短路问题的整数规划模型为：

其中，$\delta^+(v)$ 表示以 $v$ 为起点的边的集合，$\delta^-(v)$ 表示以 $v$ 为终点的边的集合。第一个限制条件保证了起点只有一条出边，最后一个限制条件保证了终点只有一条入边，中间的限制条件保证了其它节点的流量平衡。整数规划的限制条件确保了 $x_e$ 必须取整数值。

这个整数规划模型可以用 ILP（整数线性规划）求解器求解。求解器会输出一组满足所有限制条件的整数解，其中 $x_e=1$ 的边就是最短路上的边。