差分约束系统

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

如果一个系统由$n$个变量和$m$个约束条件组成，其中若每个约束条件形如 $x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])$，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。 　　

解法

求解差分約束系統，可以轉化成求解圖論的單源最短路徑。觀察$x_{j}-x_{i}\leq b_{k}$，會發現它類似最短路中的三角不等式$d[v]\leq d[u]+w[u,v]$，即$d[v]-d[u]\leq w[u,v]$。因此，以每個變數$x_{i}$為結點，對於約束條件$x_{j}-x_{i}\leq 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}\leq 1$
　$x_{1}-x_{2}\leq 0$
　$x_{1}-x_{5}\leq -1$
　$x_{3}-x_{1}\leq 5$
　$x_{4}-x_{1}\leq 4$
　$x_{4}-x_{3}\leq -1$
　$x_{5}-x_{3}\leq -3$
　$x_{5}-x_{4}\leq -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\leq b$的一个解，d为任意常数，则$x+d=(x_{1}+d,x_{2}+d,\cdots ,x_{n}+d)$也是该系统$Ax\leq b$的一个解。

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 
        <无解>