差分約束系統（System of Difference Constraints），是求解關於一組變數的特殊不等式組之方法。
如果一個系統由
個變量和
個約束條件組成，其中若每個約束條件形如 ![{\displaystyle x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25b8067ba717135111d64be72be8bff397a5e625)
，則稱其為差分約束系統。亦即，差分約束系統是求解關於一組變量的特殊不等式組的方法。
求解差分約束系統，可以轉化成求解圖論的單源最短路徑。觀察
，會發現它類似最短路中的三角不等式![{\displaystyle d[v]\leq d[u]+w[u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dfef47aca3ddb9a53376060bbd1c8700200af64)
，即![{\displaystyle d[v]-d[u]\leq w[u,v]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eafc2ccf342af267ed8e1bab417f4789e63ce613)
。因此，以每個變數
為結點，對於約束條件，連接一條邊
，邊權為
。再增加一個原點
與所有定點相連，邊權均為0（在某些題目中可能需要根據實際情況進行改動）。對這個圖以s為原點運行Bellman-Ford 算法（或SPFA），最終![{\displaystyle \{d[i]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b154f80b83c8c6f3e1a3dbdf35557a0a411105d)
即為一組可行解。
例如，考慮這樣一個問題，尋找一個5維向量
以滿足：
這一問題等價於找出未知量 
，滿足下列8個差分約束條件：
該問題的一個解為
，另一個解
，這2個解是有聯繫的：
中的每個元素比
中相應的元素大5。
引理：設
是差分約束系統
的一個解，d為任意常數，則
也是該系統的一個解。
Bellman-Ford 算法虛擬碼：
# 初始化
for each v in V do
d[v] ← ∞;
d[source] ← 0
# 松弛
for i =1,...,|V|-1 do
for each edge (u,v) in E do
d[v] ← min{d[v], d[u]+w(u,v)}
# 检查负环
for each edge (u, v) in E do
if d[v]> d[u] + w(u,v) then
<无解>
