差分约束系统 （System of Difference Constraints），是求解關於一組變數的特殊不等式組 之方法。
如果一个系统由
n
{\displaystyle n}
m
{\displaystyle m}
x
j
−
x
i
≤
b
k
(
i
,
j
∈
[
1
,
n
]
,
k
∈
[
1
,
m
]
)
{\displaystyle x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}
求解差分約束系統，可以轉化成求解圖論 的單源最短路徑 。觀察
x
j
−
x
i
≤
b
k
{\displaystyle x_{j}-x_{i}\leq b_{k}}
d
[
v
]
≤
d
[
u
]
+
w
[
u
,
v
]
{\displaystyle d[v]\leq d[u]+w[u,v]}
d
[
v
]
−
d
[
u
]
≤
w
[
u
,
v
]
{\displaystyle d[v]-d[u]\leq w[u,v]}
x
i
{\displaystyle x_{i}}
x
j
−
x
i
≤
b
k
{\displaystyle x_{j}-x_{i}\leq b_{k}}
(
i
,
j
)
{\displaystyle (i,j)}
b
k
{\displaystyle b_{k}}
原點
(
s
,
s
)
{\displaystyle (s,s)}
定點 相連，邊權 均為0（在某些题目中可能需要根据实际情况进行改动）。對這個圖以s為原點運行Bellman-Ford 算法 （或SPFA ），最終
{
d
[
i
]
}
{\displaystyle \{d[i]\}}
x
=
(
x
i
)
{\displaystyle x=(x_{i})}
这一问题等价于找出未知量
x
i
,
i
∈
{
1
,
2
,
3
,
4
,
5
}
{\displaystyle x_{i},i\in \{1,2,3,4,5\}}
x
2
−
x
5
≤
1
{\displaystyle x_{2}-x_{5}\leq 1}
x
1
−
x
2
≤
0
{\displaystyle x_{1}-x_{2}\leq 0}
x
1
−
x
5
≤
−
1
{\displaystyle x_{1}-x_{5}\leq -1}
x
3
−
x
1
≤
5
{\displaystyle x_{3}-x_{1}\leq 5}
x
4
−
x
1
≤
4
{\displaystyle x_{4}-x_{1}\leq 4}
x
4
−
x
3
≤
−
1
{\displaystyle x_{4}-x_{3}\leq -1}
x
5
−
x
3
≤
−
3
{\displaystyle x_{5}-x_{3}\leq -3}
x
5
−
x
4
≤
−
3
{\displaystyle x_{5}-x_{4}\leq -3}
x
=
(
−
5
,
−
3
,
0
,
−
1
,
−
4
)
{\displaystyle x=(-5,-3,0,-1,-4)}
y
=
(
0
,
2
,
5
,
4
,
1
)
{\displaystyle y=(0,2,5,4,1)}
y
{\displaystyle y}
x
{\displaystyle x}
引理 ：设
x
=
(
x
1
,
x
2
,
⋯
,
x
n
)
{\displaystyle x=(x_{1},x_{2},\cdots ,x_{n})}
A
x
≤
b
{\displaystyle Ax\leq b}
x
+
d
=
(
x
1
+
d
,
x
2
+
d
,
⋯
,
x
n
+
d
)
{\displaystyle x+d=(x_{1}+d,x_{2}+d,\cdots ,x_{n}+d)}
A
x
≤
b
{\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
<无解>
![{\displaystyle x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25b8067ba717135111d64be72be8bff397a5e625)
![{\displaystyle d[v]\leq d[u]+w[u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dfef47aca3ddb9a53376060bbd1c8700200af64)
![{\displaystyle d[v]-d[u]\leq w[u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eafc2ccf342af267ed8e1bab417f4789e63ce613)
![{\displaystyle \{d[i]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b154f80b83c8c6f3e1a3dbdf35557a0a411105d)
