算法（H）笔记——最短路

最短路

算法选择

• 有负权边、无环：用 DAG 最短路径，时间复杂度 \(O(V+E)\)。
• 非负权边、有环：用 Dijkstra。
• 有负权边、又有环：一般用 Bellman-Ford，时间复杂度 \(O(VE)\)。

24.0 最优子结构

引理24.1：最短路的子路径一定最短。

\[ \delta(s,u)+w(u,v)= \delta(s,v) \qquad \]

定义：最短路不包含环路，且长度最多为 \(|V|-1\)。

初始化：INITIALIZE-SINGLE-SOURCE(G, s)

INITIALIZE-SINGLE-SOURCE(G, s)
1  for each vertex v in G.V
2      v.d = infinity
3      v.pi = NIL
4  s.d = 0

含义：先把所有结点的当前估计距离设为无穷，把前驱设为 NIL，再把源点 \(s\) 的当前估计距离设为 \(0\)。

松弛：RELAX(u, v, w)

RELAX(u, v, w)
1  if v.d > u.d + w(u, v)
2      v.d = u.d + w(u, v)
3      v.pi = u

含义：如果从 \(s\) 到 \(u\)，再经过边 \((u,v)\) 到 \(v\) 的路径更短，就更新 \(v.d\)，并把 \(v\) 的前驱设为 \(u\)。

引理 24.13 设 \(G=(V,E)\) 为一个带权重的有向图，权重函数为 \(w:E\to R\)，并且边 \((u,v)\in E\)。那么在对边 \((u,v)\) 进行松弛操作 RELAX(u, v, w) 后，有 \(v.d\le u.d+w(u,v)\)。

证明：如果在对边 \((u,v)\) 进行松弛操作前，有 \(v.d>u.d+w(u,v)\)，则在松弛操作后，有 \(v.d=u.d+w(u,v)\)。如果在松弛操作前有 \(v.d\le u.d+w(u,v)\)，则松弛操作不会改变 \(u.d\) 或 \(v.d\) 的取值，因此在松弛操作后仍然有 \(v.d\le u.d+w(u,v)\)。

最短路径树

一棵根结点为 \(s\) 的最短路径树是一个有向子图：

\[ G'=(V',E') \]

其中 \(V'\subseteq V\)，\(E'\subseteq E\)，满足：

1. \(V'\) 是图 \(G\) 中从源结点 \(s\) 可以到达的所有结点的集合。
2. \(G'\) 形成一棵根结点为 \(s\) 的树。
3. 对于所有结点 \(v\in V'\)，图 \(G'\) 中从结点 \(s\) 到结点 \(v\) 的唯一简单路径，是图 \(G\) 中从结点 \(s\) 到结点 \(v\) 的一条最短路径。

六大性质

1. 三角不等式性质——针对算法结束后的 \(\delta\)

对于任意边 \((u,v)\in E\)，有：

\[ \delta(s,v) \leq \delta(s,u)+w(u,v) \]

由最短路定义，易证。

2. 上界性质

对于所有结点 \(v\in V\)，总有：

\[ v.d \geq \delta(s,v) \]

一旦 \(v.d\) 的取值达到 \(\delta(s,v)\)，其值将不再发生变化。

归纳法：

• 初始：其他点无穷，\(s\) 为 \(0\)，相等。
• 归纳：

考虑对边 \((u,v)\) 的松弛操作。根据归纳假设，在松弛之前，对于所有的结点 \(x\in V\)，\(x.d\ge \delta(s,x)\)。而在对边 \((u,v)\) 进行松弛的过程中，唯一可能发生改变的 \(d\) 值只有 \(v.d\)。如果该值发生变化，则有

\[ v.d = u.d + w(u,v) \]

根据归纳假设：

\[ v.d \ge \delta(s,u) + w(u,v) \]

根据三角不等式：

\[ v.d \ge \delta(s,v) \]

不变：取到下界后无法再减小，松弛不会增加，所以不增加。

3. 非路径性质

如果从结点 \(s\) 到结点 \(v\) 之间不存在路径，则总有：

\[ v.d=\delta(s,v)=\infty \]

上界性质：\(v=\delta=+\infty\)。

4. 收敛性质

如果从 \(s\) 到 \(u\)，再经过边 \((u,v)\) 到达 \(v\) 的这条路径是图 \(G\) 中的一条最短路径，并且在对边 \((u,v)\) 进行松弛前，有：

\[ u.d=\delta(s,u) \]

那么在之后的所有时间都有：

\[ v.d=\delta(s,v) \]

放缩性质 + 最短路的子路径也是最短路：

证明：根据上界性质，如果在对边 \((u,v)\) 进行松弛前的某个时刻有 \(u.d=\delta(s,u)\)，则该等式在松弛操作后仍然成立。特别地，在对边 \((u,v)\) 进行松弛后，有

\[ v.d \le u.d + w(u,v) \]

根据引理 24.13 和假设 \(u.d=\delta(s,u)\)：

\[ v.d \le \delta(s,u) + w(u,v) \]

根据引理 24.1：

\[ v.d \le \delta(s,v) \]

5. 路径松弛性质

如果 \(p=\langle v_0,v_1,\dots,v_k\rangle\) 是从源点 \(s=v_0\) 到结点 \(v_k\) 的一条最短路径，并且我们按照路径上的边的顺序进行松弛：

\[ (v_0,v_1),(v_1,v_2),\dots,(v_{k-1},v_k) \]

则最终有：

\[ v_k.d=\delta(s,v_k) \]

该性质与其他松弛操作无关，即使这些松弛操作与路径 \(p\) 上边的松弛交错进行也成立。

归纳法 + 收敛性质。

证明 我们使用归纳法来证明该引理。我们的归纳假设是在最短路径 \(p\) 的第 \(i\) 条边被松弛之后，有 \(v_i.d=\delta(s,v_i)\)。对于基础步 \(i=0\) 的情况，即在对路径 \(p\) 的任何一条边进行松弛操作之前，我们从初始化算法可以得出 \(v_0.d=s.d=0=\delta(s,s)\)。根据上界性质，\(s.d\) 的取值在此初始化之后将不再发生变化。

对于归纳步，假定 \(v_{i-1}.d=\delta(s,v_{i-1})\)。我们来考虑在对边 \((v_{i-1},v_i)\) 进行松弛操作时将发生的事情。根据收敛性质，在对该条边进行松弛之后，我们有 \(v_i.d=\delta(s,v_i)\)，并且该等式在此之后一直保持成立。

6.0 引理

引理 24.16 设 \(G=(V,E)\) 为一个带权重的有向图，权重函数为 \(w:E\to R\)。设 \(s\in V\) 为某个源结点，假定图 \(G\) 不包含从源结点 \(s\) 可以到达的权重为负值的环路，则在图 \(G\) 中 INITIALIZE-SINGLE-SOURCE(G, s) 算法进行初始化之后，前驱子图 \(G_\pi\) 形成根结点为源结点 \(s\) 的有根树，并且任何对图 \(G\) 的边进行的任意松弛操作都将维持该性质不变。

如果不包含从 \(s\) 可达的负环路，则在 INIT 之后，前驱子图 \(G_\pi\) 形成根节点为 \(s\) 的有根树，且任意松弛操作都将维持这一性质不变。

证明：

1. \(G_\pi\) 是无环路的。

​ 假设创建环路 \(c\)，因为 \(c\) 上每一个点都有非空 \(\pi\) 值，因此取得有限的最短路估计值，由上界性质，\(c\) 上的每一个节点有一个有限的最短路径权重，因此从 \(s\) 可达。

​ 下证 \(c\) 是负环路：

在调用 RELAX(v_{k-1}, v_k, w) 操作之前，我们有

\[ v_i.d \ge v_{i-1}.d+w(v_{i-1},v_i),\quad i=1,2,\dots,k-1 \]

记作式(24.12)。

因为 \(v_k .\pi\) 在该调用中发生改变，所以在此之前有

\[ v_k.d > v_{k-1}.d+w(v_{k-1},v_k) \]

​ 求和，左右抵消，得负环路，与假设矛盾。因此不存在环路。

2. 证明任意 \(v\in V_\pi\)，在 \(G_\pi\) 中存在唯一一条从 \(s\) 到 \(v\) 的简单路径：

   1. 首先证明路径存在。因为 \(V_\pi\) 中的节点全都有非空 \(\pi\) 值，由归纳法知 \(s\) 到 \(V_\pi\) 中的每个节点都有一条路径。

   2. 反证有两条路径。

假定 \(G_\pi\) 中包含两条从源结点 \(s\) 到结点 \(v\) 的简单路径，设其分别为 \(p_1: s \leadsto u \leadsto x \rightarrow z \leadsto v\) 和 \(p_2: s \leadsto u \leadsto y \rightarrow z \leadsto v\)。这里 \(x\ne y\)（不过，结点 \(u\) 可以是 \(s\)，结点 \(z\) 可以是 \(v\)），如图 24-9 所示。但是，\(z.\pi=x\) 并且 \(z.\pi=y\)，这将得出矛盾的结论 \(x=y\)。

6. 前驱子图性质

对于所有结点 \(v\in V\)，一旦有 \(v.d=\delta(s,v)\)，则前驱子图是一棵根结点为 \(s\) 的最短路径树。

• \(V_\pi\) 是从 \(s\) 可达节点的集合：
  • \(v\) 是从 \(s\) 可达的 \(\iff\) \(\delta\) 是有限值 \(\iff\) \(d\) 值有限 \(\iff\) \(v.\pi\) 非空（除了 \(s\) 以外，而 \(s\) 显然有限），而这些点就是 \(V_\pi\) 中的节点。
• 由引理直接得：是一棵以 \(s\) 为根节点的树。
• 任意 \(v\in V_\pi\)，\(G_\pi\) 中的唯一简单路径就是 \(G\) 中的一条最短路径：

\(s \leadsto v\) 也是图 \(G\) 中从 \(s\) 到 \(v\) 的一条最短路径。设 \(G_\pi\) 中的唯一简单路径 \(p=\langle v_0,v_1,\dots,v_k\rangle\)，这里 \(v_0=s\)，\(v_k=v\)。对于 \(i=1,2,\dots,k\)，我们有 \(v_i.d=\delta(s,v_i)\) 和 \(v_i.d\ge v_{i-1}.d+w(v_{i-1},v_i)\)。从这里我们可以得出结论 \(w(v_{i-1},v_i)\le\delta(s,v_i)-\delta(s,v_{i-1})\)。将路径 \(p\) 上的所有权重进行求和，有

\[ w(p)=w(v_0,v_1)+w(v_1,v_2)+\cdots+w(v_{k-1},v_k) \]

\[ w(p)\le (\delta(s,v_1)-\delta(s,v_0))+\cdots+(\delta(s,v_k)-\delta(s,v_{k-1})) \]

因为中间项相消，所以：

\[ w(p)\le \delta(s,v_k)-\delta(s,v_0) \]

又因为 \(v_0=s\)，有：

\[ w(p)\le \delta(s,v_k) \]

因此，\(w(p)\le\delta(s,v)\)。由于 \(\delta(s,v)\) 是从源结点 \(s\) 到结点 \(v\) 的任意一条路径权重的下界，我们推断 \(w(p)=\delta(s,v)\)。因此，\(p\) 确实是图 \(G\) 中从源结点 \(s\) 到结点 \(v\) 的一条最短路径。

注意这里的 \(v.d\le u.d+w(u,v)\)，和松弛操作、三角不等式的不等号方向恰好相反，而这依然是正确的：由于 \(v_i\) 的前驱节点是 \(v_{i-1}\)，因此只有两种可能：

• 发生松弛：取等。
• 否则，\(v_{i-1}\) 可能被更新，此时还没轮到 \(v_i\)。

24.1 Bellman-Ford 算法

边权重可以为负。若从源点可以走到一个负环，则算法返回 FALSE；否则返回 TRUE，并得到最短路和权重。

定义：

• \(d\) 表示算法进行过程中的当前最小值，也就是当前的最短路径估计。
• \(\delta\) 表示真正的最短路径权重。

伪代码

BELLMAN-FORD(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  for i = 1 to |G.V| - 1
3      for each edge (u, v) in G.E
4          RELAX(u, v, w)
5  for each edge (u, v) in G.E
6      if v.d > u.d + w(u, v)
7          return FALSE
8  return TRUE

说明与性质

• 第 1 行：所有结点的 \(d=\infty\)，\(\pi=\mathrm{NIL}\)，时间复杂度为 \(O(V)\)。
• 如果按照真实最短路的顺序进行松弛，则最终有 \(d=\delta\)。
• \(d=\delta\) 表示 \(d\) 已经达到真正的最短路径权重。
• 第 2–4 行结束后：所有从 \(s\) 可达的点都有 \(d=\delta\)。
• 每次按照最短路径顺序松弛，可以看作更新了一个点的绝对正确的最小值。
• 此时若 \(d=\infty\)，则说明 \(s\) 无法到达这个点。
• 第 5–8 行：如果还可以继续松弛，就说明存在从源点可达的负权环，因此返回 FALSE。

引理24.2：没有可以从 \(S\) 到达的负环路，则算法 2–4 行执行完之后，所有可从 \(s\) 到达的节点有 \(d=\delta\)。

推论24.3：没有可从 \(S\) 到达的负环路，则任意 \(v\in V\)，存在一条 \(s\) 到 \(v\) 的路径当且仅当算法终止时有 \(v.d<\infty\)。

定理24.4：算法正确性：如果不包含 \(s\) 可达负环路，则算法返回 TRUE，且任意 \(v\in V\) 有前驱子图 \(G_\pi\) 是一棵根节点为 \(S\) 的最短路径树。如果包含 \(s\) 可达负环路，则算法返回 FALSE。

• 算法终止时有 \(v.d=\delta(s,v)\)：如果 \(v\) 可达，用引理24.2；否则用非路径性质。
• 前驱子图性质知 \(G_\pi\) 是一棵最短路径树。
• 三角不等式知 5–8 行不会返回 false，则知返回 true。
• 如果包含可达负环路：设出具体路径，用 5–8 的不等式，累加。
  • 由推论24.3知有限值，可以消去。
  • 知 \(0\le\) 负数，矛盾。

24.2 有向无环图：拓扑排序

DAG 最短路径伪代码

DAG-SHORTEST-PATHS(G, w, s)
1  topologically sort the vertices of G
2  INITIALIZE-SINGLE-SOURCE(G, s)
3  for each vertex u, taken in topologically sorted order
4      for each vertex v in G.Adj[u]
5          RELAX(u, v, w)

核心思想：先对 DAG 做拓扑排序，再按照拓扑序依次松弛每个结点的所有出边。

定理 24.5 如果带权重无环路的有向图 \(G=(V,E)\) 有一个源结点 \(s\)，则在算法 DAG-SHORTEST-PATHS 终止时，对于所有的结点 \(v\in V\)，我们有 \(v.d=\delta(s,v)\)，且前驱子图 \(G_\pi\) 是一棵最短路径树。

证明：

• 不可达：非路径性质。
• 可达：存在最短路，设出。
  • 因为是拓扑顺序，放松次序正确。
  • 由路径松弛性质，\(v_i.d=\delta(s,v_i)\)。
  • 由前驱子图性质，\(G_\pi\) 是一棵最短路径树。

时间复杂度：\(O(V+E)\)。

PERT 图找最长路径：

• 将所有权重变为负数。
• 初始化时初始化为 \(-\infty\)，松弛时使用 <。

24.3 有环非负图：Dijkstra

Dijkstra 适用于所有边权非负的图。

伪代码

DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)
2  S = empty set
3  Q = G.V
4  while Q is not empty
5      u = EXTRACT-MIN(Q)
6      S = S union {u}
7      for each vertex v in G.Adj[u]
8          RELAX(u, v, w)

含义：每次从优先队列 \(Q\) 中取出当前 \(d\) 最小的结点 \(u\)，将其加入集合 \(S\)，然后松弛 \(u\) 的所有出边。

定理 24.6（Dijkstra 算法的正确性）Dijkstra 算法运行在带权重的有向图 \(G=(V,E)\) 时，如果所有权重为非负值，则在算法终止时，对于所有结点 \(u\in V\)，我们有 \(u.d=\delta(s,u)\)。

证明 我们使用下面的循环不变式：

在算法第 4–8 行的 while 语句的每次循环开始前，对于每个结点 \(v\in S\)，有 \(v.d=\delta(s,v)\)。我们只需要证明对于每个结点 \(u\in V\)，当结点 \(u\) 被加入到集合 \(S\) 时，有 \(u.d=\delta(s,u)\)。一旦证明了 \(u.d=\delta(s,u)\)，就可以使用上界性质来证明该等式在后续的所有时间内保持成立。

初始化：初始化时，\(S=\varnothing\)，因此，循环不变式直接成立。

保持：我们希望证明在每次循环中，对于加入到集合 \(S\) 的结点 \(u\) 来说，\(u.d=\delta(s,u)\)。我们使用反证法来证明此判断。设结点 \(u\) 是第一个在加入到集合 \(S\) 时使得该方程式不成立的结点，即 \(u.d\ne\delta(s,u)\)。由于结点 \(s\) 是第一个加入到集合 \(S\) 中的结点，并且 \(s.d=\delta(s,s)=0\)，结点 \(u\) 必定与结点 \(s\) 不同，即 \(u\ne s\)。因为 \(u\ne s\)，在即将把结点 \(u\) 加入到集合 \(S\) 时，我们有 \(S\ne\varnothing\)。此时，一定存在某条从结点 \(s\) 到结点 \(u\) 的路径，否则，根据非路径性质就有 \(u.d=\delta(s,u)=\infty\)，而这将违反我们的假设 \(u.d\ne\delta(s,u)\)。因为至少存在一条从 \(s\) 到 \(u\) 的路径，所以也存在一条从 \(s\) 到 \(u\) 的最短路径 \(p\)。在将结点 \(u\) 加入到集合 \(S\) 之前，路径 \(p\) 连接的是集合 \(S\) 中的一个结点（即 \(s\)）和 \(V-S\) 中的一个结点（即 \(u\)）。让我们考察路径 \(p\) 上第一个满足 \(y\in V-S\) 的结点 \(y\)，设 \(x\in S\) 为结点 \(y\) 在路径 \(p\) 上的前驱，则如图 24-7 所示，我们可以将路径 \(p\) 分解为 \(s \leadsto x \rightarrow y \leadsto u\)。（路径 \(p_1\) 或者 \(p_2\) 可能不包含任何边。）

图注：结点 \(x\) 和 \(y\) 是不同的结点，但可能有 \(s=x\) 或者 \(y=u\)。路径 \(p_2\) 既可能重新进入集合 \(S\)，也可能不能重新进入集合 \(S\)。

我们断言，在将结点 \(u\) 加入到集合 \(S\) 时，\(y.d=\delta(s,y)\)。为了证明这一点，只要观察到 \(x\in S\)，然后，因为选择的结点 \(u\) 是第一个在加入到集合 \(S\) 时不满足条件 \(u.d\ne\delta(s,u)\) 的结点，在将结点 \(x\) 加入到集合 \(S\) 时，有 \(x.d=\delta(s,x)\)。此时，边 \((x,y)\) 将被松弛，根据收敛性质可以得出我们的断言。

现在可以通过反证来证明 \(u.d=\delta(s,u)\)。因为结点 \(y\) 是从结点 \(s\) 到结点 \(u\) 的一条最短路径上位于 \(u\) 前面的一个结点，并且所有的边权重均为非负值，所以有 \(\delta(s,y)\le\delta(s,u)\)。因此，

\[ y.d=\delta(s,y) \]

\[ \le\delta(s,u) \]

\[ \le u.d \] > > 上面三式合称为式(24.2)，其中最后一步根据上界性质得到。 > > 但是，因为在算法第 5 行选择结点 \(u\) 时，结点 \(u\) 和 \(y\) 都在集合 \(V-S\) 里，所以有 \(u.d\le y.d\)。因此，式(24.2)中的两个不等式事实上都是等式，即 > \[ y.d=\delta(s,y)=\delta(s,u)=u.d \] > > 因此，\(u.d=\delta(s,u)\)，而这与我们所选择的结点 \(u\) 矛盾。因此，我们推断，在将结点 \(u\) 加入到集合 \(S\) 时有 \(u.d=\delta(s,u)\)，并且该等式在随后所有时间内都保持成立。 > > 终止：在算法终止时，\(Q=\varnothing\)。该事实与之前的不变式 \(Q=V-S\) 一起说明了 \(S=V\)。因此，对于所有的结点 \(u\in V\)，有 \(u.d=\delta(s,u)\)。

时间复杂度

INSERT, EXTRACT-MIN：每个节点一次。

DECREASE-KEY：每条边一次。

• 使用普通数组记录 \(v.d\)，时间复杂度为 \(O(V^2+E)\)。
  • INSERT 和 DECREASE-KEY：是 \(O(1)\)。
  • EXTRACT-MIN：遍历数组，\(O(V)\)。
• 稀疏图 \(E=o(V^2/\log V)\)，使用优先队列，时间复杂度为 \(O(E\log V)\)。
  • 构建：\(O(V)\)。
  • EXTRACT-MIN，DECREASE-KEY：\(O(\lg V)\)。
• 使用斐波那契堆：时间复杂度为 \(O(V\log V+E)\)。
  • 构建：\(O(V)\)。
  • EXTRACT-MIN：\(O(\log V)\)。
  • DECREASE-KEY：\(O(1)\)。

备注

• BFS、DFS 也可以理解为图搜索算法，但它们解决的问题和最短路径算法不完全相同。
• 差分约束可以转化为图上的最短路径问题，通常和 Bellman-Ford 联系起来。

24.4 差分约束

线性规划

在线性规划问题中，我们通常给定一个 \(m\times n\) 的矩阵 \(A\)，一个 \(m\) 维的向量 \(b\) 和一个 \(n\) 维向量 \(c\)。我们希望找到一个 \(n\) 维向量 \(x\)，使得在由 \(Ax\le b\) 给定的 \(m\) 个约束条件下优化目标函数

\[ c_1x_1+c_2x_2+\cdots+c_nx_n \]

这里的优化指的是使目标函数的取值最大。

差分约束

差分约束的一般形式是：

\[ x_j-x_i\le a \]

它对应图中的一条边：

\[ x_i\to x_j \]

这条边的权重为：

\[ w(x_i,x_j)=a \]

为了让所有结点都可以从源点到达，可以加入一个哨兵结点 \(v_0\)。哨兵结点 \(v_0\) 到任何变量结点的边权都是 \(0\)。

引理 24.8 设向量 \(x=(x_1,x_2,\dots,x_n)\) 为差分约束系统 \(Ax\le b\) 的一个解，设 \(d\) 为任意常数，则 \(x+d=(x_1+d,x_2+d,\dots,x_n+d)\) 也是该差分约束系统的一个解。

证明 对于每个 \(x_i\) 和 \(x_j\)，我们有 \((x_j+d)-(x_i+d)=x_j-x_i\)。因此，若向量 \(x\) 满足 \(Ax\le b\)，则向量 \(x+d\) 也满足该条件。

定理 24.9

给定差分约束系统 \(Ax\le b\)，设 \(G=(V,E)\) 是该差分约束系统对应的约束图。

如果图 \(G\) 不包含权重为负值的环路，则：

\[ x=(\delta(v_0,v_1),\delta(v_0,v_2),\delta(v_0,v_3),\dots,\delta(v_0,v_n)) \]

是该系统的一个可行解。

如果图 \(G\) 包含权重为负值的环路，则该系统没有可行解。

证明 首先证明如果约束图不包含权重为负值的环路，则式(24.11)给出一个可行解。考虑任意一条边 \((v_i,v_j)\in E\)，根据三角不等式，\(\delta(v_0,v_j)\le\delta(v_0,v_i)+w(v_i,v_j)\)，即 \(\delta(v_0,v_j)-\delta(v_0,v_i)\le w(v_i,v_j)\)。因此，如果设 \(x_i=\delta(v_0,v_i)\)和\(x_j=\delta(v_0,v_j)\)，则满足对应边 \((v_i,v_j)\) 的差分约束条件 \(x_j-x_i\le w(v_i,v_j)\)

现在我们来证明如果约束图包含权重为负值的环路，则差分约束系统没有可行解。不失一般性，设权重为负值的环路为 \(c=\langle v_1,v_2,\dots,v_k\rangle\)。这里 \(v_1=v_k\)（结点 \(v_0\) 不可能包含在环路 \(c\) 上，因为它没有进入的边）。环路 \(c\) 对应下面的差分约束条件组：

\[ x_2-x_1\le w(v_1,v_2) \]

\[ x_3-x_2\le w(v_2,v_3) \]

\[ \vdots \]

\[ x_k-x_{k-1}\le w(v_{k-1},v_k) \]

\[ x_1-x_k\le w(v_k,v_1) \]

我们使用反证法来进行证明。假设向量 \(x\) 有一个满足上述 \(k\) 个不等式的解，则这个解必须同时满足将 \(k\) 个不等式加起来之后形成的新的不等式。如果将 \(k\) 个等式加在边进行求和，每个未知变量 \(x_i\) 都加进来一次，被减去一次（记住，\(v_1=v_k\) 意味着 \(x_1=x_k\)），使得左边的和为 \(0\)。不等式右面的和为 \(w(c)\)，因此有 \(0\le w(c)\)。但是 \(c\) 是一个权重为负值的环路，因此 \(w(c)<0\)。这样我们得出了矛盾：\(0\le w(c)<0\)。

一个有 \(n\) 个未知变量和 \(m\) 个约束条件的差分约束系统所生成的约束图有 \(n+1\) 个结点和 \(n+m\) 条边。因此，使用 Bellman-Ford 算法，我们可以在 \(O((n+1)(n+m))=O(n^2+nm)\) 时间内求解系统。

优化：不加入哨兵节点，改为所有点的 \(d\) 被初始化为 \(0\)。