差分约束系统

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

如果一个系统由个变量和个约束条件组成，其中若每个约束条件形如 ，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

 解法 
求解差分約束系統，可以轉化成求解圖論的單源最短路徑。觀察，會發現它類似最短路中的三角不等式，即。因此，以每個變數為結點，對於約束條件，連接一條邊，邊權為。再增加一個原點與所有定點相連，邊權均為0（在某些题目中可能需要根据实际情况进行改动）。對這個圖以s為原點運行Bellman-Ford 算法（或SPFA），最終即為一組可行解。
　　例如，考虑这样一个问题，寻找一个5维向量以满足：

这一问题等价于找出未知量  ，满足下列8个差分约束条件：







　该问题的一个解为，另一个解，这2个解是有联系的：中的每个元素比中相应的元素大5。

引理：设是差分约束系统的一个解，d为任意常数，则也是该系统的一个解。

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

参考资料
Category:數學术语
分类:数学概念