八、单源点最短路问题

1.问题背景

给定一个带权重的有向图$G=\langle V,E \rangle$和权重函数$\omega:E\rightarrow R$。图中一条路径$p$的权重$\omega(p)$是构成该路径的所有边的权重之和。从结点$u$到结点$v$的最短路径权重定义为$\delta(u,v)$，当没有从$u$到$v$的路径时，$\delta(u,v)=\infty$。

试找出从给定的源点$s\in V$到其他每个结点$v\in V$的最短路径及其最短路径。

  • 单源点最短路问题(单目的地最短路径问题，单节点对最短路径问题)，所有结点对最短路径问题

  • 最优子结构性质：两个结点之间的最短路径的任何子路径都是最短的。

  • 松弛操作

    • 对于每个结点$v$，维持一个属性$v.d$，记录从源点$s$到结点$v$的最短路径权重的上界，称$v.d$为$s$到$v$的最短路径估计
    • $INITIALIZE-SINGLE-SOURCE$过程中，对所有$v\in V-{s}$有，$v.d=\infty$，$s.d=0$
    • 松弛操作中，首先进行测试(对$s$到$v$所经过的最后一个中间结点$u$，比较$v.d$和$u.d+w(u,v)$的值)，如果可以改善，则更新$v.d$和$v.\pi$
    • 时间复杂度为$O(1)$

  • 松弛操作的性质

    三角不等式性质：$\delta(s,v)\leq\delta(s,u)+\omega(u,v)$

    上界性质：$v.d$是$s$到$v$的最短路径权重$\delta(s,v)$的上界

    非路径性质：假定从源结点$s$到给定点$v$之间不存在路径，则该图在由算法$INITIALIZE-SINGLE-SOURCE(G,s)$进行初始化后，有$v.d\geq \delta(s,v)=\infty$， 并且该等式作为不变式一直维持到图$G$的所有松弛操作结束。

  • 若源点$s$无可达负环，则存在源点$s$的单源最短路径(如果有可达负环，则总有更小距离，最终可以松弛到$-\infty$)

2.$Bellman-Ford$算法

  • 给定带权图$G=\langle V,E,W \rangle$和源点编号$s$，找到源点$s$到所有其他顶点$t$的最短距离$\delta(s,t)$和最短路径$\langle s,\dots,t \rangle$或存在源点$s$可达的负环。

  • 解决挑战1：图中存在负权边时，如何求解单源最短路径?

    • 每轮对所有边进行松弛，持续迭代$\vert V\vert -1$轮。

  • 解决挑战2：图中存在负权边时，如何发现源点可达负环?

    • 若第$\vert V\vert$轮仍松弛成功，存在源点$s$可达的负环。

  • 伪代码如下

    第1行对所有结点的值进行初始化——$\Theta(V)$；

    第$2\thicksim 4$行对每条边进行$\vert V\vert -1$次松弛处理，每次循环中都对每条边进行一次松弛操作——$\Theta(E)$，共进行$\vert V\vert -1$次循环，总的时间复杂度为$\Theta(VE)$；

    第$5\thicksim 8$行检查图中是否存在权重为负值的环路并返回检查结果——$O(E)$；

    总的运行时间为$O(VE)$

  • 证明在无可达负环的情况下可以正确计算最短路径权重

    设$G=\langle V,E \rangle$为一个带权重的源点为$s$的有向图，其权重函数为$\omega:E\rightarrow R$，并假定图$G$中不包含从源结点$s$可以到达的权重为负值的环路。则$Bellman-ford$算法的第$2\thicksim 4$行的$for$循环在执行$\vert V\vert -1$次 之后，对于所有从源结点$s$可以到达的结点$v$有$v.d=\delta(s,v)$。

    证明：利用路径松弛性质。

    设$G=\langle V,E \rangle$为一个带权重的源点为$s$的有向图，其权重函数为$\omega:E\rightarrow R$，并假定图$G$中不包含从源结点$s$可以到达的权重为负值的环路。则对于所有结点$v\in V$，存在一条从源结点$s$到结点$v$的路径当且仅当$BELLMAN-FORD$算法终止时有$v.d<\infty$。

  • 证明在有可达负环的情况下可以返回FALSE值，否则返回TRUE值

    假设不包含可达负环时，可以得到$G_\pi$为一棵最短路径树，则当算法终止时，对于所有边$(u,v)\in E$，有$v.d=\delta(s,v)\leq \delta(s,u)+\omega(u,v)=u.d+\omega(u,v)$，因此返回TRUE；

    假设包含可达负环时，设该环路为$c=\langle v_0,v_1,\dots,v_k \rangle$，其中$v_0=v_k$，则有$\sum\limits_{i=1}^{k}\omega(v_{i-1},v_i)<0$，假设返回TRUE值，则有$v_i.d\leq v_{i-1}.d+\omega(v_{i-1},v_i)$，这里$i=1,2,\dots,k$。将所有不等式相加得到$\sum\limits_{i=1}^{k}v_i.d\leq \sum\limits_{i=1}^{k}(v_{i-1}.d+\omega(v_{i-1},v_i))=\sum\limits_{i=1}^{k}v_{i-1}.d+\sum\limits_{i=1}^{k}\omega(v_{i-1},v_i)$，而$v_0=v_k$，则得到$\sum\limits_{i=1}^{k}v_i.d=\sum\limits_{i=1}^{k}v_{i-1}.d$，又有$\sum\limits_{i=1}^{k}\omega(v_{i-1},v_i)\geq 0$，二者矛盾，得证。

3.$Dijkstra$算法

  • 给定带权图$G=\langle V,E,W \rangle$（所有边的权重为正值）和源点编号$s$，找到源点$s$到所有其他顶点$t$的最短距离$\delta(s,t)$和最短路径$\langle s,\dots,t\rangle$。

  • 算法从结点集$V-S$中选择当前最短路径估计最小的结点$u$，将$u$从$Q$中删除，并加入到$S$中，$u.d$就是源结点$s$到$u$的最短路径的 长度。这里$Q$是一个最小优先队列，保存结点集$V-S$。

  • 伪代码如下：

    $while$循环执行次数为$\vert V\vert$次，$for$循环执行$\vert E\vert$次（也即松弛操作次数）。

  • 证明算法的正确性

    采用反证法，假设顶点$u$被添加到$V_A$时，$u.d\ne \delta(s,u)$，而由上界性质有$u.d> \delta(s,u)$。

    应存在一条长度为$\delta(s,u)$的最短路径，设最短路径为$<s,\dots,x,y,\dots,u>$，其中$(x,y)$横跨割$\langle S,V-S\rangle$，$x\in S$，$y\in V-S$；将$x$加入$S$时，有$x.d=\delta(s,x)$，因此$(x,y)$将被松弛，由于$y$是最短路径$p$上的结点，因此有$\delta(s,y)=\delta(s,x)+\omega(x,y)=x.d+\omega(x,y)$，$y.d\leq x.d+\omega(x,y)$，得到$y.d=\delta(s,y)$，因此有$u.d>\delta(s,u)\geq \delta(s,y)=y.d$，显然$u$不是下一个被添加结点，矛盾，得证。

  • 时间复杂度分析：总运行时间依赖于$Q$的实现，采用二叉堆实现时，每次找到结点$u$需要$O(\lg V)$的时间，总运行时间为$O((V+E)\lg V)$

4.算法对比

项目 广度优先搜索 Dijkstra算法 Bellman-Ford算法
适用范围 无权图 带权图（所有边权重为正） 带权图
松弛次数 —— $\vert E \vert$次 $\vert V\vert\cdot\vert E\vert$次
数据结构 队列 优先队列 ——
运行时间 $O(\vert V\vert +\vert E\vert)$ $O(\vert E\vert\cdot\log\vert V\vert)$ $O(\vert E\vert\cdot\vert V\vert)$

5.差分约束系统

  • 线性规划：给定一个$m\times m$的矩阵$A$、一个$m$维的向量$b$和一个$n$维的向量$c$。试找一$n$维向量$x$，使得在$Ax\leq b$的约束下，目标函数$\sum\limits_{i=1}^{n}{c_ix_i}$最大。

  • 差分约束系统：矩阵$A$的每一行包括一个1和一个-1，其他所有项均为0。则上述问题转化为$m$个涉及$n$个变量的差额限制条件，每个约束条件均为简单的线性不等关系：$x_j-x_i\leq b_k$，这里$1\leq i,j\leq n,i\ne j,1\leq k\leq m$。

  • 解的线性性

    $x=(x_1,x_2,\dots,x_n)$为解，则$x+d=(x_1+d,x_2+d,\dots,x_n+d)$也为解；

  • 约束图

    引入额外结点$v_0$，从其出发可到达任何结点，因此节点集合$V$为${v_0,v_1,\dots,v_n}$

    边集合$E$包含代表每个差分约束的边，同时包含$v_0$到其他所有结点的边$(v_0,v_i)$

    如果$x_j-x_i\leq b_k$是一个差分约束条件，则边$(v_i,v_j)$的权重记为$\omega(v_i,v_j)=b_k$，而从$v_0$出发到其他结点的边的权重$\omega(v_0,v_j)=0$。

  • 问题的转换

给定差分约束系统$Ax\leq b$，设$G=\langle V,E \rangle$是该差分约束系统所对应的约束图。如果图$G$不包含权重为负值的回路，则$x=(\delta(v_0,v_1),\delta(v_0,v_2),\delta(v_0,v_3),\dots,\delta(v_0,v_n))$是该系统的一个可行解。如果图$G$包含权重为负值的回路，则该系统没有可行解。

设未知变量的个数$n=\vert x_i\vert$，不等式个数为$m$。则使用$Bellman-Ford$算法时，顶点数为$n+1$，边数为$m+n$，因此可以在$O(n^2+mn)$的时间内完成求解。

九、所有结点对的最短路径问题

1.问题背景

给定一个带权重的有向图$G=\langle V,E \rangle$和权重函数$\omega:E\rightarrow R$。图中一条路径$p$的权重$\omega(p)$是构成该路径的所有边的权重之和。从结点$u$到结点$v$的最短路径权重定义为$\delta(u,v)$，当没有从$u$到$v$的路径时，$\delta(u,v)=\infty$。

求$\forall u,v\in V$，从$u$到$v$的最短路径。

2.问题分析

  • 直观上，可以使用$Dijkstra$算法依次求解所有点，此时存在重叠子问题；

  • 使用$Dijkstra$算法依次求解所有点的算法复杂度为$O(\vert V\vert\vert E\vert\log\vert V\vert)$，对于稠密图有$\vert E\vert=O(\vert V\vert^2)$，因此算法复杂度为$O(\vert V\vert^3\log\vert V\vert)$；

  • 而观察松弛过程发现，具有最优子结构性：

  • 设$D[k,i,j]$表示：可从前$k$个点选点经过时，$i$到$j$的最短距离，则原始问题为$D[\vert V\vert,i,j]$

    如果不选第$k$个点经过，则$D[k,i,j]=D[k-1,i,j]$；

    如果选则第$k$个点经过，则$D[k,i,j]=D[k-1,i,k]+D[k-1,k,j]$；

    因此，$D[k,i,j]=min{D[k-1,i,k]+D[k-1,k,j],D[k-1,i,j]}$

3.自底向上的$Floyd-Warshall$算法

  • 初始化数组

    • $D[0,i,i]=0$：起点和终点重合，路径长度为0
    • $D[0,i,j]=e[i,j]$：任意两点直达距离为边权

  • 自底向上计算

    • 按$k$增加的顺序计算，求解时当前层只依赖上一层
    • 只需要两层表格——待计算和上一次结果
    • 当$k=i$或$k=j$时，$D[k,i,j]=D[k-1,i,j]$，可以直接覆盖；
    • 当$k\ne i且k\ne j$时，$D[k-1,i,k]+D[k-1,k,j]$和$D[k-1,i,j]$不是相同子问题，当求出$D[k,i,j]$后，$D[k-1,i,j]$不再被使用，可直接覆盖——求出新值可直接在原位置覆盖，只需存储一层表格；

  • 构建最优解

    • 使用前驱结点矩阵记录经过的中间点，此处使用追踪数组$Rec$记录经过的中间点

      $D_k[i,j]=D_{k-1}[i,j]$时$Rec$记录为0，表示没有中间点

      $D[k,i,j]=D[k-1,i,k]+D[k-1,k,j]$时$Rec$记录为$k$，表示经过中间点$k$

  • 伪代码如下：

    $All-Pairs-Shortest-Paths$：

    初始化数组$D$和$Rec$；

    按照$k$增大的顺序，对于任意一对$i,j$，进行松弛操作，并更新相关数组。

    $Find-Path$：

  • 算法复杂度为$O(\vert V\vert^3)$

4.最短路径算法小结

十、最大流

1.最大二分匹配

(1)问题描述

  • 给定一个无向图$G=\langle V,E \rangle$，其中$V=L\cup R,L\cap R=\Phi$，并且每条边$e\in E$有一个端点在$L$中而另一个端点在$R$中，可记为二分图$G=\langle L,R,E \rangle$。

  • 图$G=\langle V,E \rangle$中的一个匹配$M$是图$G$边集$E$的子集$(M\subseteq E)$，其中每个顶点至多关联$M$的一条边。

  • 现给定二分图$G=\langle L,R,E \rangle$，求出匹配$M={e_1,e_2,\dots,e_k}$，使得$max\vert M\vert$，满足$\forall i,j(i\ne j),e_i=(l_i,r_i),e_j=(l_j,r_j)$，有$l_i\ne l_j$且$r_i\ne r_j$。

    即使得匹配数最大且每个顶点至多关联一条边。

(2)问题分析

  • 直观上，可以遍历$L$中的顶点，依次检查之并与$R$中顶点进行匹配，这种策略可能达不到最大匹配，需要通过撤销边和连接边来增广原匹配。

  • 定义交替路径：从未匹配顶点出发，依次经过“非匹配边、匹配边…非匹配边”**形成的路径

  • 不断寻找交替路径进行增广

    • 依次检测左侧顶点，若相邻顶点未匹配，则构成交替路径，直接进行匹配；若相邻顶点已经匹配，则尝试寻找交替路径，增广成新匹配；
    • 直至所有左侧顶点检测完后结束。

  • 辅助数组

    • $matched$表示$L$与$R$中顶点的匹配关系

      以$R$中顶点作为下标，如$match[R_2]\leftarrow L_1$

    • $color$表示深度优先搜索辅助数组

      • white表示未被搜索过，black已被搜索过
      • 每次搜索前初始化$color$数组

(3)匈牙利算法

  • 伪代码如下：

    $Hungarian(G)$

    $DFS-Find(v)$

  • 正确性证明：

    • 命题1：匈牙利算法得到的匹配$M$无交替路径
    • 命题2：匹配$M$无交替路径$\Leftrightarrow$匹配$M$是最大匹配

2.最大流算法

(1)问题描述

  • 给定有向图$G=\langle V,E,C\rangle$，称之为流网络，$C$代表边权。

    • 源点为$s$，汇点为$t$

    • 容量：每条边的边权$c(e)\geq 0$

    • 流量：每条边的被占有容量$f(e)\geq 0$

    • 剩余容量：对于每条边，剩余容量为$c(e)-f(e)$

    • 总流量=源点流出量=汇点流入量：$\vert f\vert=\sum_{e\ out\ of\ s}f(e)=\sum_{e\ in\ to\ t}f(e)$

    • 容量限制：对于边$e\in E$，有$0\leq f(e)\leq c(e)$

      边上的流量不应超过边上的容量

    • 流量守恒：对顶点$v\in V-{s,t}$，$\sum_{e\ out\ of\ s}f(e)=\sum_{e\ in\ to\ t}f(e)$

      进入某顶点$v$流量和等于流出此顶点流量和

  • 现根据有向图$G=\langle V,E,C\rangle$，源点$s$，汇点$t$，在满足容量限制和流量守恒的约束条件下，求出最大流量。

(2)直观策略

  • 算法思想

    • 对于所有边$e\in E$，初始化流量为$f(e)=0$
    • 寻找一条$s$到$t$的路径$P$，此路径上每条边$e$均满足$f(e)<c(e)$
    • 按路径$P$上的最小剩余容量增加路径流量
    • 迭代寻找路径$P$直至无法增加路径流量

  • 此方法可能无法达到最大流量

  • 不足之处：只能扩充边的流量，不能缩减边的流量

  • 如果允许缩减边上的容量 ，则可以进一步增大总流量$\rightarrow$如果寻找路径时允许逆向搜索，可以增大总流量$\rightarrow$引入反向边，实现逆向搜索

  • 残存网络

    • 定义反向边权重：可缩减流量的上限，也即原始边上的流量$f(e)$

    • 定义正向边权重：可扩充流量的上限，也即原始边上的剩余容量$c(e)-f(e)$

    • 则根据流网络$G=\langle V,E,C\rangle$和流量$f$，可得残存网络$G_f=\langle V,E_f\rangle$，其中每条边的残存容量满足上述规则

    • 定义增广路径：增广路径$p$是残存网络$G_f$中一条从源点$s$到汇点$t$的简单路径(路径上的各顶点均不互相重复)

    • 定义增广路径的残存容量：路径上各边残存容量的最小值

      流量扩充的最大值为增广路径的残存容量

(3)$Ford-Fulkerson$算法

  • 算法思想
    • 对于所有边$e\in E$，初始化流量为$f(e)=0$
    • 构造残存网络$G_f$，寻找$s$到$t$的增广路径$P$
    • 按路径$P$的残存容量增加路径流量
    • 迭代寻找路径$P$直至无法增加路径流量
  • 伪代码如下
  • 算法复杂度
  • 正确性证明
    • 充分性：$f$是最大流$\Rightarrow$残存网络$G_f$中无增广路径
    • 必要性：$f$是最大流$\Leftarrow$残存网络$G_f$中无增广路径