才疏学浅，理论知识不够。请教大家一个问题。图里面的最大流问题，求的是两点之间的，那么有没有办法求出来所有节点的能够通过的？直接依次求，更新权重就可以了嘛？
microxiaoxiao · 2022-06-23 09:57:49 +08:00 · 1691 次点击这是一个创建于 875 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
GuuJiang 2022-06-23 10:44:48 +08:00
@microxiaoxiao 重新准确描述下，你的意思是，是否存在一个算法一次性求出指定源点到其他所有汇点的最大流?还是说一次性求出所有点两两之间的最大流?(类似于最短路问题中的 floyd 算法那样)
|
 |
2
microxiaoxiao OP @GuuJiang 求所有的。就是这个集群最大能接受多少流
|
 |
3
MoYi123 2022-06-23 10:52:47 +08:00
|
|
4
GuuJiang 2022-06-23 11:09:58 +08:00
@microxiaoxiao 你可能对最大流的定义有点误解，当我们在讨论一个最大流时是不能脱离源点汇点单独存在的，换句话说只有预先指定了源点和汇点，接下来才能讨论最大流
不过我也大概理解了你的意思，你的意思应该是“在可以任意选择源点和汇点的前提下，所有任意组合的最大流中的最大值”，这个确实没有认真想过，和这个比较接近的是有多个源和多个汇的问题，解决方法是添加一个超级源和超级汇，然后求解，但是我猜这个方法应该是无法直接套用到你说的这个场景的，可能需要一些手段来规避同一个结点既作为源又作为汇的情况，否则的话求出来直接就是无穷大了，细节容我再想想 |
|
5
GuuJiang 2022-06-23 11:13:54 +08:00
刚才搜索了下，对于这个问题，目前没有什么比针对每一对结点分别跑一遍最大流算法更优的算法
|
 |
6
vance123 2022-06-23 11:16:21 +08:00 via Android
最大流问题也是线性规划问题，要不试试万能的求解器？
|
 |
7
nagatoism 2022-06-23 15:18:33 +08:00
|
|
8
nagatoism 2022-06-23 15:19:08 +08:00
全局的最小的 最大流等于全局的最小割。
|
|
9
microxiaoxiao OP @GuuJiang 哈哈，要不怎么说才疏学浅呢，就是我不太了解，其实问题更抽象一点，就是现在有多个节点，找到这样的组合，使得能够规划出来的两两节点值加起来最大。那么这个就是整个集群对外提供的输入输出能力
|
Select Language