腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
数据结构中MaxFlow问题的
路径
选择是否有限制?
、
、
在下面的最
大流
问题中,
算法
首先可以选择S-A-D-T
路径
。在这种情况下,
算法
将不再看到任何增强
路径
,因此它将生成4作为最
大流
的答案。但是,如果
算法
首先选择任何其他
路径
,则会看到最
大流
变为5。
浏览 11
提问于2021-12-04
得票数 0
1
回答
具有权值1的图中的Ford-Fulkerson
算法
、
在最
大流
问题中,当我应用ford-fulkerson
算法
寻找最
大流
时,如果图的所有链接都有权重1,则最
大流
将是我在ford fulkerson
算法
中找到的
路径
数,对吗?我是说,dfs
路径
的数目。
浏览 4
提问于2014-04-17
得票数 1
回答已采纳
3
回答
动态图中的最
大流
、
、
我正在寻找快速
算法
来计算动态图中的最
大流
量(添加/删除具有相关边的节点到图中)。也就是说,我们在G中有了最
大流
,现在添加/删除了带有相关边的新节点,我不喜欢重新计算新图的最
大流
,实际上,我想使用以前的结果来计算这个图。 任何不占用大量时间/内存的预处理都会被占用。
最
简单的想法是重新计算流程。另一个简单的想法是,保存之前的最
大流
量计算中使用的所有增加
路径
,现在为了添加顶点v,我们可以找到简单的
路径
(在上一步更新的容量图中),
浏览 0
提问于2012-01-26
得票数 10
回答已采纳
1
回答
图中具有特定长度的顶点不相交
路径
、
、
、
输出
: true,如果至少有两个两个顶点从s到t的最大
路径
长度k的不相交
路径
。否则-返回false。我的想法是分配每个边容量=1,并找到最
大流
。如果最
大流
量为>= 2,则返回true。但是,最
大流
搜索最短的增强
路径
,这并不总是最优的解决方案,如果你需要2个或更多的
路径
。有人有解决这个问题的
算法
吗?
浏览 3
提问于2021-09-22
得票数 0
回答已采纳
1
回答
在最
大流
问题中,如何找到给出最
大流
的所有可能的
路径
集?
、
、
我知道在流网络中,可以找到从源(s)流到宿(t)的最
大流
。举个例子:
路径
集1:s-0-1-t, s-2-3-t, s-5-6-t
路径
集3:s-0-3-t, s-2-4
浏览 7
提问于2018-12-18
得票数 4
1
回答
图论/
算法
:多个最
大流
量是否意味着多个最小切割?
、
我们知道,福特-富尔克森
算法
(FFA)将同时产生最
大流
和最小割解。我的问题是:如果仅限于整数图,多条最
大流
路径
的存在是否意味着多条最小切割
路径
的存在?我的方法是,如果我们知道FFA可以帮助我们找到不同的最
大流
量
路径
,那么我们就知道可以找到不同的对应最小切割。但是我们如何知道FFA是否可以找到不同的最
大流
量
路径
呢? 提前感谢!
浏览 1
提问于2018-11-11
得票数 0
2
回答
最大二部匹配方法中的误差
、
、
、
我想找出从源头到下沉的最
大流
量。一种方法是使用Fulkerson
算法
求解最
大流
问题,该
算法
适用于所有的图。我找到了一种简单的方法来找到最
大流
(太简单了,不正确!)我无法在这个方法中发现任何错误。最
大流
将是这两个数字的最小值,即min(c1,c2).Since --任何
路径
都需要从
输出
顶点列表中提取一个顶点,而从传入顶点列表中需要另一个顶点。 任何帮助都将不胜感激。
浏览 3
提问于2016-01-24
得票数 0
回答已采纳
2
回答
最
大流
量
算法
运行时间
、
、
、
正确或错误:在Ford-Fulkerson
算法
中,我们总是可以找到一个增强s
路径
的流序列,这样我们就可以在多项式迭代次数中达到最
大流
。正确或错误:我们总是可以在Fulkerson
算法
中找到一个增强s
路径
的流序列,这样我们只有经过指数型迭代才能达到最
大流
。
浏览 4
提问于2018-12-18
得票数 3
2
回答
最
大流
量-通过顶点-如何?
、
找到一条从a到b的简单
路径
,如果存在的话。(简单
路径
是没有重复顶点的
路径
。)如果我将顶点b设置为接收器,我不能确定它是否会包括v。如果我将v设置为接收器,当达到v时如何继续?
浏览 0
提问于2012-01-05
得票数 8
1
回答
非赋权图中的最
大流
、
、
、
最
大流
问题通常采用edmond-karp
算法
来解决,该
算法
建立残差图,并利用BFS来寻找增广
路径
。 但最
大流
问题通常是针对赋权图定义的。对于未加权的图,我们可以简单地将每条边的权重视为1,但我想知道是否有更简单的
算法
来解决未加权的版本。
浏览 4
提问于2017-02-22
得票数 4
6
回答
如何使用最
大流
算法
在图上找到最小割线?
、
、
、
、
我一直在读关于流网络的文章,但我所能找到的都是最
大流
算法
,如Ford-Fulkerson,push-relabel等。给定最
大流
-最小割集定理,是否可以使用这些
算法
中的一种来使用最
大流
算法
在图上找到最小割集?多么? 到目前为止,我找到的最好的信息是,如果我找到“饱和”边,即流量等于容量的边,这些边对应于最小切割。的确,最小割线上的所有边都是饱和的,但我相信也可能有饱和的边在最小割线“
路径
”之外。
浏览 6
提问于2010-12-19
得票数 59
1
回答
最短
路径
的最
大流
算法
?
、
在这种
算法
上有资源吗?我有一个无权图(所有边到一个容量更准确),我想找到源顶点和汇顶点之间的所有不同
路径
(所有可能的
路径
,没有人与另一个顶点共享),所以我想到了最
大流
问题和algo,但问题是我想要一个algo,它允许我拥有所有最短的不同
路径
由于最
大流
algo只是使用BFS或残差图中的某些内容进行搜索,因此它会随机增加我的流量(由于最
大流
的权重,最
大流
algo的每一次迭代都会增加我的流量,这对应于寻找一条新的不同
路径
),而我最终会得到最
浏览 0
提问于2018-07-20
得票数 0
回答已采纳
3
回答
最
大流
量和最小的切割。我做得对吗?
我得到这个配置的最
大流
了吗?假设我拿到了它安全吗?
浏览 2
提问于2013-12-03
得票数 2
回答已采纳
1
回答
确定最小边数E*,使得所有这些边的容量增加会导致最
大流
量的增加
、
、
在我们运行FF
算法
并得到残差grpah Gf和min-cut (S,T)之后,这是我的方法。(1)使用BFS找出到u的部分增广
路径
s和从v到t的所有部分增广
路径
。如果这两条部分增广
路径
都存在。然后增加(u,v)可以使最
大流
量增加1。有几种可能性 (a)在残差中,源s没有
输出</e
浏览 3
提问于2017-12-10
得票数 0
1
回答
最大二部匹配图论中的最
大流
算法
为何正确
、
、
、
我读过很多文章,指出用最
大流
算法
可以找到二部图的最大匹配。但是,我们从最
大流
得到的匹配可能不是最大的,或者匹配没有最大的边。来自Anti Laaksonen的竞争性方案编制手册的例子: 但是,如果我以不同的方式呈现这个图,那么现在的图形是: 然后,随着最
大流
量
算法
的推进,匹配结果为1-5,2-7。因为1简单地擦除了通向水槽的
路径
,但是如果它被移到边缘1-6,那么匹配可能是 1
浏览 3
提问于2021-06-24
得票数 1
回答已采纳
1
回答
如何找到包含边e的从顶点x到顶点y的简单
路径
?
、
、
建议一种
算法
,以确定是否存在从x到y的包含边缘e的简单
路径
。提前谢谢。
浏览 5
提问于2022-01-03
得票数 6
回答已采纳
2
回答
添加边缘后更新最
大流
、
、
、
、
考虑到我们有一个网络流,并且使用Edmond
算法
,我们已经有了网络上的最
大流
。现在,如果我们在网络中添加一个任意的边缘(具有一定的容量),那么更新最
大流
量的最佳方法是什么?我正在考虑更新关于新的边缘的剩余网络,并再次寻找增强
路径
,直到我们找到新的最
大流
量,但我不确定它是否工作或它是否是最好的方式!
浏览 6
提问于2014-12-13
得票数 4
回答已采纳
1
回答
图形数据库中的图形
算法
执行
、
、
使用图形数据库执行遍历或最短
路径
之类的图形
算法
在哪里?它们是在数据库服务器本身执行还是在客户端执行?在后一种情况下,似乎有必要为每个迭代步骤向服务器发送请求。 Noe4j提供遍历和最短
路径
算法
。是否有其他图形数据库提供额外的最
大流
量
算法
?
浏览 3
提问于2012-02-29
得票数 0
2
回答
检查一个简单的无向图是否是三连通的。
、
、
问题 给出了一个简单的无向图G= (V,E),其中x-V=n=节点数,x-E=m=m=边数,检验G是否三连通.也就是说,在随机删除任意两个边后,G是否保持连通(从每个节点到所有其他节点存在一条
路径
)。
浏览 3
提问于2019-09-13
得票数 1
回答已采纳
1
回答
网络流中的“增长边”
、
、
、
我们得到了一个网络流,以及一个网络中的最
大流
。如果以任意正数增加边的容量,则称为增长边,也会增加最
大流
。 对不对,我是否符合规定的运行时
浏览 4
提问于2018-08-17
得票数 1
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
(七)输出菱形、递归算法
RRT路径规划算法
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
云直播
活动推荐
运营活动
广告
关闭
领券