定义

如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。 求解差分约束系统，可以转化成图论的单源最短路径（或最长路径）问题。 观察Xj-Xi<=bk，会发现它类似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边(i,j)，边权为bk。我们再增加一个源点s,s与所有定点相连，边权均为0。对这个图，以s为源点运行Bellman-ford算法（或SPFA算法），最终{d[i]}即为一组可行解。

注意到如果{a1,a2,a3..an}是一组解，那么对于常数b,{a1+b,a2+b,a3+b}也是一组解。 设dis[0]=0,以0为起点的求单源最短路。若图中存在负环，则给定的差分约束系统误解，否则，Xi = dis[i]就是差分约束系统的一组解。在某些题目中，约束条件如Xi-Xj>=Ck。任然一样，只不过在计算单源最短路的时候，若图中存在正环，则无解。当然也可以堪称Xj-Xi<=-Ck计算