腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(1706)
视频
沙龙
1
回答
非赋权图中的最
大流
algorithm
、
graph-algorithm
、
max-flow
、
edmonds-karp
最
大流
问题通常采用edmond-karp
算法
来解决,该
算法
建立残差图,并利用BFS来寻找
增广
路径
。 但最
大流
问题通常是针对赋权图定义的。对于未加权的图,我们可以简单地将每条边的权重视为1,但我想知道是否有更简单的
算法
来解决未加权的版本。
浏览 4
提问于2017-02-22
得票数 4
1
回答
确定最小边数E*,使得所有这些边的容量增加会导致最
大流
量的增加
algorithm
、
graph
、
network-flow
在我们运行FF
算法
并得到残差grpah Gf和min-cut (S,T)之后,这是我的方法。(1)使用BFS找出到u的部分
增广
路径
s和从v到t的所有部分
增广
路径
。如果这两条部分
增广
路径
都存在。然后增加(u,v)可以使最
大流
量增加1。有
浏览 3
提问于2017-12-10
得票数 0
1
回答
数据结构中MaxFlow问题的
路径
选择是否有限制?
data-structures
、
max-flow
、
network-flow
在下面的最
大流
问题中,
算法
首先可以选择S-A-D-T
路径
。在这种情况下,
算法
将不再看到任何增强
路径
,因此它将生成4作为最
大流
的答案。但是,如果
算法
首先选择任何其他
路径
,则会看到最
大流
变为5。
浏览 11
提问于2021-12-04
得票数 0
3
回答
最小成本流到最
大流
algorithm
、
reduction
是否存在从最小费用流问题到最
大流
问题的简化?或者反之亦然?我想使用最小费用流
算法
来解决最
大流
问题。
浏览 2
提问于2013-06-18
得票数 2
回答已采纳
2
回答
扩展
路径
算法
-最大匹配
matching
、
bipartite
我正在阅读扩充
路径
或Kuhn的
算法
,以便在未加权的二部图中找到最大匹配大小。我可以理解
算法
,但我在理解它通常实现的方式方面存在问题。这里有一个参考实现-- 。在每个阶段,我们应该尝试从左侧不匹配的顶点开始找到一条交替的
路径
。
浏览 4
提问于2014-08-27
得票数 2
1
回答
具有权值1的图中的Ford-Fulkerson
算法
algorithm
、
graph
在最
大流
问题中,当我应用ford-fulkerson
算法
寻找最
大流
时,如果图的所有链接都有权重1,则最
大流
将是我在ford fulkerson
算法
中找到的
路径
数,对吗?我是说,dfs
路径
的数目。
浏览 4
提问于2014-04-17
得票数 1
回答已采纳
1
回答
输出精确边缘的全局小裁剪
算法
algorithm
、
graph
我正在寻找一个
算法
,以找到一个无向图的全局小割集。我想输入一个图和
算法
输出最小的边数,通过切割它们,可以将给定的图分成两部分。 提前谢谢。
浏览 6
提问于2016-03-16
得票数 0
3
回答
动态图中的最
大流
algorithm
、
graph
、
max-flow
我正在寻找快速
算法
来计算动态图中的最
大流
量(添加/删除具有相关边的节点到图中)。也就是说,我们在G中有了最
大流
,现在添加/删除了带有相关边的新节点,我不喜欢重新计算新图的最
大流
,实际上,我想使用以前的结果来计算这个图。 任何不占用大量时间/内存的预处理都会被占用。
最
简单的想法是重新计算流程。另一个简单的想法是,保存之前的最
大流
量计算中使用的所有增加
路径
,现在为了添加顶点v,我们可以找到简单的
路径
(在上一步更新的容量图中),
浏览 0
提问于2012-01-26
得票数 10
回答已采纳
1
回答
图论/
算法
:多个最
大流
量是否意味着多个最小切割?
algorithm
、
graph-theory
我们知道,福特-富尔克森
算法
(FFA)将同时产生最
大流
和最小割解。我的问题是:如果仅限于整数图,多条最
大流
路径
的存在是否意味着多条最小切割
路径
的存在?我的方法是,如果我们知道FFA可以帮助我们找到不同的最
大流
量
路径
,那么我们就知道可以找到不同的对应最小切割。但是我们如何知道FFA是否可以找到不同的最
大流
量
路径
呢? 提前感谢!
浏览 1
提问于2018-11-11
得票数 0
2
回答
最
大流
量
算法
运行时间
algorithm
、
time-complexity
、
max-flow
、
ford-fulkerson
正确或错误:在Ford-Fulkerson
算法
中,我们总是可以找到一个增强s
路径
的流序列,这样我们就可以在多项式迭代次数中达到最
大流
。正确或错误:我们总是可以在Fulkerson
算法
中找到一个增强s
路径
的流序列,这样我们只有经过指数型迭代才能达到最
大流
。
浏览 4
提问于2018-12-18
得票数 3
2
回答
最
大流
量-通过顶点-如何?
algorithm
、
graph
找到一条从a到b的简单
路径
,如果存在的话。(简单
路径
是没有重复顶点的
路径
。)如果我将顶点b设置为接收器,我不能确定它是否会包括v。如果我将v设置为接收器,当达到v时如何继续?
浏览 0
提问于2012-01-05
得票数 8
1
回答
为什么我们要在Hopcroft-Karp
算法
中寻找最短的扩充
路径
?
algorithm
、
graph
、
graph-theory
、
matching
在最大二部匹配的Hopcroft-Karp
算法
中,为什么我们总是在广度优先搜索中寻找最短的
增广
路径
?是不是因为广度优先搜索总是找到最短的
路径
?我只是搞不懂为什么增强
路径
是最短的,这很重要。
浏览 2
提问于2013-05-15
得票数 0
回答已采纳
6
回答
如何使用最
大流
算法
在图上找到最小割线?
graph-theory
、
cut
、
minimum
、
flow
、
max-flow
我一直在读关于流网络的文章,但我所能找到的都是最
大流
算法
,如Ford-Fulkerson,push-relabel等。给定最
大流
-最小割集定理,是否可以使用这些
算法
中的一种来使用最
大流
算法
在图上找到最小割集?多么? 到目前为止,我找到的最好的信息是,如果我找到“饱和”边,即流量等于容量的边,这些边对应于最小切割。的确,最小割线上的所有边都是饱和的,但我相信也可能有饱和的边在最小割线“
路径
”之外。
浏览 6
提问于2010-12-19
得票数 59
1
回答
最短
路径
的最
大流
算法
?
algorithm
、
graph
在这种
算法
上有资源吗?我有一个无权图(所有边到一个容量更准确),我想找到源顶点和汇顶点之间的所有不同
路径
(所有可能的
路径
,没有人与另一个顶点共享),所以我想到了最
大流
问题和algo,但问题是我想要一个algo,它允许我拥有所有最短的不同
路径
由于最
大流
algo只是使用BFS或残差图中的某些内容进行搜索,因此它会随机增加我的流量(由于最
大流
的权重,最
大流
algo的每一次迭代都会增加我的流量,这对应于寻找一条新的不同
路径
),而我最终会得到最
浏览 0
提问于2018-07-20
得票数 0
回答已采纳
3
回答
最
大流
量和最小的切割。我做得对吗?
algorithm
我得到这个配置的最
大流
了吗?假设我拿到了它安全吗?
浏览 2
提问于2013-12-03
得票数 2
回答已采纳
1
回答
图中具有特定长度的顶点不相交
路径
algorithm
、
path
、
graph-theory
、
max-flow
输出: true,如果至少有两个两个顶点从s到t的最大
路径
长度k的不相交
路径
。否则-返回false。我的想法是分配每个边容量=1,并找到最
大流
。如果最
大流
量为>= 2,则返回true。但是,最
大流
搜索最短的增强
路径
,这并不总是最优的解决方案,如果你需要2个或更多的
路径
。有人有解决这个问题的
算法
吗?
浏览 3
提问于2021-09-22
得票数 0
回答已采纳
1
回答
最大二部匹配图论中的最
大流
算法
为何正确
algorithm
、
graph
、
bipartite
、
max-flow
我读过很多文章,指出用最
大流
算法
可以找到二部图的最大匹配。但是,我们从最
大流
得到的匹配可能不是最大的,或者匹配没有最大的边。来自Anti Laaksonen的竞争性方案编制手册的例子: 但是,如果我以不同的方式呈现这个图,那么现在的图形是: 然后,随着最
大流
量
算法
的推进,匹配结果为1-5,2-7。因为1简单地擦除了通向水槽的
路径
,但是如果它被移到边缘1-6,那么匹配可能是 1
浏览 3
提问于2021-06-24
得票数 1
回答已采纳
0
回答
在edmonds-karp
算法
中,我们如何在最短的
增广
长度内打破平局?
algorithm
、
edmonds-karp
那么,如果两条最短的
增广
路径
的长度是2,那么第二个过滤器是什么?然而,这两条
路径
的长度都是2。那么这个
算法
是否会扩展并说“选择具有最大/最小流量的
路径
”?
浏览 6
提问于2016-07-15
得票数 0
回答已采纳
1
回答
如何找到包含边e的从顶点x到顶点y的简单
路径
?
algorithm
、
undirected-graph
、
max-flow
建议一种
算法
,以确定是否存在从x到y的包含边缘e的简单
路径
。提前谢谢。
浏览 5
提问于2022-01-03
得票数 6
回答已采纳
2
回答
添加边缘后更新最
大流
algorithm
、
graph
、
max-flow
、
ford-fulkerson
、
edmonds-karp
考虑到我们有一个网络流,并且使用Edmond
算法
,我们已经有了网络上的最
大流
。现在,如果我们在网络中添加一个任意的边缘(具有一定的容量),那么更新最
大流
量的最佳方法是什么?我正在考虑更新关于新的边缘的剩余网络,并再次寻找增强
路径
,直到我们找到新的最
大流
量,但我不确定它是否工作或它是否是最好的方式!
浏览 6
提问于2014-12-13
得票数 4
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是网络流算法?详述网络流算法的原理?用C语言实现网络流算法。内附完整代码。
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
人脸定位算法的实际应用总结
人脸关键点定位算法在实际应用中的经验总结
NetworkX:Python图与网络模型基础
热门
标签
更多标签
活动推荐
运营活动
广告
关闭
领券