网络流 Network flow
flowchart LRS(Source)v1([V1])v2([V2])v3([V3])v4([V4])t(sink)S -->|4| v1S -->|2| v2v1 -->|1| v2v2 -->|2| v4v1 -->|4| v4v1 -->|2| v3v4-->|3|tv3-->|3|t
有向有权图，Source为起点，Sink为终点。
阻塞流 blocking flow
flowchart LRS a@-->|2/2| v1v1 b@-->|1/1| v2S -->|0/2| v2v1 c@-->|1/2|Tv2 d@-->|1/1|Ta@{ animation: fast }b@{ animation: slow }c@{ animation: slow }d@{ animation: slow }
无法让更多的水流过。
如何找到一种阻塞流方案
Residual (空闲量) Graph (图)
空闲量=管道最大流量-实际流量；
- 随便找一条从起点到终点的路径。
- 计算该路径可通过的最大流量，更新空闲量。
- 重复，若找不到路径就结束。
flowchart LRS(Source)v1([V1])v2([V2])v3([V3])v4([V4])t(sink)S ==>|4-3=1| v1S -->|2| v2v1 -->|1| v2v2 -->|2| v4v1 ==>|4-3=1| v4v1 -->|2| v3v4==>|3-3=0|tv3-->|3|t
flowchart LRS(Source)v1([V1])v2([V2])v3([V3])v4([V4])t(sink)S ==>|1-1=0| v1S -->|2| v2v1 -->|1| v2v2 -->|2| v4v1 -->|1| v4v1 ==>|2-1=1| v3v4 -.-> tv3==>|3-1=2|t
没有从起点到终点的路径，找到阻塞流
最大流 Maximum flow
将边看成一些水管，水管有最大流量限制。从起点注水，求网络能承载的最大流量，即注水口和出水口的最大流量，每根管道的流量不能超过其最大流量。
Ford-Fulkerson Algorithm
- 随便找一条从起点到终点的路径。
flowchart LRS(Source)v1([V1])v2([V2])v3([V3])v4([V4])t(sink)S a@==> |4-3=1| v1S --> |2| v2v1 -->|1| v2v2 -->|2| v4v1 b@==>|4-3=1| v4v1 -->|2| v3v4 c@==>|3-3=0|tv3-->|3|ta@{ animation: fast }b@{ animation: fast }c@{ animation: fast }
-
该路径可通过最大流量为3，更新空闲量。
-
添加反向路径
flowchart LRS(Source)v1([V1])v2([V2])v4([V4])v3([V3])t(sink)S -->|1| v1S -->|2| v2v1 -->|1| v2v2 -->|2| v4v1 -->|1| v4v1 -->|2| v3v4 ~~~tt a@-.->|3|v4v4 b@-.->|3|v1v1 c@-.->|3|Sv3 -->|3|ta@{ animation: slow }b@{ animation: slow }c@{ animation: slow }
- 重复第一步，找一条从起点到终点的路径。
flowchart LRS(Source)v1([V1])v2([V2])v4([V4])v3([V3])t(sink)S -->|1| v1S a@==>|2| v2v1 -->|1| v2v2 b@==>|2| v4v1 -->|1| v4v1 d@==>|2| v3v4 ~~~tt -.->|3|v4v4 c@-.->|3|v1v1 -.->|3|Sv3 e@==>|3|ta@{ animation: fast }b@{ animation: fast }c@{ animation: fast }d@{ animation: fast }e@{ animation: fast }
- 最大流量为2，更新空闲量。
flowchart LRS(Source)v1([V1])v2([V2])v4([V4])v3([V3])t(sink)S -->|1| v1S ~~~ v2v1 -->|1| v2v2 ~~~ v4v1 -->|1| v4v1 ~~~ v3v4 ~~~ tt -.->|3|v4v4 -.->|1|v1v1 -.->|3|Sv3 -->|1|t
- 添加反向边，合并方向相同的边。
flowchart LRS(Source)v1([V1])v2([V2])v4([V4])v3([V3])t(sink)S -->|1| v1v1 -->|1| v2v1 c@--->|3| v4t -.->|3|v4v4 -.->|1|v1v1 -.->|3|Sv3 -->|1|tv2 a@-.->|2| Sv4 b@-.->|2| v2v3 d@-.->|2| v1t e@-.->|2| v3a@{ animation: slow }b@{ animation: slow }c@{ animation: fast }d@{ animation: slow }e@{ animation: slow }
- 找不到从起点到终点的路径，结束循环、
删除反向路径
flowchart LRS(Source) -->|1| v1([V1])S ~~~ v2([V2])v1 --> |1| v2v2 ~~~ v4v1 -->|3| v4([V4])v1 ~~~ v3([V3])v4~~~t(Sink)v3-->|1|t
计算流量
flowchart LRS(Source)v1([V1])v2([V2])v3([V3])v4([V4])t(sink)S -->|3| v1S -->|2| v2v1 -.-> v2v2 -->|2| v4v1 -->|1| v4v1 -->|2| v3v4-->|3|tv3-->|2|t
算法效率
Ford-Fulkerson Algorithm由于选择路径时的不确定性在一些情况下，速度非常慢。
举例：
flowchart LRS -->|1000| v1v1-->|1| v2S -->|1000| v2v1-->|1000|Tv2-->|1000|T
显然最大流为2000
若第一次选择路径 S->v1->T 或 S->v2->T则可以很快解决问题。
若选择 S->v1->v2->T 则需消耗较长时间。
flowchart LRS <-->|1\999| v1v2 -.->|1| v1S -->|1000| v2v1-->|1000|Tv2<-->|1\999|T
flowchart LRS <-->|1\999| v1v1 -.->|1| v2S <-->|1\999| v2v1<-->|1\999|Tv2<-->|1\999|T
在最坏情况下需要循环2000次。
Edmonds-Karp Algorithm
为了解决最坏情况下的效率问题，每次选取最短路径（不考虑边的权重）
时间复杂度：找最短路 \(O(edges)\),最多循环 \(edges\times vertices\)。最坏时间复杂度
\(O(edges^2 \times vertices)\) 证明比较复杂可以看原始论文。
Dinic's Algorithm
Yefilm Dinitz. Proceedings of the USSR Academy of Sciences, 11:
1277-1280, 1970.
阻塞流
最大流一定是阻塞流
阻塞流不一定是最大流，但无法让更多的水流过。
Level Graph 分层图
从起点出发走几步可以到达。
flowchart LRs(S/0)v1([3])v2([1])v3([3])v4([2])t(T/4)s <--> v2v2 <--> v4v1 <--> v4v1 --> sv4 --> v3v3 <--> tt --> v4v2 --> v4
flowchart LRs(S/0)v1([1])v2([1])v3([2])v4([2])t(T/3)s --> v1s --> v2v1 --> v3v1 --> v4v2 --> v4v3 --> t v4 --> t
计算最大流
- 构建 level graph
- 寻找阻塞流（更新空闲量）
- 如果找不到，break。
- 添加反向边
- goto 1
最坏时间复杂度 \(O(edges \times vertices^2)\)