差分约束系统（System of Difference Constraints），是求解关于一组变数的特殊不等式组之方法。
如果一个系统由
个变量和
个约束条件组成，其中若每个约束条件形如 ![{\displaystyle x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25b8067ba717135111d64be72be8bff397a5e625)
，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成求解图论的单源最短路径。观察
，会发现它类似最短路中的三角不等式![{\displaystyle d[v]\leq d[u]+w[u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dfef47aca3ddb9a53376060bbd1c8700200af64)
，即![{\displaystyle d[v]-d[u]\leq w[u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eafc2ccf342af267ed8e1bab417f4789e63ce613)
。因此，以每个变数
为结点，对于约束条件，连接一条边
，边权为
。再增加一个原点
与所有定点相连，边权均为0（在某些题目中可能需要根据实际情况进行改动）。对这个图以s为原点运行Bellman-Ford 算法（或SPFA），最终![{\displaystyle \{d[i]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b154f80b83c8c6f3e1a3dbdf35557a0a411105d)
即为一组可行解。
例如，考虑这样一个问题，寻找一个5维向量
以满足：
这一问题等价于找出未知量 
，满足下列8个差分约束条件：
该问题的一个解为
，另一个解
，这2个解是有联系的：
中的每个元素比
中相应的元素大5。
引理：设
是差分约束系统
的一个解，d为任意常数，则
也是该系统的一个解。
Bellman-Ford 算法伪代码：
# 初始化
for each v in V do
d[v] ← ∞;
d[source] ← 0
# 松弛
for i =1,...,|V|-1 do
for each edge (u,v) in E do
d[v] ← min{d[v], d[u]+w(u,v)}
# 检查负环
for each edge (u, v) in E do
if d[v]> d[u] + w(u,v) then
<无解>
