最短路径

在最短路径问题中， 希望在一个图中找出从一个节点到另外一个节点的最短路径， 可能要找出从某一个特定节点到其他节点的最短路径， 也可能是找出所有节点对之间的最短路径， 图中边的权重可能为负值，甚至包含负的回路， 因此，在不同的情况下，有不同的算法适合求解问题， 关于求解所有节点之间的最短路径问题已经在动态规划时详细地解释过Floyd算法， 现在就谈谈两个处理单源最短路径的算法, Dijkstra算法和Bellman-Ford算法。

Dijkstra算法

Dijkstra算法用于求解所有边的权重为非负值时的单源最短路径问题， 它与Prim算法很相似，利用一个集合S保存已经求出最短路径的节点集合， 开始是S只包含源节点s, 每次从V-S中挑选出一个距离S中节点最近的节点u放入S，同时正确地设置u的邻居节点的路径长度， 直到S为V。

对于Dijkstra算法的正确性，只需要递归地证明下面的性质成立：

当节点u被加入到S时，u到s的最短路径已经被正确的设置, 而且u到s的最短路径上的前趋节点w已经被添加进S。

• 初始化：一开始时，这个性质显然成立
• 保持：假设当u被添加到S时，u到s的最短路径已经被正确的设置，对于u的任何一个邻接节点v， 如果s到v的最短路径是$s \xrightarrow{p} u \xrightarrow{} v$，那么s到v的路径能够被正确的设置， 而且从v到s最短路径上的前趋节点u已经被添加进S, 这样当v被添加进S时，上述的性质都是能够保持的。

Bellman-Ford算法

Bellman-Ford算法用于求解权重可以为负值时的单源最短路径问题， 而且它还可以用于判断图中是否存在s可达的负的回路。 Bellman-Ford的执行过程就是运行|V|-1次更新操作， 每次更新操作遍历每一条边(u, v)更新dist[v]，伪代码如下：

    procedure update((u, v)):
        dist[v] = min(dist[v], dist[u]+w(u, v))

    for k := 1 to |V|-1
        for (u, v) in E:
            update((u, v))

要证明这个算法的正确性，先说明它的两个性质：

1. 如果调用update((u, v))时，dist[u]已经被正确的设置， 那么dist[v]也将会被正确地设置。
2. 如果dist[v]已经被正确的设置， 调用任意的update((u, v))都不会改变dist[v]的值， 也就是说多次地执行update是安全的。

有了这个性质，对于任意节点v, 通过对v到s的最短路径的长度做一个简单的归纳， 就能够说明当算法结束时，dist[v]能够被正确的设置。

在我看来，Bellman-Ford算法的价值并不在于这个算法本身， 它给出求解一些问题的普遍思路。对于有着相互依赖的k个元素$\{n_1, n_2, ..., n_k\}$, 如果它们之间的关系很复杂，比如如果$n_1$和$n_2$之间有关系，那么$n_1$和$n_3$之间可能就会有关系， 而且这种关系可能构成一个循环，如果每次找到了两个元素的关系就去更新其他元素的关系就会陷入一个死循环， 但如果利用Bellman-Ford算法的思想，就能明白对于任意两个元素$n_i$和$n_j$，它们之间的关系最多隔着k-2个中间元素， 第1次更新的时候可以把没有隔中间元素的两个元素的关系确立好，第2次更新的时候可以把只隔1个元素的两个元素确定好， 依次类推，当k-1次更新的时候，所有元素的关系都能确定好。就不需要一确定两个元素的关系就去考虑要不要更新相关的元素， 思路显得清晰。

最大流问题

最大流问题是图论中一类很重要的问题，因为它和线性规划也有着很强的关联， 所以它的应用也十分广泛。在最大流问题中，对于图G，有两个特殊的节点s,t， 它的任何一条边都有一个容量c，对每条边的一个特定赋值称为一个流f， 流必须满足两个性质：

1. 对于任意一条边e，$0 \leq f_e \leq c_e$
2. 对于除了s,t之外的任意节点u, 入流等于出流, 即: $\sum\limits_{(w,u) \in E} f_{wu} = \sum\limits_{(u, z) \in E} f_{uz}$

最大流是想找出一个f，使得$\sum\limits_{s,u \in E} f_{su}$最大。

求解最大流的算法非常直观：

1. 从零流量开始
2. 每次从f的残留网络中选择一条从s到t的路径，在这条路径上增加流， 重复这个过程直到残留网络中不存在从s到t的路径为止

要证明这个算法的正确性，需要了解图的(s,t)-割， 以及割的容量，一个图的(s,t)-割把图分成互不交叉的两个组L和R, 使得s在L中，t在R中。该割的容量就是横跨L和R两个集合的所有边的容量之和， 有如下性质成立：

对于任意流f，任意(s,t)-割(L, R), $size(f) \leq capacity(L, R)$

说明割的容量是任何流的大小的上限。

下面说明最大流算法的正确性。当程序终止时，残留网络$G^f$中不存在由s到t的路径， 那么令L为$G^f$中s可达的所有节点，R为其他的节点，那么此时size(f) = capacity(L, R)。 这是因为对于任何从L到R的边e, 有

因为这其中任何一个违反都会导致e的终止节点在$G^f$中从s可达。所以此时size(f) = capacity(L, R)。 所以对于任意流f’, 都有$size(f') \leq size(f)$，意味这f是一个最大流。

关于最大流还有两个很重要的东西：

1. 如果采用BFS在残留网络中寻找从s到t的最短路径，会使得迭代的次数不会超过O(VE)
2. 最大流可用于二部图的匹配，关键是要证明容量为整数的图中找出的最大流给任意边的赋值都是整数。