如何为最短路径问题制定 LP？
How to formulate LP for shortest path problems?
我正在尝试了解最短路径问题的 LP 公式是如何工作的。但是我无法理解约束。为什么这个公式有效？
http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf
我无法理解第 15 页和第 17 页的约束是如何工作的。我明白了主要思想，我理解 x 应该如何以及为什么应该取一些值，但我不明白整个系统是如何工作的数学。有人可以解释吗？在考试中，我应该能够创建和修改此类约束，但我离做到这一点还差得很远。
那些幻灯片（第 15 和 17 页）中不是很清楚的是，以 "s.t." 开头的行实际上指定了一个约束 per vertex i ，即总共 n 个单独的约束（如果有 n 个顶点）。通常这会通过在约束旁边写上类似“∀i ϵ V”的内容来传达。
在任何情况下，此行表示对于每个顶点 i，从任何其他顶点进入它的流量总量必须等于离开它的流量总量 - 除非该顶点是源，在这种情况下离开它的流量总量必须大于 1，或者汇，在这种情况下，进入它的流量总量必须大于 1。首先如何提出这个约束系统可能并不明显放置，但是通过查看一些示例，您应该能够看到任何最短路径（或者实际上，从 s 到 t 的任何路径）都满足所有这些：路径中的每个内部顶点都有 1 个入边和 1 个出边，而 s 和 t 将分别只有 1 个出边或 1 个入边。完全不参与路径的顶点有 0 个传入和 0 个传出流，因此它们也有效。
还有一点是，对于流量问题，标记边缘的数字通常代表容量限制——两个端点之间流量的最大限制——不是他们在这里的成本。
我正在尝试了解最短路径问题的 LP 公式是如何工作的。但是我无法理解约束。为什么这个公式有效？
http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf
我无法理解第 15 页和第 17 页的约束是如何工作的。我明白了主要思想，我理解 x 应该如何以及为什么应该取一些值，但我不明白整个系统是如何工作的数学。有人可以解释吗？在考试中，我应该能够创建和修改此类约束，但我离做到这一点还差得很远。
那些幻灯片（第 15 和 17 页）中不是很清楚的是，以 "s.t." 开头的行实际上指定了一个约束 per vertex i ，即总共 n 个单独的约束（如果有 n 个顶点）。通常这会通过在约束旁边写上类似“∀i ϵ V”的内容来传达。
在任何情况下，此行表示对于每个顶点 i，从任何其他顶点进入它的流量总量必须等于离开它的流量总量 - 除非该顶点是源，在这种情况下离开它的流量总量必须大于 1，或者汇，在这种情况下，进入它的流量总量必须大于 1。首先如何提出这个约束系统可能并不明显放置，但是通过查看一些示例，您应该能够看到任何最短路径（或者实际上，从 s 到 t 的任何路径）都满足所有这些：路径中的每个内部顶点都有 1 个入边和 1 个出边，而 s 和 t 将分别只有 1 个出边或 1 个入边。完全不参与路径的顶点有 0 个传入和 0 个传出流，因此它们也有效。
还有一点是，对于流量问题，标记边缘的数字通常代表容量限制——两个端点之间流量的最大限制——不是他们在这里的成本。