差分约束系统

Template:Refimprove 差分约束系统（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 
        <无解>