差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。也就是开始各点不符合条件，后来通过减小变得符合了，所以一定是符合条件的最大值。既然是求最大值，并且是减小各点距离，也就是把各点由数轴的右侧向左侧拉，所以我们一定要选择一个最终在数轴最左侧的点，并初始化为0，把所有正无穷的点拉近到符合不等式。最长路同理。
最短路求得是最大值，最长路求得是最小值。
全都是两个未知数的差小于等于某个常数（大于等于也可以，因为左右乘以-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<=0
X2-X0<=0
X3-X0<=0
X4-X0<=0
X5-X0<=0
结束语：以上就是关于差分约束算法的全部内容，更多内容请关注学步园。