差分约束的最短路径算法证明和解释。

差分约束系统

• 差分约束系统用一个m×n的线性规划矩阵表示m个不等式，这m个不等式中共n个变量x1,x2,…,xn，每个不等式满足如下形式：xi - xj <= bk（1 <= i, j <= n, 1 <= k <= m），在矩阵中的表示为，每一行都有一个1和一个-1,其他元素都为0。例如

  1	-1	0	0	0
  1	0	0	0	-1
  0	1	0	0	-1
  -1	0	1	0	0
  -1	0	0	1	0
  0	0	-1	1	0
  0	0	-1	0	0
  0	0	0	-1	1

  用上面的矩阵乘一个n×1的变量矩阵x = (xi)，使其满足一个m×1的常数矩阵（bk）。等价于找出下面8个不等式的可行解：x1 - x2 <= b1; x1 - x5 <= b2; x2 - x5 <= b3; x3 - x1 <= b4; x4 - x1 <= b5; x4 - x1 <= b6; x5 - x3 <= b7; x5 - x4 <= b8。对于bk = (0, -1, 1, 5, 4, -1, -3, -3)的一个序列，x的一个可行解为(-5, -3, 0, -1, -4)，同样，对于任意x’ = x+d，d为任意常数，x’也是该不等式组的一组解。

约束图

• 观察差分约束系统的不等式，发现其与最短路径松弛操作相似。松弛操作的判断条件是d[v] <= d[u] + w(u, v)，差分约束方程中为xi - xj <= bk，因此xi <=> d[v]，xj <=> d[u]，w(u, v) <=> bk，据此建边vj->vi，权值为bk，变量x1,x2,…,xn分别对应结点s1,s2,s3,…,sn。
• 在上述图中，附加一个源点s0,将其与所有顶点相连，并将s0的所有出边权值均设为0。下面将证明，给定一个差分约束系统Ax<=b，设G=(V,E)为该系统对应的约束图，则如果G不包含负权环，从s0到其它各点的最短路径权值就是一组可行解，否则此系统不存在可行解。证明过程如下：当G不包含负权回路时，对于任意边(vi, vj)，根据三角不等式d[vj] <= d[vi] + w(vi, vj)，设d[vi] = xi， d[vj] = xj，那么xj - xi <= w(vi , vj)，因此满足对应边（vi, vj）的差分约束。而当G中包含负权回路时，假设负权回路为，其中v1 = vk（源点s0没有入边，不可能出现在负权环上），因此整个负权环对应如下的差分约束：x2 - x1 <= w(v1,v2)；x3 - x2 <= w(v2, v3);…;xk - xk-1 <= w(vk-1, vk)，将这k-1个不等式相加，则左边为0,而右边是负数，矛盾。因此不存在解。

最大解与最小解

• 当差分约束条件给出其中一个解xi，即固定解的一个元素，求解的其他元素所能取到的最大解或最小解。在约束图的创建中，我们将从源点引出的边权值都赋为0,其实隐含着：d[vi] - d[v0] <= 0这样的条件，因此求出的解一定小于等于零，如果我们把s0也看作一个变量x0,那么上面例子中的解就是(0, -5, -3, 0, -1, -4)，也就是预先指定了x0的解为0。这里的x0就是源点s0的偏移量，例如当题中增加条件，要求解的所有元素都小于某个值，此时只要将该值设置为s0的偏移量即可。
• 对于这类有一个未知数已经定死的情况，还有一个性质：通过最短路径算法求出的一组解是所有解中的最大值。考虑到Bellman-Ford等单源最短路径算法的初始化都是d[vi] = 正无穷，通过各种约束条件使d[vi]的值不短减小来满足，因此当所有约束条件都满足，无法松弛任意边时，求出的解就是最大解。同样，如果要求所求得的解是所有解中的最小解，只要将问题转化为求解最长路径，松弛条件变为d[v] >= d[u] + w(u, v)，此时的不等式变为xj - xi >= -bk，因此建边vi->vj，权值为-bk，求其最长路径，即为最小值。

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://forec.github.io/2015/12/24/Graph-Algorithms6/) 、作者信息（Forec）和本声明。