（本文假設(shè)讀者已經(jīng)有以下知識(shí)：最短路徑的基本性質(zhì)、Bellman-Ford算法。）
比如有這樣一組不等式：
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)
全都是兩個(gè)未知數(shù)的差小于等于某個(gè)常數(shù)（大于等于也可以，因?yàn)樽笥页艘?1就可以化成小于等于）。這樣的不等式組就稱作差分約束系統(tǒng)。
這個(gè)不等式組要么無解，要么就有無數(shù)組解。因?yàn)槿绻幸唤M解{X1, X2, ..., Xn}的話，那么對(duì)于任何一個(gè)常數(shù)k，{X1 + k, X2 + k, ..., Xn + k}肯定也是一組解，因?yàn)槿魏蝺蓚€(gè)數(shù)同時(shí)加一個(gè)數(shù)之后，它們的差是不變的，那么這個(gè)差分約束系統(tǒng)中的所有不等式都不會(huì)被破壞。
差分約束系統(tǒng)的解法利用到了單源最短路徑問題中的三角形不等式。即對(duì)于任何一條邊u -> v，都有：
d(v) <= d(u) + w(u, v)
其中d(u)和d(v)是從源點(diǎn)分別到點(diǎn)u和點(diǎn)v的最短路徑的權(quán)值，w(u, v)是邊u -> v的權(quán)值。
顯然以上不等式就是d(v) - d(u) <= w(u, v)。這個(gè)形式正好和差分約束系統(tǒng)中的不等式形式相同。于是我們就可以把一個(gè)差分約束系統(tǒng)轉(zhuǎn)化成一張圖，每個(gè)未知數(shù)Xi對(duì)應(yīng)圖中的一個(gè)頂點(diǎn)Vi，把所有不等式都化成圖中的一條邊。對(duì)于不等式Xi - Xj <= c，把它化成三角形不等式：Xi <= Xj + c，就可以化成邊Vj -> Vi，權(quán)值為c。最后，我們?cè)谶@張圖上求一次單源最短路徑，這些三角形不等式就會(huì)全部都滿足了，因?yàn)樗亲疃搪窂絾栴}的基本性質(zhì)嘛。
話說回來，所謂單源最短路徑，當(dāng)然要有一個(gè)源點(diǎn)，然后再求這個(gè)源點(diǎn)到其他所有點(diǎn)的最短路徑。那么源點(diǎn)在哪呢？我們不妨自已造一個(gè)。以上面的不等式組為例，我們就再新加一個(gè)未知數(shù)X0。然后對(duì)原來的每個(gè)未知數(shù)都對(duì)X0隨便加一個(gè)不等式（這個(gè)不等式當(dāng)然也要和其它不等式形式相同，即兩個(gè)未知數(shù)的差小于等于某個(gè)常數(shù)）。我們索性就全都寫成Xn - X0 <= 0，于是這個(gè)差分約束系統(tǒng)中就多出了下列不等式：
X1 - X0 <= 0
X2 - X0 <= 0
X3 - X0 <= 0
X4 - X0 <= 0
X5 - X0 <= 0
不等式組(2)
對(duì)于這5個(gè)不等式，也在圖中建出相應(yīng)的邊。最后形成的圖如下：
圖1
圖中的每一條邊都代表差分約束系統(tǒng)中的一個(gè)不等式。現(xiàn)在以V0為源點(diǎn)，求單源最短路徑。最終得到的V0到Vn的最短路徑長度就是Xn的一個(gè)解啦。從圖1中可以看到，這組解是{-5, -3, 0, -1, -4}。當(dāng)然把每個(gè)數(shù)都加上10也是一組解：{5, 7, 10, 9, 6}。但是這組解只滿足不等式組(1)，也就是原先的差分約束系統(tǒng)；而不滿足不等式組(2)，也就是我們后來加上去的那些不等式。當(dāng)然這是無關(guān)緊要的，因?yàn)閄0本來就是個(gè)局外人，是我們后來加上去的，滿不滿足與X0有關(guān)的不等式我們并不在乎。
也有可能出現(xiàn)無解的情況，也就是從源點(diǎn)到某一個(gè)頂點(diǎn)不存在最短路徑。也說是圖中存在負(fù)權(quán)的圈。這一點(diǎn)我就不展開了，請(qǐng)自已參看最短路徑問題的一些基本定理。
其實(shí)，對(duì)于圖1來說，它代表的一組解其實(shí)是{0, -5, -3, 0, -1, -4}，也就是說X0的值也在這組解當(dāng)中。但是X0的值是無可爭(zhēng)議的，既然是以它作為源點(diǎn)求的最短路徑，那么源點(diǎn)到它的最短路徑長度當(dāng)然是0了。因此，實(shí)際上我們解的這個(gè)差分約束系統(tǒng)無形中又存在一個(gè)條件：
X0 = 0
也就是說在不等式組(1)、(2)組成的差分約束系統(tǒng)的前提下，再把其中的一個(gè)未知數(shù)的值定死。這樣的情況在實(shí)際問題中是很常見的。比如一個(gè)問題表面上給出了一些不等式，但還隱藏著一些不等式，比如所有未知數(shù)都大于等于0或者都不能超過某個(gè)上限之類的。比如上面的不等式組(2)就規(guī)定了所有未知數(shù)都小于等于0。
對(duì)于這種有一個(gè)未知數(shù)定死的差分約束系統(tǒng)，還有一個(gè)有趣的性質(zhì)，那就是通過最短路徑算法求出來的一組解當(dāng)中，所有未知數(shù)都達(dá)到最大值。下面我來粗略地證明一下，這個(gè)證明過程要結(jié)合Bellman-Ford算法的過程來說明。
假設(shè)X0是定死的；X1到Xn在滿足所有約束的情況下可以取到的最大值分別為M1、M2、……、Mn（當(dāng)然我們不知道它們的值是多少）；解出的源點(diǎn)到每個(gè)點(diǎn)的最短路徑長度為D1、D2、……、Dn。
基本的Bellman-Ford算法是一開始初始化D1到Dn都是無窮大。然后檢查所有的邊對(duì)應(yīng)的三角形不等式，一但發(fā)現(xiàn)有不滿足三角形不等式的情況，則更新對(duì)應(yīng)的D值。最后求出來的D1到Dn就是源點(diǎn)到每個(gè)點(diǎn)的最短路徑長度。
如果我們一開始初始化D1、D2、……、Dn的值分別為M1、M2、……、Mn，則由于它們?nèi)紳M足三角形不等式（我們剛才已經(jīng)假設(shè)M1到Mn是一組合法的解），則Bellman-Ford算法不會(huì)再更新任合D值，則最后得出的解就是M1、M2、……、Mn。
好了，現(xiàn)在知道了，初始值無窮大時(shí)，算出來的是D1、D2、……、Dn；初始值比較小的時(shí)候算出來的則是M1、M2、……、Mn。大家用的是同樣的算法，同樣的計(jì)算過程，總不可能初始值大的算出來的結(jié)果反而小吧。所以D1、D2、……、Dn就是M1、M2、……、Mn。
那么如果在一個(gè)未知數(shù)定死的情況下，要求其它所有未知數(shù)的最小值怎么辦？只要反過來求最長路徑就可以了。最長路徑中的三角不等式與最短路徑中相反：
d(v) >= d(u) + w(u, v)
也就是 d(v) - d(u) >= w(u, v)
所以建圖的時(shí)候要先把所有不等式化成大于等于號(hào)的。其它各種過程，包括證明為什么解出的是最小值的證法，都完全類似。
用到差分約束系統(tǒng)的題目有ZJU 2770