目前，差分约束系统在当代的应用可谓是越来越广泛

目前，差分约束系统在当代的应用可谓是越来越广泛，差分约束系统是值得我们好好学习的。现在我们就深入了解差分约束系统，希望本文能对各位读者有比较大的参考价值。

差分约束系统（system of difference constraints），是求解关于一组变量的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如：xj-xi<=bk（ij∈[1n]k∈[1m]）。 如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(ij∈[1n]k∈[1m])则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

求解差分约束系统，可以转化成图论的单源最长路径问题。观察xj-xi<=bk，会发现它类似最短路中的三角不等式d[v] <=d[u]+w[uv]，即d[v]-d[u]<=w[uv]。因此，以每个变量xi为结点，对于约束条件xj-xi<=bk，连接一条边（ij），边权为bk。再增加一个原点（ss）与所有定点相连，边权均为0。对这个图以s为原点运行Bellman-ford算法（或SPFA算法），最终{d[i]}即为一组可行解。

如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(ij∈[1n]k∈[1m])则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

综上所述，本文已为讲解差分约束系统，相信大家对差分约束系统的认识越来越深入，希望本文能对各位读者有比较大的参考价值。