简化您的工作流程：搜索 miniwebtool。
添加插件
主页 > 数学 > 进阶数学计算 > 网络最大流计算器
 

网络最大流计算器

使用 Ford-Fulkerson 方法 (Edmonds-Karp 算法) 计算有向网络中从源点到汇点的最大流。动态演示每条增广路径，显示残留容量、饱和边以及证明最优性的最小割划分。

网络最大流计算器
快速示例：
教科书示例 (6 节点) 小型网络 经典 CLRS 类二分图 矩阵输入
边格式：A -> B : 10（箭头加容量），或 A, B, 10。 矩阵格式：每行输入一个矩阵行，C[i][j] 是边 i → j 的容量（无边使用 0）。对角线必须为 0。
以逗号或空格分隔的标签，对应每个矩阵行。默认为 S, A, B, …, T。

Embed 网络最大流计算器 Widget

网络最大流计算器

网络最大流计算器用于计算任何带容量的有向网络中从选定源点 s 到选定汇点 t 的最大流。在底层，它运行 Ford-Fulkerson 方法和广度优先增广路径（即 Edmonds-Karp 算法），并记录找到的每一条路径，以便您可以逐次迭代回放整个决策过程。结果页面还会显示最小割 —— 这是证明您的流值真正达到最优的瓶颈划分。

什么是最大流问题？

流网络是一个有向图 G = (V, E) 以及容量函数 c: E → ℝ≥0。其中有两个特殊的顶点：源点 s（流的起点）和汇点 t（流的终点）。流 f 是分配给各条边且满足以下条件的赋值 f(u, v) ≥ 0：

容量限制： 0 ≤ f(u, v) ≤ c(u, v) 对于每一条边 (u, v) 流量守恒： Σ f(w, v) = Σ f(v, w) 对于每一个 v ∈ V \ {s, t} 流值大小： |f| = Σ f(s, w) − Σ f(w, s) (离开 s 的净流量)

最大流问题是寻找使 |f| 最大化的流 f。直观理解：如果边是具有给定容量的水管，您每秒可以从 s 运送到 t 多少升水？

算法原理 — 带 BFS 的 Ford-Fulkerson

该算法在维护当前流量的同时维护一个残余图。对于每一条容量为 c 且当前流量为 f 的边 (u, v)，残余图包含：

在每次迭代中，它都会在残余图上执行从 s 到 t 的广度优先搜索 (BFS)。如果找到路径，则该路径上最小的边容量 —— 即瓶颈 —— 会被加到路径上每条正向边的流量中，并从每条反向边的流量中减去。这被称为增广路径。当 BFS 无法再到达 t 时，当前流量即为最优解。

当 残余图中存在从 s 到 t 的增广路径 P 时： b ← 路径 P 中所有边 (u, v) 的最小残余容量 c_residual(u, v) 沿路径 P 推送 b 单位流量 // 更新残余图 + 流量 返回总流量 |f|

使用 BFS（而非任意路径查找策略）将 Ford-Fulkerson 算法转变为 Edmonds-Karp 算法，其保证运行时间为 O(V · E²)。它还保证了在无理数容量情况下的终止，而普通 Ford-Fulkerson 则不能保证。

最大流最小割定理

割是将顶点划分为两个集合 (S, T) 的划分，其中 s ∈ S 且 t ∈ T。它的容量是从 S 到 T 的边的容量之和：

cap(S, T) = Σ c(u, v) 对于 u ∈ S, v ∈ T

最大流最小割定理 (Ford & Fulkerson, 1956) 指出：

最大流的值 = 最小割的容量

该工具会自动寻找最小割。在 Edmonds-Karp 算法终止后，它会在残余图上从 s 开始执行最后一次 BFS；到达的顶点形成 S，其余形成 T，原始图中所有从 S → T 跨越的边均已饱和。它们的容量总和恰好等于最大流值 —— 在结果顶部的“最小割容量 ✓ 验证了最优性”中可见。

专为学习设计的功能

输入格式

1. 带容量的边列表

每行一条边。箭头形式最易读，但也支持其他替代方案：

S -> A : 10 S -> B : 13 A -> B : 10 B -> A : 4 B -> T : 14

同时接受：A, B, 10 · A B 10 · A -> B , 10。同一对顶点之间的多条边将被累加。

2. 容量矩阵

每行输入一行数据，值之间用空格或逗号分隔。条目 C[i][j] 是从顶点 i 到顶点 j 的边的容量。无边请使用 0。矩阵必须是方阵，且对角线必须为 0（不允许自环）。

S A B C D T S [ 0 10 0 10 0 0 ] A [ 0 0 4 2 8 0 ] B [ 0 0 0 0 0 10 ] C [ 0 0 0 0 9 0 ] D [ 0 0 6 0 0 10 ] T [ 0 0 0 0 0 0 ]

在矩阵标签字段输入对应的顶点标签（用逗号或空格分隔）。如果省略，标签默认为 S, A, B, …, T。

最大流的应用

领域最大流的用途
交通与物流铁路/公路/管道网络每天从起点到终点可以运送多少货物？
二分图匹配将工作分配给工人，将学生分配给项目。单位容量的最大流即为最大匹配。
图像分割计算机视觉中的 Boykov–Kolmogorov 最小割算法用于分离前景和背景像素。
网络可靠性最小割可以识别最薄弱的环节，这些环节的失效会导致网络断开。
项目调度闭包问题和选择问题可以归约为最小割问题。
棒球淘汰分析确定一支球队是否在数学上已经失去了夺冠的可能性。

操作实例

“教科书”快速示例编码了一个具有源点 S 和汇点 T 的 6 节点网络。运行 Edmonds-Karp 算法会产生四条增广路径：

  1. S → A → B → T，瓶颈为 4（边 A-B 是限制因素）。当前总流量：4。
  2. S → A → D → T，瓶颈为 6。当前总流量：10。
  3. S → C → D → T，瓶颈为 4（边 D-T 现在是限制因素，仅剩 4 个单位）。当前总流量：14。
  4. S → C → D → B → T，瓶颈为 5。当前总流量：19。

算法停止 —— 不再存在增广路径。最小割为 (S = {S, C}, T = {A, B, D, T})，跨越边为 S → A (容量 10) 和 C → D (容量 9)，总和为 19 —— 正好等于最大流值。

如何使用此计算器

  1. 选择输入格式（使用选项卡） —— 边列表（推荐）或容量矩阵。
  2. 输入您的网络。 您可以从快速示例开始并进行修改。对于矩阵输入，如果您想要 S, A, B, …, T 以外的名称，请提供标签。
  3. 指定源点和汇点（或留空以自动检测 S 和 T）。
  4. 点击计算最大流。 结果页面显示最大流值、最小割划分、分层图可视化、每条增广路径、边利用率表以及三个矩阵（容量、流量、残余）。
  5. 播放图表下方的动画来回放算法的决策。点击任何增广路径步骤可直接跳至该步骤。

限制

常见问题解答

什么是最大流问题？

给定一个有向网络，其中每条边都有一个非负容量，最大流问题是问：在满足每条边的流量不能超过其容量，且进入每个非源、非汇顶点的流量必须等于离开它的流量的规则下，从指定的源点 s 到指定的汇点 t 可以推送多少流量？答案被称为最大流值。

什么是 Ford-Fulkerson 方法？

Ford-Fulkerson 是计算最大流的一种通用技术。它在残余图中反复寻找从源点到汇点的增广路径，并沿该路径推送尽可能多的流量（瓶颈容量），然后更新残余图。当不存在增广路径时，程序终止。当使用广度优先搜索进行路径选择时，它被称为 Edmonds-Karp 算法，运行时间为 O(V · E²)。

流网络的最小割是什么？

割是将顶点划分为两个集合 S 和 T，使得源点在 S 中，汇点在 T 中。割的容量是从 S 到 T 的边的容量之和。最小割是容量最小的割。著名的最大流最小割定理证明了最大流值始终等于最小割容量，因此找到其中一个也就免费得到了另一个。

什么是残余图？

残余图跟踪每条边还可以推送多少流量。对于容量为 c 且当前流量为 f 的原始边 (u, v)，残余图包含一条正向边 (u, v) 与容量 c 减 f（剩余容量），以及一条反向边 (v, u) 与容量 f（可取消流量）。增广路径使用残余图中的边，使算法能够撤回之前的决定。

为什么该工具使用 BFS 寻找增广路径？

使用广度优先搜索 (Edmonds-Karp) 选择增广路径可以保证无论边容量如何，都能在多项式时间内终止。使用任意路径查找策略的普通 Ford-Fulkerson 在病态输入上可能会循环指数次迭代，在无理数容量上甚至可能永远不会终止。BFS 还会产生最短增广路径，更易于阅读和分析。

饱和边意味着什么？

当一条边的流量等于其容量时，该边即为饱和，这意味着无法再在其上推送更多流量。饱和边是网络的瓶颈，每个最小割完全由从割的 S 侧到 T 侧的饱和边组成。该工具用红色突出显示饱和边，让您一眼就能看到瓶颈结构。

延伸阅读

引用此内容、页面或工具为：

"网络最大流计算器" 于 https://MiniWebtool.com/zh-cn/网络最大流计算器/，来自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 团队制作。更新于：2026年4月22日

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

其他相关工具:

绝对值计算器新
邻接矩阵计算器新
亲和数检查器新
进位与借位可视化工具新
迪杰斯特拉最短路径计算器

进阶数学计算:

常用工具:

随机信用卡生成器MAC地址查找🌡️ 体感温度计算器彩票号码生成器网址提取器相对标准偏差计算器英尺英寸转换为厘米CAGR计算器太阳、月亮与上升星座计算器 🌞🌙✨随机选择器cpm计算器样本量计算器百分比折扣计算器VAT计算器HEX计算器比例计算器随机扑克牌生成器二进制计算器毛利率计算器音频提取器FPS 转换器月亮星座计算器定期存款计算器随机名字选择器时间持续计算器SRT转为TXT工具音频分割器kg到lbs转换器斜边计算器图片打码工具年龄计算器血糖转换器股票平均成本计算器厘米到英寸转换器MAC地址生成器厘米到英尺和英寸转换器📅 日期计算器随机IMEI生成器两个日期之间磅转千克转换器视频转图片提取器随机字符串生成器合并视频分数计算器英寸到厘米转换器MAC 地址分析工具卡方检验计算器💧 露点计算器螺栓扭矩计算器凯利公式计算器圆计算器百分比变化计算器One Rep Max (1RM) 计算器🎮 游戏灵敏度转换器随机分组生成器英尺到米转换器调整视频速度srt时间偏移质数检查器椭圆周长计算器三角函数绘图器百分比增长率计算器罗马数字转换器图片分割器年度天数计算器 - 今天是今年的第几天百分比计算器石头剪刀布生成器随机用户代理生成器对数计算器随机化数字SHA256 哈希生成器t检验计算器最简分数计算器商和余数计算器条形码生成器利润计算器MD5哈希生成器百分比增加计算器线性回归计算器每个月的天数随机超能力生成器日历DOY日历半衰期计算器圆形面积计算器职位查找器Facebook用户ID查询随机坐标生成器快速傅里叶变换FFT计算器电池续航计算器分数百分比转换器移除标点符号在线工具随机端口号生成器位数计算器为图片添加文字平方根计算器随机装备生成器六西格玛过程能力计算器逻辑门模拟器随机颜色生成器体脂百分比计算器数字提取器两点间距离计算器分贝 (dB) 计算器视频压缩器SRT合并工具复合增长率计算器股息收益率计算器行数统计工具AI Token 计数器自酿啤酒酒精度计算器随机字母生成器黄金分割计算器kpa到psi转换器命运数字计算器圆台计算器方向场斜率场绘图器质数分解计算器闰年清单Log Base 10 计算器图片添加线条圆柱体体积计算器 高精度填字游戏制作器查找并替换文本年金现值计算器组合计算器随机数字选择器AI改写工具AI标点符号添加器卧推计算器根式化简器箱线图生成器PSI 转 Bar 转换器方差计算器 高精度获取字符串长度迷宫生成器AI内容检测器Instagram用户ID查询🎲 掉落概率计算器楼梯计算器百分比减少计算器英亩到平方米转换器随机域名生成器YouTube频道统计克到磅转换器工资转换计算器IPv4/IPv6到十六进制转换器为视频添加水印十进制到十六进制转换器平均值计算器盎司到克转换器字符计数器相关系数计算器磅到克转换器视频分割器图片压缩器模计算器死链检查器黄金时刻和蓝调时刻计算器AI语言检测器标准偏差计算器 - 高精度科学计算器atan2计算器克到盎司转换器🎰 抽卡保底计算器🌍 碳足迹计算器线性方程组求解器误差函数计算器平均偏差计算器指数计算器-高精度旋转视频沸点计算器百分比到ppm转换器隐形文本生成器YouTube缩略图下载器⏱️ 倒计时器农历转换器双重积分计算器真心话大冒险生成器翻转视频随机圣经经文生成器鞋码转换器文本去重工具十六进制到十进制转换器坡度与倾斜度计算器幻方生成器折扣计算器斜率截距式计算器步数距离计算器随机生日生成器anova计算器原根计算器⏱️ 小时计算器工作日计算器文本格式化工具标准误差计算器直方图生成器竖式加减法计算器配色方案生成器随机物品生成器标准杯计算器葡萄酒搭配建议器攀岩难度等级转换器自行车齿轮比计算器钓鱼结强度计算器瑜伽体式保持计时器游泳SWOLF计算器跑步成绩预测计算器拳击出拳力量计算器橄榄球得分计算器板球得分率计算器足球 xG预期进球计算器网球计分器Wells评分计算器 (DVT/PE)格拉斯哥昏迷评分计算器阿普加评分计算器FFMI计算器库珀12分钟跑步计算器一英里步行测试Rockport计算器瘦体重力量计算器碳水化合物胰岛素比例计算器胰岛素敏感系数计算器希伯来历转换器伊斯兰历转换器跨文化年龄计算器多久以前计算器还有多久倒计时计算器日期模式生成器中间日期计算器日期添加工作日词频分析器句子长度方差分析器海明威风格可读性编辑器发音音标转换器维吉尼亚密码工具埃特巴什密码工具ROT13编码解码器EXIF数据查看与移除工具猪拉丁文翻译器倒推首字母缩写生成器首字母缩写生成器全字母句检查器漏字文检测器图像转SVG描摹器图片转 ASCII 艺术转换器JSON Schema 生成器TypeScript 在线演练场Less 到 CSS 编译器SCSS转CSS编译器SVG 转 React/JSX 转换器查询字符串生成器URL解析器UUID验证和解码器HTTP状态码参考cURL命令构建器谢尔宾斯基三角形生成器3D曲面绘图器极坐标方程绘图器朱利亚集合生成器曼德博集合探索器L-System分形生成器Delaunay 三角剖分生成器Voronoi 图生成器万花尺图案生成器镶嵌图案生成器帕累托图生成器NPS净推荐值计算器留存率同期群计算器客户流失率计算器客户获取成本CAC计算器客户终身价值 CLV 计算器转化率计算器A/B测试样本量计算器A/B测试显著性计算器透镜方程计算器导线磁场计算器电场计算器库仑定律计算器斯涅尔定律计算器惯性矩计算器角速度计算器向心力计算器单摆周期计算器弹簧劲度系数计算器多普勒效应计算器索提诺比率计算器特雷诺比率计算器股票贝塔系数计算器通胀保值美国国债 (TIPS) 计算器房贷重新摊还计算器远期利率计算器债券久期计算器 (麦考利和修正)债券凸性计算器固定指数年金计算器变额年金计算器反向抵押贷款计算器年金支付计算器日本算盘模拟器俄罗斯农民乘法吠陀数学技巧计算器古埃及乘法计算器罗马数字数学求解器心算训练器乘法口诀表测验进位与借位可视化工具数的分合生成器硬币应用题求解器距离速度时间三角形计算器工作效率问题求解器混合问题求解器年龄问题求解器火车相遇问题求解器补水计算器配速卡路里计算器药物剂量计算器酒精卡路里计算器身体重塑计算器随机辩论话题生成器随机猫狗名字生成器随机数学题生成器随机段落生成器随机英文句子生成器砾石、砂和表土计算器钢材重量计算器管道流量计算器梁荷载计算器美元换黄金转换器期权概率计算器股票拆分计算器员工持股计划计算器发票滞纳金计算器自由职业者时薪计算器租赁与购买对比计算器高级小费分摊计算器装箱清单生成器时差反应计算器旅行预算计算器飞行距离计算器热损失计算器发电成本计算器用水量计算器家电用电成本计算器家庭能源审计计算器太阳能投资回报率计算器太阳能板计算器堆肥CN比计算器草坪肥料计算器霜冻日期计算器高床种植箱土壤计算器NPK肥料计算器种子发芽率计算器视频比特率计算器音乐调性转换器音乐BPM节拍点击器照片文件大小估算计算器百万像素到打印尺寸计算器裁切系数计算器曝光三角计算器车辆牵引能力计算器汽车租赁计算器0–60与四分之一英里计算器电动车充电时间计算器电动汽车续航计算器3D距离计算器环面计算器不规则多边形面积计算器正多边形计算器圆锥曲线识别器双曲线计算器长除法计算器Twitter/X 字符计数器YouTube评论抽选器YouTube标签提取器youtube收益估算器随机RPG角色生成器