差分约束系统
- 差分约束系统（spfa）
- 1、概述
- 2、过程模拟
- 3、推理
差分约束系统（spfa）
1、概述
x j − x i ≤ w k x_j-x_i\le w_k xj−xi≤wk转换为： x j ≤ w k + x i x_j\le w_k+x_i xj≤wk+xi
在松弛操作中：
∙
\bullet
∙如果
d
(
v
j
)
>
d
(
v
i
)
+
w
(
e
i
,
j
)
d(v_j)>d(v_i)+w(e_{i,j})
d(vj)>d(vi)+w(ei,j)，则更新
d
(
v
j
)
=
d
(
v
i
)
+
w
(
e
i
,
j
)
d(v_j)=d(v_i)+w(e_{i,j})
d(vj)=d(vi)+w(ei,j)；
∙ \bullet ∙如果 d ( v j ) ≤ d ( v i ) + w ( e i , j ) d(v_j)\le d(v_i)+w(e_{i,j}) d(vj)≤d(vi)+w(ei,j)，则无需更新，这是最终目的。
差分约束系统转化成图的形式，再通过求解最短路径的方法（即通过松弛操作）就能够实现差分系统的求解。
2、过程模拟
由上述所知， x j − x i ≤ w k x_j-x_i\le w_k xj−xi≤wk就相当于节点 v i v_i vi到节点 v j v_j vj的边权距离为 w k w_k wk
x
2
−
x
1
≤
−
2
x_2-x_1\le -2
x2−x1≤−2
x
1
−
x
3
≤
−
1
x_1-x_3\le -1
x1−x3≤−1
x
2
−
x
3
≤
4
x_2-x_3\le 4
x2−x3≤4
x
4
−
x
2
≤
5
x_4-x_2\le 5
x4−x2≤5
x
3
−
x
4
≤
2
x_3-x_4\le 2
x3−x4≤2
x
4
−
x
3
≤
−
2
x_4-x_3\le -2
x4−x3≤−2
x
5
−
x
4
≤
3
x_5-x_4\le 3
x5−x4≤3
x
5
−
x
3
≤
−
3
x_5-x_3\le -3
x5−x3≤−3
⇓
\Darr
⇓
⇓
\Darr
⇓
以
v
1
v_1
v1作为源节点
顶点的
d
d
d值为：
(
0
,
−
2
,
5
,
3
,
2
)
(0,-2,5,3,2)
(0,−2,5,3,2)
由于
d
(
v
2
)
−
d
(
v
1
)
≤
w
1
,
2
d(v_2)-d(v_1)\le w_{1,2}
d(v2)−d(v1)≤w1,2，所以
−
2
−
0
≤
−
2
-2-0\le -2
−2−0≤−2成立，也可得
x
2
=
−
2
x_2=-2
x2=−2，
x
1
=
0
x_1=0
x1=0
⇓
\Darr
⇓
以
v
3
v_3
v3作为源节点
顶点的
d
d
d值为：
(
−
1
,
−
3
,
0
,
−
2
,
−
3
)
(-1,-3,0,-2,-3)
(−1,−3,0,−2,−3)
⇓
\Darr
⇓
以
v
0
v_0
v0作为源节点
顶点的
d
d
d值为：
(
−
1
,
−
3
,
0
,
−
2
,
−
3
)
(-1,-3,0,-2,-3)
(−1,−3,0,−2,−3)
以 v 2 v_2 v2作为源节点，顶点的 d d d值为： ( 4 , 0 , 7 , 5 , 8 ) (4,0,7,5,8) (4,0,7,5,8)
以 v 4 v_4 v4作为源节点，顶点的 d d d值为： ( 1 , − 1 , 2 , 0 , − 1 ) (1,-1,2,0,-1) (1,−1,2,0,−1)
总计如下：
以
v
1
v_1
v1作为源节点，
x
v
1
=
(
0
,
−
2
,
5
,
3
,
2
)
x_{v_1}=(0,-2,5,3,2)
xv1=(0,−2,5,3,2)
以
v
2
v_2
v2作为源节点，
x
v
2
=
(
4
,
0
,
7
,
5
,
8
)
x_{v_2}=(4,0,7,5,8)
xv2=(4,0,7,5,8)
以
v
3
v_3
v3作为源节点，
x
v
3
=
(
−
1
,
−
3
,
0
,
−
2
,
−
3
)
x_{v_3}=(-1,-3,0,-2,-3)
xv3=(−1,−3,0,−2,−3)
以
v
4
v_4
v4作为源节点，
x
v
4
=
(
1
,
−
1
,
2
,
0
,
−
1
)
x_{v_4}=(1,-1,2,0,-1)
xv4=(1,−1,2,0,−1)
其中， x v 2 x_{v_2} xv2和 x v 1 x_{v_1} xv1、 x v 3 x_{v_3} xv3都没有关联性，但 x v 4 = x v 3 + 2 x_{v_4}=x_{v_3}+2 xv4=xv3+2。
3、推理
推理1：
对于差分约束系统的任意一个解
x
=
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
x=(x_1,x_2,x_3,x_4,x_5)
x=(x1,x2,x3,x4,x5)，以及任意一个常数
k
k
k，则
x
′
=
x
+
k
=
(
x
1
+
k
,
x
2
+
k
,
x
3
+
k
,
x
4
+
k
,
x
5
+
k
)
x'=x+k=(x_1+k,x_2+k,x_3+k,x_4+k,x_5+k)
x′=x+k=(x1+k,x2+k,x3+k,x4+k,x5+k)依然是差分约束系统的解。
推理2：
以差分约束系统对应图的所以节点为源节点，得出所有的独立解（这些解之间没有关联性），差分约束系统的所有解包含：1、所有的独立解，2、这些独立解和任意一个常数的和。
推理3：
如果差分约束系统对应图存在负环（也就是不存在最短路径），则差分约束系统不存在可行解。
