algorithm - Bellman-Ford 算法的差异约束

Question

假设我们想使用 Bellman-Ford 来最小化 max_i x_i - min_i x_i

在变量 x_1, x_2, ... x_n 上(总共 n 个变量)

受到形式为 x_i - x_j <= c_{i,j} 的 m 约束

其中 c_{i,j} 是指定的常数，可以为负数。

如何证明 Bellman-Ford 可以在 O(n*m) 时间内解决此类问题？

我尝试了以下方法:

为每个变量 x_i 创建一个节点 i

制作一个源节点s

创建从 s 到所有其他节点的 0 权重边

不知道之后该怎么办...请帮忙，谢谢。

Answer 1

这是我的方法，但我不认为它是 O(m * n)，但它可能会引导您朝着正确的方向前进。尝试画一幅画是一件好事，假设我们有以下约束:

相应的约束图如下所示:

现在请注意，在您的情况下，您拥有一整套约束，因此约束图将是一个完整的图。我们现在将根据您的问题考虑图中的路径。现在考虑一条从 x_i 开始，到 x_j 结束的路径。这通过点 x_i1、x_i2 ...、x_ik。所以我们的路径是 { x_i, x_i1, ..., x_ik, x_j }。由于不等式的设置方式，这条路径给了我们一个新的约束 (x_i - x_i1) + (x_i1 - x_i2) + ... + (x_ik - x_j) = x_i - x_j。

这里发生的事情是，即使我们有一个约束 x_i - x_j <= c[i,j]，我们可以通过采用其他约束的线性组合来找到对 x_i 和 x_j 的更严格的约束，这些约束由此中的路径表示完整的图表。

因此固定任何顶点 x_i 并找到它的最紧约束，即 bellman ford 到任何其他顶点的最短路径。然后对所有 i 执行此操作，并取最小值。