文档介绍：(本文假设读者已经有以下知识:最短路径的基本性质、Bellman-Ford 算法。) 比如有这样一组不等式: X1 -X2 <= 0X1 -X5 <= -1 X2 -X5 <= 1X3 -X1 <= 5X4 -X1 <= 4X4 -X3 <= -1 X5 -X3 <= -3 X5 -X4 <= -3 不等式组(1) 全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘以-1就可以化成小于等于)。这样的不等式组就称作差分约束系统。这个不等式组要么无解,要么就有无数组解。因为如果有一组解{X1, X2, ..., Xn} 的话,那么对于任何一个常数 k,{X1 +k,X2+k,..., Xn+k} 肯定也是一组解,因为任何两个数同时加一个数之后,它们的差是不变的,那么这个差分约束系统中的所有不等式都不会被破坏。差分约束系统的解法利用到了单源最短路径问题中的三角形不等式。即对于任何一条边 u->v,都有: d(v) <= d(u) +w(u, v) 其中d(u) 和d(v) 是从源点分别到点u和点v的最短路径的权值,w(u, v) 是边 u->v的权值。显然以上不等式就是 d(v) -d(u) <=w(u, v)。这个形式正好和差分约束系统中的不等式形式相同。于是我们就可以把一个差分约束系统转化成一张图,每个未知数 Xi对应图中的一个顶点 Vi,把所有不等式都化成图中的一条边。对于不等式 Xi-Xj<=c,把它化成三角形不等式: Xi<=Xj+c,就可以化成边 Vj->Vi,权值为 c。最后,我们在这张图上求一次单源最短路径,这些三角形不等式就会全部都满足了,因为它是最短路径问题的基本性质嘛。话说回来,所谓单源最短路径,当然要有一个源点,然后再求这个源点到其他所有点的最短路径。那么源点在哪呢?我们不妨自已造一个。以上面的不等式组为例,我们就再新加一个未知数 X0。然后对原来的每个未知数都对 X0随便加一个不等式(这个不等式当然也要和其它不等式形式相同,即两个未知数的差小于等于某个常数)。我们索性就全都写成 Xn-X0<=0,于是这个差分约束系统中就多出了下列不等式: X1 -X0 <= 0X2 -X0 <= 0X3 -X0 <= 0X4 -X0 <= 0 X5 -X0 <= 0不等式组(2) 对于这 5个不等式,也在图中建出相应的边。最后形成的图如下: 图1 图中的每一条边都代表差分约束系统中的一个不等式。现在以 V0为源点,求单源最短路径。最终得到的 V0到Vn的最短路径长度就是 Xn的一个解啦。从图 1中可以看到,这组解是{-5, -3, 0,-1, -4} 。当然把每个数都加上 10 也是一组解: {5, 7,10, 9,6}。但是这组解只满足不等式组(1) ,也就是原先的差分约束系统;而不满足不等式组(2) ,也就是我们后来加上去的那些不等式。当然这是无关紧要的,因为 X0本来就是个局外人,是我们后来加上去的,满不满足与 X0有关的不等式我们并不在乎。也有可能出现无解的情况,也就是从源点到某一个顶点不存在最短路径。也说是图中存在负权的圈。这一点我就不展开了,请自已参看最短路径问题的一些基本定理。其实,对于图 1来说,它代表的一组解其实是{0, -5, -3, 0,-1, -4} , 也就是说 X0的值也在这组解当中。但是 X0的值是无可争议的,既然是以它作为源点求的最短路径,那么源点到它的最短路径长度当然是 0了。因此,实际上我们解的这个差分约束系统无形中又存在一个条件: X0 =0 也就是说在不等式组(1) 、(2) 组成的差分约束系统的前提下,再把其中的一个未知数的值定死。这样的情况在实际问题中是很常见的。比如一个问题表面上给出了一些不等式,但还隐藏着一些不等式,比如所有未知数都大于等于 0 或者都不能超过某个上限之类的。比如上面的不等式组(2) 就规定了所有未知数都小于等于 0。对于这种有一个未知数定死的差分约束系统,还有一个有趣的性质,那就是通过最短路径算法求出来的一组解当中,所有未知数都达到最大值。下面我来粗略地证明一下,这个证明过程要结合 Bellman-Ford 算法的过程来说明。假设 X0是定死的;X1到Xn在满足所有约束的情况下可以取到的最大值分别为 M1、M2、……、Mn(当然我们不知道它们的值是多少);解出的源点到每个点的最短路径长度为 D1、D2、……、Dn。基本的 Bellman-Ford 算法是一开始初始化 D1到Dn都是无穷大。然后检查所有的边对应的三角形不等式,一但发现有不满足三角形不等式的情况,则更新对应的 D值。最后求出来的 D1到Dn就是源点到每个点的最短路径长度。如果我们一开始初始化 D1、D2、……、Dn的值分别为 M1、M2、……、 Mn,则由于它们全都满足三角形不等式