【笔记】【网络流】原始对偶算法中调整的必要性与正确性的证明

如果不熟悉算法过程的话可以参考以下链接(中的代码)

  1. https://oi-wiki.org/graph/flow/min-cost/#primal-dual
  2. https://www.luogu.com.cn/blog/Mogician/Network-Flow-Guide

''引理'':若图\(G\)中有边\((u,v,w)\)(且均存在源点到\(u,v\)的最短路),则有

\[dis[v]\le dis[u]+w \]

证明:由最短路定义易得。\(\blacksquare\)

''正确性'':要证正确性,即证每次跑Dijkstra之前,(没有负环——不过这是显然的——且)对所有边\((u,v,w)\)有新的边权

\[w' = h[u]-h[v]+w \ge 0 \tag{1}\label{ref1} \]

证明:\(G\)增广后,每个点的势能\(Ep\)都加上了\(dis'\),变成了\(G\)中源点到每个点的最短路\(dis\)(见上面的第2个连接)。只需证明,在\(s\)到\(t\)的最短路上增加了一些负权反向边/删除了一些边后得到的\(G'\)中,对所有边\((u,v,w)\)都有\(\ref{ref1}\)成立

分两类讨论:

  1. 对所有不在最短路上的边\((u,v,w)\),因为\(w\)未变,故由引理,在图\(G\)上有\(dis[u]-dis[v]-w \ge 0\),成立。

  2. 对所有在最短路上的边\((u,v,w)\)有

    \[dis[u] - dis[v] + w\ge 0 \\ dis[v] - dis[u] - (-w)\ge 0 \]

    \[dis[u] +w = dis[v] \]

    由于\((u,v,w)\)在最短路上,显然成立。\(\blacksquare\)

修改是必要的:因为\(G\)的最短路可能不为\(0\)(与\(prev(G)\)相比增加了,如图\(G=(V=\{1,2,3\},E=\{(1,2,1),(1,3,1),(2,3,1)\})\)在一次增广之后的情况),导致出现正权边,必须变为零边。(否则新图\(G'\)中会有负权,不能跑Dijkstra)

上一篇:nopCommerce 3.9 大波浪系列 之 IWebHelper


下一篇:观察者模式的程序实例C++