下载此文档

最大流问题以及应用.ppt

文档分类：IT计算机 | 页数：约12页举报非法文档有奖

1/12

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/12 下载此文档

文档列表 文档介绍

最大流问题以及应用
答辩人:吕永强
指导老师:王朝阳
目录

选题背景
最大流问题在生活中的方方面面都有广泛的应用。
交通运输网络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等,都属于最大流问题。
课题内容

,通过标号过程找到一条
增广路径;
,沿着增广路径增加网络
流流量的过程
优点:会得到一个最小割集,也就找到了网络中的“瓶颈”。也就找到了提高总流量的方法。
缺点:由于对增广路选择的任意性导致该算法的时间复杂度不仅仅依赖网络规模还与各边容量有关。
-Karp修正算法
“先标号的先扫描”。
对已给标号的顶点进行扫描时,先对所有和邻接的未给标号的顶点给予标号
优点:相对于Ford-Fulkerson算法,其使得流量增加总是沿着一条长度最短的路径从流向的。
缺点:时间复杂度相对于标号法而言减少了但仍然很大
Dinic算法
Dinic算法是标号法的改进算法。
Dinic算法则是兼取以上两种方法。在分层时用的宽度优先法,而寻求增广路径时·则采用深度优先策略。
是目前这三中算法中最高效的一个。
。
。
。
。
dinic算法基本步骤
Dinic算法的优点
通过分层切断了原来网络中的许多不必要的链接
每次 DFS 结束后会找到一条路径容量最小的边,那这条边之前的点可能引发新的增广路,若找到该点则可回溯到该点,从而减少从始点开始的开销。

最大流问题以及应用来自淘豆网www.taodocs.com转载请标明出处.

最大流问题以及应用.ppt

最大流问题及其应用

毕业设计论文最大流问题及应用

(毕业设计论文)最大流问题及应用

毕业设计论文最大流问题及应用

《最大流问题及应用毕业设计论文》

最大流问题及应用毕业设计论文

最大流问题及应用毕业设计论文

《最大流问题及应用毕业设计论文》

最大流问题以及应用

网络最大流问题的应用