本篇作为最短路系列的扩展，讲如何用图论知识对差分约束系统进行建模并求解。
1. 线性规划问题(Linear Program)
假设给定了一个m×n矩阵A，列向量x跟b，线性规划问题可以描述为在约束
下求解向量
使得目标函数
最大。其中未知量的数目为n，约束数目为m。
2.差分约束系统
所谓差分约束系统是线性规划的一种特殊情况，其中矩阵A的每一行分别有一个1跟-1其余元素为0。每个约束都形如
3.如何用最短路算法求解差分约束系统
首先构造约束图(Constraint Graph)
, V=\{v_{1},\dots,v_{n}\}\cup\{v_{0}\}, E=\{(v_{i},v_{j}):x_{j}-x{i}\leq b_{k}\}\cup\{(v_{0},v_{1}),\dots,{(v_{0},v_{n})}\})
其中边上的权值为
=b_{k}, w(v_{0},v_{i})=0,1 \leq i,j \leq n, 1 \leq k \leq m)
。
下面的定理说明，可以用Bellman-Ford算法来求解差分约束系统。
Theorem 1 设差分约束系统对应的约束图为G=(V,E)。若该图无负权的环，则差分约束系统的一个可行解为,\dots,\delta(v_{0},v_{n}))))
。若该图有由源可待的带负权的环，则该系统无可行解。
Proof 由于带权有向图最短路若有解，则解
符合三角不等式
\leq\delta(v_{0},v_{i})+w(v_{i},v_{j}))
，即+\delta(v_{0},v_{i}) \leq w(v_{i},v_{j})=b_{k})
。
因此x是该系统的一个可行解。
若约束图存在由源可达的带负权的环，不失一般性，设该回路为
,(v_{2},v_{3}),\dots,({v_{k-1},v_{k}),(v_{k},v_{1})\})
。
用反证法，若该图有解，则有)
满足
,x_{3}-x_{2}\leq w(v_{2},v_{3}),\dots,x_{k}-x_{k-1}\leq w(v_{k-1},v_{1}),x_{1}-x_{k}\leq w(v_{k},v_{1}))
将上面式子相加，左边为0，右边为该回路的权值小于0，得到0<0，矛盾。
下面给出一个程序。该程序输入变量数目、约束数目以及具体的约束。若有解则输出解，否则报错。
1 #include <iostream>
2 #define MAXN 200
3 #define INF 0xfffffff
4
5 using namespace std;
6
7 int list[MAXN][MAXN][2]; // 图的链接表存储
8 int deg[MAXN]; // 每个顶点的出度
9 int delta[MAXN]; // 最终存储最短路的距离
10 int trace[MAXN]; // trace[i]表示s到i的最短路i的前驱
11 int n,e; // 顶点数
12
13 void initialize_single_source()
14 {
15 int i;
16 for(i=1;i<=n;i++) delta[i]=INF;
17 trace[i]=-1;
18 }
19
20 void relax(int a,int b)
21 {
22 if(delta[list[a][b][0]]>delta[a]+list[a][b][1])
23 delta[list[a][b][0]]=delta[a]+list[a][b][1];
24 trace[list[a][b][0]]=a;
25 }
26
27 bool checkNegtiveCycle()
28 {
29 int i,j,k;
30 for(i=0;i<=n;i++)
31 {
32 for(j=0;j<deg[i];j++)
33 {
34 if(delta[list[i][j][0]]>delta[i]+list[i][j][1]) return false;
35 }
36 }
37 return true;
38 }
39
40 bool bellman_ford()
41 {
42 int i,j,k;
43 for(i=1;i<n;i++)
44 {
45 for(j=0;j<=n;j++)
46 {
47 for(k=0;k<deg[j];k++)
48 {
49 // 这里j跟k的含义不同：j是顶点编号，k是第j个顶点的第k条边
50 relax(j,k);
51 }
52 }
53 }
54 return checkNegtiveCycle();
55 }
56
57
58
59 void printSolution()
60 {
61 int i;
62 for(i=1;i<=n;i++) printf("x_{%d}=%d\n",i,delta[i]);
63 return;
64 }
65
66 int main()
67 {
68 int i,j,k,u,v,b;
69 // 输入未知量的个数
70 printf("Enter the number of unknowns:");
71 scanf("%d",&n);
72 // 输入约束数
73 printf("Enter the number of constrains:");
74 scanf("%d",&e);
75 // 输入约束
76 printf("Enter constrains in the format of xi(-)xj(<=)bk\n");
77 for(i=1;i<=e;i++) deg[i]=0;
78 for(i=1;i<=e;i++)
79 {
80 scanf("%d%d%d",&v,&u,&b);
81 list[u][deg[u]][0]=v;
82 list[u][deg[u]][1]=b;
83 deg[u]++;
84 }
85 // 添加新的顶点
86 deg[0]=n;
87 for(i=0;i<n;i++)
88 {
89 list[0][i][0]=i+1;
90 list[0][i][1]=0;
91 }
92 if(bellman_ford()){printSolution();}
93 else printf("no solution.\n");
94 return 1;
95 }