在本书的29章会介绍通用的线性规划问题，即在满足一组线性不等式的条件下优化一个线性函数。而本节中所介绍的线性规划则是一种特例，可被归类在单源最短路径问题中。并可调用Bellman_Ford算法解决该问题。
在此之前，先介绍何为线性规划。
线性规划: 在一般的线性规划中，对于不等式 Ax ≤ b，我们给定的常量有：
A ： 一个 m×n 的矩阵； b：一个m维向量； c：一个n为向量。
其中 k 维向量即代表 k 行 1 列的矩阵，即书上的列向量。
（笔者注：对于不了解矩阵的同学，我们可以当作一个由 m 个不等式， n 个未知量组成的不等式组，其中，矩阵A为方程组的系数，b为位于右侧的常量数，若皆为0，则为齐次线性方程组，否则为非齐次。） 在某些时刻，我们仅需要找到一个满足不等式组的解，或者，判定解存在与否。以下将根据此进行讨论。
差分约束系统：
（笔者注：关于差分的概念，可以在百度上寻得，俺之前也不清楚相关概念，不过相应的百度百科给出了详细的解释：差分（difference）又名差分函数或差分运算，差分的结果反映了离散量之间的一种变化，是研究离散数学的一种工具。它将原函数f(x) 映射到f(x+a)-f(x+b) ，其中映射的这个过程就是差分。差分运算，相应于微分运算，是微积分中重要的一个概念。总而言之，差分对应离散，微分对应连续。
同时，关于约束：即不等式所限定的所有变量的取值范围的交集）
在一个差分约束系统中，线性规划矩阵A的每一行仅包括一个 1 和 一个 -1，其余皆为0，因此，由Ax ≤ b所给出的约束条件变为m个涉及n个变量的差额限制条件。其中，根据由矩阵等效而来的单个不等式为 ，其中1 ≤ i, j ≤ n，i != j（即不同的变量），同时有 1 ≤ k ≤ m（即对应的不等式）。
关于该不等式组的解，理论上可能有多个，然而这多个解存在关系，这其中的关系将在下面给出：
引理 8：设向量 x = (x1, x2, ……, xn)为差分系统 Ax ≤ b 的一个解，设 d 为任意常数，则 x + d = (x1 + d, x2 + d, ……, xn + d)也是该差分系统的一个解。
证明：显然，根据单个不等式中，可以判断出，，它仍然符合条件。
约束图：现在将进入到图论的领域。
在一个 Ax ≤ b 的差分约束系统中，我们将 m × n 的线性规划矩阵看作一张由 n 个结点和 m 条边构成的图的关联矩阵的转置。
在此补充说明一下关联矩阵的定义：
关联矩阵：有向无环图 G = （V， E），是一个满足以下条件的|V| × |E|的矩阵B = (bij)。
1、若边 j 从结点 i 发出，则 bij = -1；
2、若边 j 进入结点 i ，则 bij = 1;
3、其他情况下， bij = 0。
（笔者注：可能会有人感到奇怪：为什么发出是负而接收是正，我所理解的是，若我们把边当作饼干，那么从某个结点发出边，那么它就把自己的饼干给了别人，多少则取决于边的权重。从而倘若从某个顶点发出了边，它就损失了饼干，因此自然是负的，而得到饼干的结点则为正。）
我们将关联矩阵的定义套入到目前我们所处的场景：
首先，我们要明确：我们是从线性规划矩阵套到图中，因此我们不要先去想象图。
好，之后我们回到线性规划矩阵：在前文中，对于一个 m × n 的矩阵，我们提到它的每行都满足：每行都有一个 -1 和 1，之后，经过转置后，我们得到的矩阵为一个 n × m 的矩阵，同时它现在满足的是：每列都有一个 - 1 和 1.
现在，我们再回到对于图G =(V, E)所产生的|V| × |E|的关联矩阵：思考一个很重要的点：每列很显然，只能连接两个顶点u, v，同时，它们之间的边（若有的话）(u, v)，是从u而出，v而进，那么在矩阵中，该边在第 u 行为 -1， 在第 v 行为 1。那么很显然，我们就察觉到了其中每列（即每条边）与上述给出的约束条件的相似之处：每列都有一个 -1 和 1.
之后，我们便可以完成由上述的差分约束系统的线性规划矩阵到图的关联矩阵的转换：我们根据它的列数对应图G = （V， E）中的V，而根据它每行中的 -1 和 1 来连接顶点形成边，同时每行右边的bk则组成所对应边上的权值。因此就形成了一个图G——显然我们不必循规蹈矩得进行转换再对应。
现在，我们将这个过程形式化，给定差分约束系统 Ax ≤ b，其对应的约束图是一个带权重的有向图 G=（V，E），其中：
V = {V0,，V1，……，Vn}——即每个变量 x ，以及额外的结点V0，它连接所有的顶点，是为了保证我们的算法能够抵达所有的顶点。
E = {(Vi, Vj)：xj - xi ≤ bk是一个约束条件}∪{(V0, V1), (V0, V2), (V0, V3)……(V0, Vn)}，其中由V0到达其他顶点的边上的权值为0.
下面的定理将说明可以通过在对应的约束图中寻找最短路径权重来找到一个差分约束系统的解。
定理9：给定差分约束系统 Ax ≤ b，设G = （V，E）是该差分约束系统所对应的约束图，若G不包含权重为负值的环路，则
x = (δ(V0, V1)， δ(V0, V2)，……，δ(V0 ,Vn))是该系统的一个可行解。若包含权重为负值的环路，则该系统没有可行解。
证明：先证明不包含权重为负值的环路的情况：考虑任意一条边(Vi, Vj)∈E，则δ(V0, Vj) ≤ δ(V0, Vi) + w(Vi, Vj)，即 δ(V0, Vj) - δ(V0, Vi) ≤ w(Vi, Vj)，若设 xi = δ(V0, Vi), xj = δ(V0, Vj)，则对应边(Vi, Vj)的差分约束条件 xj - xi ≤ w(vi, vj) = bij。
之后证明包含权重为负值的环路的情况：同样我们设环路 c = <V1, V2, ……, Vk>，其中V1 = Vk，也应该注意到V0不可能包含在内——它并没有进入的边。那么其对于的差分约束条件组：
………………
同时注意到在不等式相加后，左边和为0，同时右边为环路的总权重，那么应大于等于0，与假设相悖。从而得证。
求解差分约束系统
显然，我们可通过运行Bellman_Ford算法对其进行求解。
同时，由于算法本身分别根据结点和边的数目进行循环，因此消耗时间O（VE），在差分约束系统中，V = n + 1，E = n + m（其中V中的1代表额外的V0，同时n代表由V0发出的边），则其时间消耗为O(nm)。
