假设我们想使用 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 权重边
不知道在此之后该怎么办...请帮助，谢谢。
这是我的方法，但我不认为它是 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 执行此操作，并取最小值。
在一般情况下，您不能使用 bellman-ford 算法来解决这个问题。anil的回答（在此页面上）提到了一个反例。在他的回答中提到的图表中，我们有一个负圆 ( sum of weights = -1): x1->x2->x3->x4->x5->x1，所以我们不能对这种类型的图表和问题使用贝尔曼福特算法。