差分约束系统

解法

求解差分约束系统，可以转化成图论的单源最短路径问题。观察，会发现它类似最短路中的三角不等式，即。因此，以每个变数为结点，对于约束条件，连接一条边，边权为。再增加一个原点与所有定点相连，边权均为0。对这个图以s为原点运行Bellman-ford算法（或SPFA算法），最终即为一组可行解。

　　例如，考虑这样一个问题，寻找一个5维向量以满足：
　　这一问题等价于找出未知量 ，满足下列8个差分约束条件：

　　　　

　　　　

　　　　

　　　　

　　　　

　　　　

　　　　

　　　　

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

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

bellman-ford算法伪代码：

# initialization
for each v in V do 
    d[v] ← ∞; 
d[source] ← 0
# Relaxation
for i =1,...,|V|-1 do
    for each edge (u,v) in E do
        d[v] ← min{d[v], d[u]+w(u,v)}
# Negative cycle checking
for each edge (u, v) in E do 
    if d[v]> d[u] + w(u,v) then 
        no solution