算法学习之路|差分约束系统

摘要： 差分约束系统实际上是一种转化，把某些问题转化成最短路问题来进行求解

差分约束系统实际上是一种转化，把某些问题转化成最短路问题来进行求解

差分约束系统解决的问题是不等式的求解：

例如：

x2-x0<=3;

x4-x2<=2;

x3-x0<=5;

x1-x0<=4;

x3-x1<=1;

x4-x3<=1;

x3-x2<=3;

如果要求x4-x0的不等式解，显然可用不等式俩俩相加的方法求，求出是:

x4-x0<=5,x4-x0<=6;x4-x0<=7这三个式子显然最后求交集(ˇˍˇ) x4-x0<=5

我们可以这么看，x0~x4为图上五个点，xj-xi为i到j的距离这样就建立了一个有向图

显然x0到x4的路径有5,6,6,7四条最短的路为5

如若一个系统由n个变量和m个不等式组成，并且这m个不等式对应的系数矩阵中每一行有且仅有一个1和-1，其它的都为0，这样的系统称为差分约束( difference constraints )系统。

例如

如果还不清楚的话看看三角不等式：

给出三个不等式：

B - A <= c (1)

C - B <= a (2)

C - A <= b (3)

可以得到图

我们发现min{b, a+c}正好对应了A到C的最短路，而这三个不等式就是著名的三角不等式。将三个不等式推广到m个，变量推广到n个，就变成了n个点m条边的最短路问题了。

解的存在性

如果转化的的图中存在负权的回路先让就不会有解，因为负的回路会一直循环下去直到无穷小，这样就不可能有解

还有一种是两点之间不可达，这样最短路径为无穷大，此时有无限个解

版权声明：本文内容由互联网用户自发贡献，版权归作者所有，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至：yqgroup@service.aliyun.com 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。

用云栖社区APP，舒服~

原文链接