Bellman-Ford算法的差分约束

Question

假设我们想使用贝尔曼-福特最小化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}是可以为负数的指定常量。

我如何证明贝尔曼-福特算法可以在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 <= ci，j，我们可以通过将其他约束的线性组合来找到对x_i和x_j的更紧密的约束，这些约束由这个完整图中的路径表示。

所以固定任何顶点x_i，并找到它最紧的约束，也就是说，贝尔曼·福特到任何其他顶点的最短路径。然后，对所有的i执行此操作，并取最小值。

Answer 2

在一般情况下，您不能使用贝尔曼-福特算法来解决这个问题。anil的答案中提到的一个反例(在本页)。在他的答案中提到的图中，我们有一个负圈(sum of weights = -1)：x1->x2->x3->x4->x5->x1，所以我们不能使用贝尔曼-福特算法来处理这种类型的图和问题。