在一个由n个变量和m个约束条件组成的系统，如\(x_i-x_j<=k_t\)，在不等式组中，要求任意一组特解
将一个不等式变换，\(x_j+k_t>=x_i\)
这看起来很像spfa三角不等式的判断，如果把整个系统看作一张有向图，这个式子又可以写成
\(dis[pos]+val>=dis[to]\)
这个不等式的反向命题
\(dis[pos]+val<dis[to]\)
必须不成立
即当每一个都无法再对其临接点更新时，整个不等式组成立
利用spfa算法对整个图松弛即可得到一个可行的特解
若此不等式组不存在解，一定会有以下情况发生
\(x_i-x_j>k\)
\(x_j-x_i>k\)
放在图中就是一对可以互相松弛的点，成为一个负环，判断图中是否存在负环得到是否有解
自此，spfa可以完美的解决差分约束的问题
? ——2020.5.22
原文：https://www.cnblogs.com/nebulyu/p/12935570.html