algorithm - 如何为最短路径问题制定 LP？

Question

我正在尝试了解最短路径问题的 LP 公式是如何工作的。但是我无法理解约束。为什么这个公式有效？

http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf

我无法理解第 15 页和第 17 页的约束是如何工作的。我明白了主要思想，并且我理解 x 应该如何以及为什么应该取一些值，但我不理解整个系统在数学方面是如何工作的。有人可以解释吗？在考试中，我应该能够创建和修改此类约束，但我离做到这一点还有很长的路要走。

Answer 1

那些幻灯片(第 15 和 17 页)中不太清楚的是，以“s.t.”开头的行。实际上是为每个顶点 i 指定一个约束，即总共 n 个单独的约束(如果有 n 个顶点)。通常，这将通过在约束旁边写上类似“∀i ϵ V”的内容来传达。

在任何情况下，这条线表示对于每个顶点 i，从任何其他顶点进入它的流量总量必须等于离开它的流量总量——除非该顶点是源头，在这种情况下，总量离开它的流量必须大于 1，或者汇，在这种情况下，进入它的流量总量必须大于 1。首先如何提出这个约束系统可能并不明显，但是通过查看一些示例，您应该能够看到任何最短路径(或者实际上，从 s 到 t 的任何路径)都满足所有这些:路径中的每个内部顶点都有 1 个入边和 1 个出边，而 s 和 t 将分别只有 1 个传出边或 1 个传入边。根本不参与路径的顶点有 0 个传入和 0 个传出流，因此它们也有效。

还有一点是，对于流量问题，标记边缘的数字通常代表容量限制——两个端点之间流量的最大限制——而不是像这里那样的成本.