差分约束系统（System of Difference Constraints），是求解關於一組變數的特殊不等式組之方法。

如果一个系统由 n 个变量和 m 个约束条件组成，其中若每个约束条件形如 x_j-x_i \le b_k(i,j \in [1,n], k \in [1,m]) ，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
　　
解法
求解差分約束系統，可以轉化成求解圖論的單源最短路徑。觀察 x_j-x_i \le b_k ，會發現它類似最短路中的三角不等式 d[v] \le d[u]+w[u,v] ，即 d[v]-d[u] \le w[u,v] 。因此，以每個變數 x_i 為結點，對於約束條件 x_j-x_i \le b_k ，連接一條邊 (i,j) ，邊權為 b_k 。再增加一個原點 (s, s) 與所有定點相連，邊權均為0（在某些题目中可能需要根据实际情况进行改动）。對這個圖以s為原點運行Bellman-Ford 算法（或SPFA），最終 \{d[i]\} 即為一組可行解。

　　例如，考虑这样一个问题，寻找一个5维向量 x=(x_i) 以满足：

这一问题等价于找出未知量 x_i, i \in \{1,2,3,4,5\} ，满足下列8个差分约束条件：

　 x_2-x_5 \le 1

　 x_1-x_2 \le 0

　 x_1-x_5 \le -1

　 x_3-x_1 \le 5

　 x_4-x_1 \le 4

　 x_4-x_3 \le -1

　 x_5-x_3 \le -3

　 x_5-x_4 \le -3
该问题的一个解为 x=(-5,-3,0,-1,-4) ，另一个解 y=(0,2,5,4,1) ，这2个解是有联系的： y 中的每个元素比 x 中相应的元素大5。

引理：设 x=(x_1,x_2,\cdots,x_n) 是差分约束系统 Ax \le b 的一个解，d为任意常数，则 x+d=(x_1+d,x_2+d,\cdots,x_n+d) 也是该系统 Ax \le b 的一个解。

Bellman-Ford 算法-{zh-hans:伪代码; zh-hant:虛擬碼; zh-cn:伪代码; zh-tw:虛擬碼; zh-hk:虛擬碼; zh-sg:伪代码}-：

初始化

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

参考资料