本篇作為最短路系列的擴(kuò)展，講如何用圖論知識(shí)對(duì)差分約束系統(tǒng)進(jìn)行建模并求解。
1. 線(xiàn)性規(guī)劃問(wèn)題(Linear Program)
假設(shè)給定了一個(gè)m×n矩陣A，列向量x跟b，線(xiàn)性規(guī)劃問(wèn)題可以描述為在約束
下求解向量
使得目標(biāo)函數(shù)
最大。其中未知量的數(shù)目為n，約束數(shù)目為m。
2.差分約束系統(tǒng)
所謂差分約束系統(tǒng)是線(xiàn)性規(guī)劃的一種特殊情況，其中矩陣A的每一行分別有一個(gè)1跟-1其余元素為0。每個(gè)約束都形如
3.如何用最短路算法求解差分約束系統(tǒng)
首先構(gòu)造約束圖(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})}\})
其中邊上的權(quán)值為
=b_{k}, w(v_{0},v_{i})=0,1 \leq i,j \leq n, 1 \leq k \leq m)
。
下面的定理說(shuō)明，可以用Bellman-Ford算法來(lái)求解差分約束系統(tǒng)。
Theorem 1 設(shè)差分約束系統(tǒng)對(duì)應(yīng)的約束圖為G=(V,E)。若該圖無(wú)負(fù)權(quán)的環(huán)，則差分約束系統(tǒng)的一個(gè)可行解為,\dots,\delta(v_{0},v_{n}))))
。若該圖有由源可待的帶負(fù)權(quán)的環(huán)，則該系統(tǒng)無(wú)可行解。
Proof 由于帶權(quán)有向圖最短路若有解，則解
符合三角不等式
\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是該系統(tǒng)的一個(gè)可行解。
若約束圖存在由源可達(dá)的帶負(fù)權(quán)的環(huán)，不失一般性，設(shè)該回路為
,(v_{2},v_{3}),\dots,({v_{k-1},v_{k}),(v_{k},v_{1})\})
。
用反證法，若該圖有解，則有)
滿(mǎn)足
,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，右邊為該回路的權(quán)值小于0，得到0<0，矛盾。
下面給出一個(gè)程序。該程序輸入變量數(shù)目、約束數(shù)目以及具體的約束。若有解則輸出解，否則報(bào)錯(cuò)。
1 #include <iostream>
2 #define MAXN 200
3 #define INF 0xfffffff
4
5 using namespace std;
6
7 int list[MAXN][MAXN][2]; // 圖的鏈接表存儲(chǔ)
8 int deg[MAXN]; // 每個(gè)頂點(diǎn)的出度
9 int delta[MAXN]; // 最終存儲(chǔ)最短路的距離
10 int trace[MAXN]; // trace[i]表示s到i的最短路i的前驅(qū)
11 int n,e; // 頂點(diǎn)數(shù)
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是頂點(diǎn)編號(hào)，k是第j個(gè)頂點(diǎn)的第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 // 輸入未知量的個(gè)數(shù)
70 printf("Enter the number of unknowns:");
71 scanf("%d",&n);
72 // 輸入約束數(shù)
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 // 添加新的頂點(diǎn)
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 }