运筹学教学 | 十分钟快速掌握最大流算法(附C++代码及算例)

—“运筹教科书到底能给你啥?”

—“算法和实现离教科书有多远?”

—“问题解决能力到底从哪来?”

今天刚起床就接到了BOSS的 提·问·三·连

小编表示

收到直击内心的提问之后,小编决定

翻开教科书、打开编译器

在今天的运筹学·第二弹——最大流问题篇

和大家一起寻找问题的答案!

运筹学·教学笔记 第二弹 —— 最大流问题篇 奉上!熟悉的攻略三连问题、方法、实现)、熟悉的实践演示、熟悉的代码算例...手把手带你走上 运筹学·大佬 的征程!

内容提要:

*什么是最大流问题

*求解最大流问题的算法

*两种增广路算法

1.什么是最大流问题

最大流问题(maximum flow problem)是一种组合优化问题,即讨论如何充分利用装置的能力,使得运输的流量最大以取得最好的效果的问题。

在具体描述最大流问题前,我们先介绍几个网络流问题中常见的定义:

G = (V,E) 表示整个图.

V 表示整个图中的所有结点的集合.

E 表示整个图中所有边的集合. s 表示网络的源点

t 表示网络的汇点. 对于每条边(u,v), 有一个容量c(u,v) (c(u,v)>=0)

(如果c(u,v)=0,则表示(u,v)不存在在网络中。相反,如果原网络中不存在边(u,v),则令c(u,v)=0.)

对于每条边(u,v) 有一个流量f(u,v).

在了解了些上述定义后,下面我们给出具体问题描述

(没错,就是你们常见的教科书内容来了!!)

好了,记笔记记笔记~~ 问题描述 part 教科书里面有基·础·范·本!!

2.求解最大流问题的算法

再次划重点记笔记!教科书上多只讲增广路算法!解决问题的算法不只一种,课本上篇幅有限,要想了解更多,还是要 自·己·学·操·作!!

然而和善如小编已经整理好这部分的资料打包送给各位...(没错,不要吝啬你们的夸奖...)

鉴于下面小编也会着重介绍增广路算法,有关最高标号预流推进算法学习资料在这里为大家指路

http://blog.csdn.net/KirinBill/article/details/60882828

(PS.致谢blog主人——大佬KirinBill~~~)

3.两种增广路算法

—增广路算法—

图2 残量网络与增广路算法

上面介绍了增广路解决最大流的思路,接下来我们介绍两种具体实现增广路方法的算法

Edmonds-Karp 算法

Dinic 算法

代码及算例示例

代码(c++版本)

算例演示

算例示例

输入格式:

Input

6 9

1 2 8

1 3 7

2 4 9

2 5 3

2 3 5

3 5 9

4 6 7

5 4 6

5 6 10

PS. 需要输入两个整数n, m分布代表节点数和边数,

接下来每行3个整数x y z代表x、y之间路径的容量是z

输出结果为:

Output:

15

PS. 输出一个整数,表示图中最大流结果

算例演示

如上所示,我们输入的是第一个网络图,算法代码运行后的结果如第二个网络图所示,其中边上流量值如11/16,表示这条边的最大容量为16,而从s到t,这条边的路径能通过的最大流量为11。

上述代码仅供分享交流学习用,如有需要复制下面链接自取 ↓ ↓ ↓

http://paste.ubuntu.com/25584352/

或直接戳文章底部的 阅读原文,跳转代码页面!

参考书目

[1] Operations Research - Applications and Algorithms (Wayne L. Winston)

[2] 刘汝佳, 算法竞赛入门经典(第2版) (算法艺术与信息学竞赛) P569 - P573

运筹学·教学笔记 第二弹 —— 最大流问题篇 画上句点!如果大家对 最大流问题 及 文中所叙内容 还有疑问或想要交流心得建议,欢迎移步留言区!

读至此,相信大家也都明白了开头的提问三连了~~教科书≠算法,教科书只会给我们列出 问题—方法 的框架,基于这些框架有许多算法、算法的实现、具体问题中的变化和运用...这些都需要我们自己主动去开拓、学习

......不说了,小编要去自己开拓solo了!

—end—

编辑:谢良桢(1922193128@qq.com)

华中科技大学管理学院本科三年级

贺兴(hexing15@gmail.com)

华中科技大学管理学院本科三年级

代码:贺兴(hexing15@gmail.com)

华中科技大学管理学院本科三年级

指导老师:秦时明岳(professor.qin@qq.com)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-11-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

资源 | 囊括欧亚非大陆多种语言的25个平行语料库数据集(拿走不谢!)

原文链接:https://gengo.ai/datasets/25-best-parallel-text-datasets-for-machine-transl...

2353
来自专栏鸿的学习笔记

写给开发者的机器学习指南(九)

正如你所看到的,最高的权重给予了几乎立即得到电子邮件回复的电子邮件,而最低权重给予具有非常长的时间范围的电子邮件。这允许具有非常低频率的电子邮件仍然基于它们被发...

1041
来自专栏AI科技大本营的专栏

用JavaScript创建神经网络的有趣教程,一定要让你知道!

【导读】本文中作者为初学者解释了如何使用 JavaScript 来搭建一个神经网络。不用担心,这不是一份深入介绍隐藏输入层、激励函数或如何使用 TensorFl...

1032
来自专栏CSDN技术头条

Google核心技术之——PageRank算法scala实现

PageRank算法简述 常言道,看一个人怎样,看他有什么朋友就知道了。也就是说,一个人有着越多牛X朋友的人,他是牛X的概率就越大。将这个知识迁移到网页上就是“...

2756
来自专栏大数据

有向无环图检测

01 — Spark背景介绍 Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark 是一种与 Hadoop 相似的开源集群计算环...

4557
来自专栏数据小魔方

R语言可视化——用ggplot构造期待已久的雷达图

之前一直苦恼于ggplot函数无法制作雷达图,心想着既然饼图可以通过柱形图+极坐标模拟出来,为啥雷达图不行。 我尝试着用折线图+极坐标来模拟雷达图(之前在制作饼...

3786
来自专栏CreateAMind

DeepMind可微分神经计算机-论文中文解读

又是一篇deepmind发表在nature上的文章,还记得前面2篇吗?一篇是DQN,一篇讲AlphaGo。发表在nature上的论文格式不太一样,正文只是简单描...

952
来自专栏生信宝典

NGS基础 - FASTQ格式解释和质量评估

FASTQ文件格式和命名 高通量测序之后用于下游分析的数据一般存储在FASTQ文件中。为了节省空间,又不影响下游使用,也一般用gzip压缩的格式。 单端测序每个...

3815
来自专栏林欣哲

自然语言处理--文本处理

自然语言处理的目的是让机器试图理解和处理人类的文字。通常来说,人的语言是冗余的,含有歧义的,而机器是准确的,无歧义的,要让机器理解,这之间存在一个转换的问题。 ...

3878
来自专栏杨建荣的学习笔记

对于随机数的一些分析

多年前我朋友圈的一个朋友公司年会抽奖出现了下面的这样一幕:CTO现场review代码。本来带着一丝娱乐精神,结果被无限放大了。所以年会中大家都会很自然想revi...

3558

扫码关注云+社区

领取腾讯云代金券