547
差分約束轉最短路徑概述
差分約束係統
整理自：https://ycool.com/post/m2uybbf。
如果一個係統由n個變量和m個約束條件組成，其中每個約束條件都形如xj-xi<=bk，(i,j∈[1,n],k∈[1,m]),則稱其為差分約束係統(system of difference constraints)。亦即，差分約束係統是求解關於一組變量的特殊不等式組的方法。
求解差分約束係統，可以轉化成圖論的單源最短路徑（或最長路徑）問題。
比如有這樣一組不等式,不等式組(1)：
X1 - X2 <= 0
X1 - X5 <= -1
X2 - X5 <= 1
X3 - X1 <= 5
X4 - X1 <= 4
X4 - X3 <= -1
X5 - X3 <= -3
X5 - X4 <= -3
全都是兩個未知數的差小於等於某個常數（大於等於也可以，因為左右乘以-1就可以化成小於等於）。這樣的不等式組就稱作差分約束係統。
這個不等式組要麼無解，要麼就有無數組解。因為如果有一組解{X1, X2, ..., Xn}的話，那麼對於任何一個常數k，{X1 + k, X2 + k, ..., Xn + k}肯定也是一組解，因為任何兩個數同時加一個數之後，它們的差是不變的，那麼這個差分約束係統中的所有不等式都不會被破壞。
差分約束係統的解法利用到了單源最短路徑問題中的三角形不等式。即對於任何一條邊u -> v，都有：d(v) <= d(u) + w(u, v)，其中d(u)和d(v)是從源點分別到點u和點v的最短路徑的權值，w(u, v)是邊u -> v的權值。
顯然以上不等式就是d(v) - d(u) <= w(u, v)。這個形式正好和差分約束係統中的不等式形式相同。於是我們就可以把一個差分約束係統轉化成一張圖，每個未知數Xi對應圖中的一個頂點Vi，把所有不等式都化成圖中的一條邊。對於不等式Xi - Xj <= c，就可以化成邊Vj -> Vi，權值為c。最後，我們在這張圖上求一次單源最短路徑，這些三角形不等式就會全部都滿足了，因為它是最短路徑問題的基本性質嘛。
話說回來，所謂單源最短路徑，當然要有一個源點，然後再求這個源點到其他所有點的最短路徑。那麼源點在哪呢？我們不妨自已造一個X0=0。
添加n個不等式Xn - X0 <= 0，於是這個差分約束係統中就多出了下列不等式，不等式組(2)：
X1 - X0 <= 0
X2 - X0 <= 0
X3 - X0 <= 0
X4 - X0 <= 0
X5 - X0 <= 0
對於這5個不等式，也在圖中建出相應的邊。最後形成的圖如下：
圖中的每一條邊都代表差分約束係統中的一個不等式。現在以V0為源點，求單源最短路徑。最終得到的V0到Vn的最短路徑長度就是Xn的一個解啦。從圖中可以看到，這組解是{-5, -3, 0, -1, -4}。當然把每個數都加上10也是一組解：{5, 7, 10, 9, 6}。但是這組解隻滿足不等式組(1)，也就是原先的差分約束係統；而不滿足不等式組(2)，也就是我們後來加上去的那些不等式。當然這是無關緊要的，因為X0本來就是個局外人，是我們後來加上去的，滿不滿足與X0有關的不等式我們並不在乎。
也有可能出現無解的情況，也就是從源點到某一個頂點不存在最短路徑。也說是圖中存在負權的圈。
最後更新：2017-04-03 08:26:24