差分約束系統

所謂的差分約束系統，實際上指一系列的表達式，滿足形如 xi - xj <= a求解實際上轉化成了圖論里的一個等價問題，最短路問題，實際上巧妙的利用了最短路具有的性質 di - dj <= w(j,i)如果這樣的最短路求成來了，他們的值便可以直接作為xi xj的一組可行解。

基本定義

如果一個系統由n個變數和m個約束條件組成，其中每個約束條件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),則其為差分約束系統(system of difference constraints)。亦即，差分約束系統是關於一組變數的特殊不等式組。求解差分約束系統，可以轉化成圖論的單源最短路徑問題。

主要原理

觀察xj-xi<=bk，會發現它類似最短路中的三角不等式d[v]<=d[u]+w[u,v]，即d[v]-d[u]<=w[u,v]。因此，以每個變數xi為結點，對於約束條件xj-xi<=bk，連線一條邊(i,j)，邊權為bk。我們再增加一個源點s,s與所有定點相連，邊權均為0。對這個圖，以s為源點運行bellman-ford算法，最終{d}即為一組可行解。