算法与数据结构 / 图论 · graph 算法合集 / 差分约束系统：不等式与最短路 待审核 7 / 7
difference-constraints · 差分约束

差分约束系统：不等式与最短路

排程、时序检查、版面压缩这几类问题，写成数学形式后常常长得一模一样：一堆变量，一堆只涉及两个变量之差的不等式。「养护要在浇筑之后至少 3 天」「触发沿到数据沿之间不少于一个 setup time」「两个图元的间距不小于 5」都是这个形状。这类系统有一个精确的图论对应物，求解它不需要线性规划，一遍 Bellman-Ford 就够。

本页是 graph 系列的一员，是 最短路径：拆解 Dijkstra 与 全源最短路：Floyd 与 Johnson 的一个应用侧出口。把原问题翻译成图、让现成算法的输出恰好是原问题的答案，这套路数在 建模与归约：把问题翻译成网络流 里有系统的展开；差分约束是其中最薄的一层翻译。

1 · 只关于差的不等式

定义 1.1（difference constraint system） 给定变量 x1,…,xnx_1, \dots, x_n 与一组形如 xj−xi≤cx_j - x_i \le c 的不等式，cc 为常数。求一组赋值使全部不等式同时成立，称为求该系统的一个 feasible solution。

形状上的限制比看起来宽。「BB 至少比 AA 晚 3」写成 xA−xB≤−3x_A - x_B \le -3；「DD 不得比 AA 晚 8 以上」写成 xD−xA≤8x_D - x_A \le 8。单个变量的绝对上下界看似不合形状，只要引入一个充当参考零点的普通变量 xRx_R，「AA 不早于 2」就是 xR−xA≤−2x_R - x_A \le -2，「AA 不晚于 6」就是 xA−xR≤6x_A - x_R \le 6。真正写不进来的只有涉及三个及以上变量的约束，或系数不为 ±1\pm 1 的项。

2 · 从不等式到边

单源最短路收敛时，每条边 i→ji \to j 都满足 dist[j]≤dist[i]+w\mathit{dist}[j] \le \mathit{dist}[i] + w，这是 relaxation 停下来的条件。把它移项写成 dist[j]−dist[i]≤w\mathit{dist}[j] - \mathit{dist}[i] \le w，与差分约束的形状逐字相同。翻译规则由此定死：

xj−xi≤c⟺一条 i→j 的边，权为 cx_j - x_i \le c \quad\Longleftrightarrow\quad \text{一条 } i \to j \text{ 的边，权为 } c

不等号右边的常数就是边权，被减数是边的终点。图建好之后还差一步：约束图未必连通，也没有天然的起点。补法是接一个超级源点 SS，向每个变量连一条 0 权边，一次遍历即可覆盖全部变量。

警示 · 超级源点不是白接的：S→vS \to v 那条 0 权边本身就是一条约束 xv−xS≤0x_v - x_S \le 0。把绝对下界直接挂到 SS 上（比如用 xS−xA≤−2x_S - x_A \le -2 表示「AA 不早于 2」）会与它首尾相接，凑成一个权为 −2-2 的环，系统当场被判无解。本页测试里留着这个错误建模作对照：同样的意图改挂到一个普通变量 RR 上就有解。绝对时刻的参考零点必须是变量，超级源点只负责让遍历有个出发点。

图 2-1 · 把约束逐条翻译成边。可切换实例，每帧加入一条不等式对应的边，末帧接上超级源点 SS。

3 · 可行解与 negative cycle

定理 3.1 设约束图按上述规则建成并接好超级源点。系统有 feasible solution 当且仅当图中无 negative cycle；此时 SS 到各点的最短距离 dist\mathit{dist} 就是一组解。

证明 无 negative cycle 时 Bellman-Ford 收敛，收敛意味着每条边都无法再松弛，即 dist[j]≤dist[i]+c\mathit{dist}[j] \le \mathit{dist}[i] + c 对每条边成立，逐条正是原不等式，取 xv=dist[v]x_v = \mathit{dist}[v] 即可。反过来，设环上依次是 xv1−xv0≤c1, …, xv0−xvm−1≤cmx_{v_1} - x_{v_0} \le c_1,\ \dots,\ x_{v_0} - x_{v_{m-1}} \le c_m，把这 mm 条相加，左边逐项相消得 0，右边是环的总权 WW，于是任何解都必须满足 0≤W0 \le W。W<0W < 0 时无解。∎

证明的后半段值得单独看一眼：negative cycle 不只是「算法报错」的信号，它是矛盾的一份可读的证据——环上那几条约束相加，就把「0≤0 \le 某个负数」这句荒谬的话摆了出来，无需再多解释。

Bellman-Ford 跑满 VV 轮的代价是 O(VE)O(VE)，即约束条数乘变量数。解不唯一：给所有变量同时加一个常数，每条差都不变，可行性也不变，所以解是一整族，只定到相差一个常数。

图 3-1 · 超级源点出发的 Bellman-Ford 单步执行。可切换实例，逐条边看 dist 收紧；无解的实例会在第 VV 轮仍能松弛处停下并报出 negative cycle。

4 · 排程实例

四道工序 AA、BB、CC、DD 依次进行，相邻两道各有最小间隔 3、2、1，另有一条「CC 不早于 AA 之后 4」的冗余约束，以及总工期不超过 8。五条不等式建成的图跑一遍 Bellman-Ford，把解平移到 xA=0x_A = 0，读数是 0、3、5、6。三条最小间隔约束的 slack 全为 0，它们串起来即决定工期的那条最长链；总工期约束还剩 2 的余量。

把总工期从 8 压到 4，其余一字不改，A→D→C→B→AA \to D \to C \to B \to A 四条边的权和变成 4−1−2−3=−24 - 1 - 2 - 3 = -2，系统无解。这个负环恰好也是最直白的解释：三段最小间隔加起来已经 6，容不下 4 的总工期。

图 4-1 · 解的时间轴与逐条核对。可切换实例并拖动整体平移量，观察每条差与 slack 均不随平移改变；无解的实例改为列出构成负环的那几条约束及其权和。

5 · 与全源最短路的接口

单条最短路给出一组解，全源最短路给出的是更强的东西：系统所蕴含的一切两两之差的界。uu 到 vv 的最短距离 δ(u,v)\delta(u, v) 恰是把沿途约束相加所能得到的最紧上界，即 xv−xu≤δ(u,v)x_v - x_u \le \delta(u, v) 在系统里成立，而任何更小的常数都不成立。一次 Floyd-Warshall 把这些界全算了出来。

上节那个排程实例即是例子：δ(A,B)=5\delta(A, B) = 5，δ(B,A)=−3\delta(B, A) = -3，两条合起来把 xB−xAx_B - x_A 夹在 [3,5][3, 5] 里。Bellman-Ford 给出的解取的是下端的 3，也就是「每道工序都尽早开工」的那一组。想要另一端的排法，把全部约束的方向与符号取反再跑一遍即可。

建议 · 这类系统在时序验证里叫 temporal constraint network [2]，在 VLSI 版图压缩里是标准工具 [4]：把每对图元的间距要求写成差分约束，最短路解出的就是各图元的最左合法位置。识别它的信号很简单——若所有约束都只关乎两个量之差，且系数是 ±1\pm 1，那就不必动用线性规划求解器。

6 · 参考文献

  1. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90.
  2. Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49(1–3), 61–95.
  3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Difference constraints and shortest paths. In Introduction to Algorithms (3rd ed.), section 24.4. MIT Press.
  4. Liao, Y.-Z., & Wong, C. K. (1983). An algorithm to compact a VLSI symbolic layout with mixed constraints. IEEE Transactions on Computer-Aided Design, 2(2), 62–69.