最短路的基本性质
如果图中不存在负权回路，则当算法结束以后，对于边\((x,y,w)\)有\(dist[y] <= dist[x] + w\)成立。
差分约束系统
对于一组不等式
特点是全部是两个未知数的差小于等于某一个常数，这样的不等式组就称为差分约束系统。
这个不等式要么无解，要么就存在无限组解。因为如果存在一组解\({x_1,x_2,...,x_n}\)的话，那么对于任何一个常数\(k\)有\(\lbrace x_1+k,x_2+k,...,x_n+k\rbrace\)也肯定是一组解，因为任何两个数加上一个数后，他们之间的关系是不变的，差分约束系统所有的不等任然是满足的
差分约束系统与最短路径
差分约束系统的解法用到了单元最短路径问题中的三角不等式。对于有向图中任意一条边\((u,v)\)都有：\(dist[v] <= dist[u] + len[u]][v]\)
如果存在顶点\(u\)到顶点\(v\)的有向边，那么从源点到顶点\(v\)的最短路径小于等于从源点到顶点\(u\)的最短路径长度加上边(u,v)的长度
上述不等式和差分约束系统中的不等式相同，因此就可以把差分约束系统转化成一张图求解
构图
对于未知数\(x_i\)对应图中的一个顶点\(v_i\)，把所有不等式都转化为图中的一条边，对于不等式\(x_i - x_j \leq y\)转化为三角不等式\(x_i\leq x_j + y\)，就可以化成边\((x_i,x_j,y)\)，最后在这条边上求一遍单源最短路径，这些不等式就全部满足了，因此它是单元最短路的基本性质
求解
若存在负环\正环，则不等式组一定矛盾，以不同的顶点出发会得到不同的解，但这些解都一定合理
增加源点
源点需要满足的条件：从源点出发，一定可以走到所有的边。从0号点可以走到任意的边，则一定可以到达所有边，具体在实现算法的时候，可以附加上超级源点，这个顶点和每一个顶点都连接一条权值为0的边。
算法求解的步骤
如果存在负环，则原不等式一定无解，否则，dist[i]就是原不等式组的一个可行解
最大值和最小值的求法
如果求得是最小值，则应该求最长路，如果求最大值，应该求最短路。
对于\(x_i\leq c\)不等式的转化，建立一个超级源点0，然后建立从0到\(i\)的边，长度是\(c\)即可
最长路对应大于关系，最短路对应小于关系
原文：https://www.cnblogs.com/zykBlog/p/13855838.html