10算法设计与分析---网络流

本章主要讲述网络流,其中包括取消部分设置好的流,残留网络:某一条边使用了多少流量,则其反方向设置多少可反悔的流量;Fold-Fulkerson算法:在残留网络从源到汇找一条可行路径,塞满流量;Edmonds-Karp算法:使用BFS搜索可行路径,时间复杂度
展开查看详情

1.东南大学计算机学院 方效林 网络流

2.本章内容 网络流 2

3.本章内容 给定有向图 ,边上 权值表示 容量,给定源点 和汇点 ,求 到 可流过的最大流量是多少?   3 s t 16 13 12 20 4 9 7 14 4

4.网络流 只考虑单向边的图,双向的图可通过增加虚拟节点的方式 变 换为单向边的图 4 s t 16 13 12 20 4 9 7 14 4 10 10 s t 16 13 12 20 4 9 7 14 4

5.网络流 给定有向图 ,边上 权值表示 容量,给定源点 和汇点 ,求 到 可流过的最大流量是多少?   5 s t 100 100 100 100 100

6.网络流 只考虑单向边的图,双向的图可通过增加虚拟节点的方式 变 换为单向边的图 6 s t 10 10 10 10 10 10 s t 10 10 10 10 10 10 10

7.网络流 简单想法 从源到汇找一条可行路径,塞满流量 7 s t 100 100 100 100 100 s t 100 100 100 100 100 简单想法 最优解

8.网络流 取消部分设置好的流 对一些设置好的流可能反悔 8 s t 100 100 100 100 100 s t 100 100 100 100 100 s t 100 100 100 100 100

9.网络流 残留网络 某一条边使用了多少流量,则其反方向设置多少可反悔的流量 9 s t 100 100 100 100 100 s t 100 100 100 100 100  

10.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 10   s t 100 100 100 100 100 s t 100 100 100 100 100 s t 100 100 100 100 100

11.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 11 s t 100 100 100 100 100   s t 100 100 100 100 100 s t 100 100 100 100 100 + =

12.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 12   s t 16 13 12 20 4 9 7 14 4 初始网络

13.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 13   s t 16 13 12 20 4 9 7 14 4 0 0 0 0 0 0 0 0 0 残留网络 1 路径上流为 4

14.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 14   s t 12 13 8 20 4 5 7 10 0 4 4 4 0 4 0 0 4 0 残留网络 2 路径上流为 4

15.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 15   s t 12 9 4 16 0 5 7 10 0 4 8 4 4 4 4 4 4 0 残留网络 3 路径上流为 4

16.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 16   s t 8 9 4 12 4 9 7 10 0 8 8 0 8 4 4 0 4 0 残留网络 4 路径上流为 7

17.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 17   s t 8 2 4 5 4 9 0 3 0 8 8 0 15 4 11 0 11 7 残留网络 5 路径上流为 4

18.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满流量 18   s t 4 2 0 1 4 9 0 3 0 12 12 0 19 4 11 0 11 7 残留网络 6 路径上流为 0

19.网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径,塞满 流量 遇到下面这个图,再遇到搜索可行路径时每次都经过权值为 1 那条边,时间复杂度很高 19   s t 10 6 10 6 10 6 1 10 6

20.网络流 Edmonds-Karp 算法 使用 BFS 搜索可行路径,时间复杂度   20 s t 10 6 10 6 10 6 1 10 6