本篇作為最短路系列的擴展，講如何用圖論知識對差分約束系統進行建模并求解。
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 }