差分约束系统

求解差分约束系统，可以转化成求解图论的单源最短路径。观察${\displaystyle x_{j}-x_{i}\leq b_{k}}$ ，会发现它类似最短路中的三角不等式${\displaystyle d[v]\leq d[u]+w[u,v]}$ ，即${\displaystyle d[v]-d[u]\leq w[u,v]}$ 。因此，以每个变数${\displaystyle x_{i}}$ 为结点，对于约束条件${\displaystyle x_{j}-x_{i}\leq b_{k}}$ ，连接一条边${\displaystyle (i,j)}$ ，边权为${\displaystyle b_{k}}$ 。再增加一个原点${\displaystyle (s,s)}$ 与所有定点相连，边权均为0（在某些题目中可能需要根据实际情况进行改动）。对这个图以s为原点运行Bellman-Ford 算法（或SPFA），最终${\displaystyle \{d[i]\}}$ 即为一组可行解。
　　例如，考虑这样一个问题，寻找一个5维向量${\displaystyle x=(x_{i})}$ 以满足：

这一问题等价于找出未知量 ${\displaystyle x_{i},i\in \{1,2,3,4,5\}}$  ，满足下列8个差分约束条件：
　${\displaystyle x_{2}-x_{5}\leq 1}$ 
　${\displaystyle x_{1}-x_{2}\leq 0}$ 
　${\displaystyle x_{1}-x_{5}\leq -1}$ 
　${\displaystyle x_{3}-x_{1}\leq 5}$ 
　${\displaystyle x_{4}-x_{1}\leq 4}$ 
　${\displaystyle x_{4}-x_{3}\leq -1}$ 
　${\displaystyle x_{5}-x_{3}\leq -3}$ 
　${\displaystyle x_{5}-x_{4}\leq -3}$ 
该问题的一个解为${\displaystyle x=(-5,-3,0,-1,-4)}$ ，另一个解${\displaystyle y=(0,2,5,4,1)}$ ，这2个解是有联系的：${\displaystyle y}$ 中的每个元素比${\displaystyle x}$ 中相应的元素大5。

引理：设${\displaystyle x=(x_{1},x_{2},\cdots ,x_{n})}$ 是差分约束系统${\displaystyle Ax\leq b}$ 的一个解，d为任意常数，则${\displaystyle x+d=(x_{1}+d,x_{2}+d,\cdots ,x_{n}+d)}$ 也是该系统${\displaystyle 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 
        <无解>