腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(5962)
视频
沙龙
1
回答
最短
路径
的最
大流
算法
?
、
在这种
算法
上有资源吗?我有一个无权图(所有边到一个容量更准确),我想找到源顶点和汇顶点之间的所有不同
路径
(所有可能的
路径
,没有人与另一个顶点共享),所以我想到了最
大流
问题和algo,但问题是我想要一个algo,它允许我拥有所有
最短
的不同
路径
由于最
大流
algo只是使用BFS或残差图中的某些内容进行搜索,因此它会随机增加我的流量(由于最
大流
的权重,最
大流
algo的每一次迭代都会增加我的流量,这对应于寻找一条新的不同
路径
)
浏览 0
提问于2018-07-20
得票数 0
回答已采纳
1
回答
图形数据库中的图形
算法
执行
、
、
使用图形数据库执行遍历或
最短
路径
之类的图形
算法
在哪里?它们是在数据库服务器本身执行还是在客户端执行?在后一种情况下,似乎有必要为每个迭代步骤向服务器发送请求。 Noe4j提供遍历和
最短
路径
算法
。是否有其他图形数据库提供额外的最
大流
量
算法
?
浏览 3
提问于2012-02-29
得票数 0
1
回答
确定最小边数E*,使得所有这些边的容量增加会导致最
大流
量的增加
、
、
在我们运行FF
算法
并得到残差grpah Gf和min-cut (S,T)之后,这是我的方法。(1)使用BFS找出到u的部分增广
路径
s和从v到t的所有部分增广
路径
。如果这两条部分增广
路径
都存在。找到从交叉边到t的
最短
路径
,这个距离+1(交叉边)将是我们的最小值。在O(E*log(V))时间内
浏览 3
提问于2017-12-10
得票数 0
1
回答
图中具有特定长度的顶点不相交
路径
、
、
、
输出: true,如果至少有两个两个顶点从s到t的最大
路径
长度k的不相交
路径
。否则-返回false。我的想法是分配每个边容量=1,并找到最
大流
。如果最
大流
量为>= 2,则返回true。但是,最
大流
搜索
最短
的增强
路径
,这并不总是最优的解决方案,如果你需要2个或更多的
路径
。有人有解决这个问题的
算法
吗?
浏览 3
提问于2021-09-22
得票数 0
回答已采纳
2
回答
C#通用图搜索框架
、
、
算法
重复了很多次。每次,唯一真正的区别是我正在搜索的实际搜索状态,以及如何从现有状态生成新状态。真的存在这样的东西吗?我什么也找不到。
浏览 0
提问于2010-12-02
得票数 4
回答已采纳
2
回答
如何计算具有非凸多边形的欧氏环境中的
最短
路径
?
有人能给出关于在非凸多边形为障碍物的欧氏空间中
求
最短
路径
的论文或
算法
吗?
浏览 0
提问于2010-09-27
得票数 10
1
回答
Edmonds-Karp
算法
的复杂性
、
、
Edmonds-Karp
算法
表示,每次增加
最短
路径
时,源s和宿t之间的
最短
距离t单调增加。在这个假设下,源s和宿T之间的距离t将不会大于|V| - 1。我认为这意味着在|V| -1增强之后,源S和宿T之间将不再有
路径
。如果这是真的,那么寻找最
大流
的复杂度将是(|V| - 1) * E。 我知道我错误地假设了上面的某些东西。但是不能理解它是什么。
浏览 17
提问于2017-03-14
得票数 0
4
回答
用于图形的Javascript库(在数学意义上)
、
、
、
是否有任何重要的Javascript库用于图形和网络表示,以及通用
算法
、优化等?我正在想象类似于的东西,具有图搜索、
最短
路径
、最
大流
等功能。
浏览 0
提问于2011-06-23
得票数 13
回答已采纳
2
回答
R中有向多图的绘制
、
、
因此,我想问您,哪个包具有
最
简单的学习曲线,并且满足以下要求: 试图在两个顶点之间画出多条边,这样它们就不会重叠。(不需要任何图
算法
,如链接分析、
最短
路径
、最
大流
等,但如果存在,则很好)
浏览 2
提问于2011-04-04
得票数 5
回答已采纳
3
回答
在有向图上有下界但没有上界的情况下,我应该使用什么
算法
来
求
最小流?
、
、
、
在有向图上有下界而没有上界的情况下,我应该使用什么
算法
来
求
最小流?例如这个简单的例子:在文献中,这是一个最小成本流问题。在文献中,问题是:寻找单源/单汇有向无圈图的最小成本流的最佳
算法
是什么,其中每个边都有无限的容量,流上的非零下界,以及与流的下界相等的成本。然而,我的直觉是,没有流的上界,即具有无限电容的边,使问题更容易解决,所以我想知道是否有一种专门针对这种情况的
算法
,使用比单纯形方法et更多的“图”技术。阿尔。我的意思是,如果所有的成本和下限都是1,如上面所示.然后,我们正在寻找一种流,它覆盖所
浏览 7
提问于2013-09-03
得票数 11
回答已采纳
1
回答
Dijkstra
算法
是对称的吗?
、
在
求
正权图中
最短
路径
的Dijkstra
算法
中,会出现路由A -> B不等于路由B -> A的情况吗?(A和B是图形上的顶点)。你能举个例子吗?
浏览 38
提问于2019-10-18
得票数 0
回答已采纳
1
回答
最
大流
-最小割集定理
、
我理解Ford-Fulkerson
求
最
大流
的方法,但我很难理解min如何给出最
大流
的值。 最
大流
-最小切割定理指出,从源到汇的最
大流
量等于最小切割的值。如果容量最小,就意味着存在容量较高的增强
路径
,那么为什么容量较低的
路径
会出现最
大流
量?作者所说的容量是指residual capacity吗?因为这一切都有意义。
浏览 2
提问于2016-06-24
得票数 2
回答已采纳
1
回答
在O(|E|)迭代内终止的Ford-Fulkerson
算法
,而不考虑寻找增广
路径
的时间复杂度
、
、
福特Fulkerson
算法
将在O(|E|f)时间内运行,其中f是最
大流
;但是,是否有方法使其运行O(|E|)?让它运行少于O(|E|f)的解决方案之一是选择一条允许流量最大增加的扩充
路径
,使用与使用加权
最短
路径
问题等查找
路径
相关的东西,但我能保证它在O(|E|)时间运行吗?基本上忽略了寻找扩充
路径
所需的时间复杂度(即,无论
算法
是什么,让复杂度为O(1))。 如果没有这样的方法,那么反例是什么?如果是,我需要使用什么方法?
浏览 4
提问于2014-04-13
得票数 3
1
回答
通过最
大流
约束在未加权图中查找shortestS
路径
、
、
在这里,我遇到了一个最
大流
量和
最短
路径
之间的问题,因为两条
路径
之间可能存在一些捷径,有时如果我只有一只或几只蚂蚁,最好只走一条
路径
(走捷径),并以单文件的形式发送我的蚂蚁,但在一定数量的蚂蚁中,最好采用两条
路径
到目前为止,我已经找到了一些很好的
算法
来测试
最短
路径
,但他们总是给我错误的答案,因为他们可以找到阻塞流,这意味着采用一条
最短
路径
而不是两条本来可以更好的
路径
,为了避免这个问题
浏览 0
提问于2018-07-19
得票数 0
1
回答
数据结构中MaxFlow问题的
路径
选择是否有限制?
、
、
在下面的最
大流
问题中,
算法
首先可以选择S-A-D-T
路径
。在这种情况下,
算法
将不再看到任何增强
路径
,因此它将生成4作为最
大流
的答案。但是,如果
算法
首先选择任何其他
路径
,则会看到最
大流
变为5。
浏览 11
提问于2021-12-04
得票数 0
1
回答
从一个未加权的无向图计算另一个具有精确长度l的边的图
、
、
、
我想出了一个解决方案,在每个顶点上使用深度优先搜索来搜索每个V中的每个分支,直到我从每个顶点找到
路径
长度为l的所有顶点。这给出了O(V^(l+1))的运行时,当然,这不是最优的解决方案。
浏览 2
提问于2012-11-11
得票数 0
回答已采纳
1
回答
在半边DS中逼近大地测量,我如何改进我的网格以获得良好的逼近
、
、
、
、
我在任意网格上实现了吉卜斯特的
最短
路径
算法
来逼近大地测量。贾克斯特拉的作品,但我注意到一个固有的问题,我的网格离散化。📷📷这是我目前的
求
精
算法
,它是
最
简单的/标准的人脸细分。现在考虑一个测地线在两点上的近似:蓝色点是我认为实际测地线与边缘相交的地方,离近似测地线穿过的地方很远。然而,这条道路并没有错。因此,就贾克斯特拉的情况而言,一条一直往下再到左边的
路径
,其长度与一条在楼梯模式中对角的
路径
是相
浏览 0
提问于2020-07-21
得票数 1
回答已采纳
1
回答
计算机视觉中使用图论中的优化方法的问题?
、
、
我应该做一个关于图的优化
算法
的演讲。另一方面,我对计算机视觉也很感兴趣。我希望在我的演示文稿中将这两者结合起来。你能推荐一些计算机视觉中的主题,这些主题可以通过图论中的优化方法来解决(例如
最短
路径
,最
大流
,匹配等)?越新越好。
浏览 20
提问于2020-04-07
得票数 0
1
回答
具有权值1的图中的Ford-Fulkerson
算法
、
在最
大流
问题中,当我应用ford-fulkerson
算法
寻找最
大流
时,如果图的所有链接都有权重1,则最
大流
将是我在ford fulkerson
算法
中找到的
路径
数,对吗?我是说,dfs
路径
的数目。
浏览 4
提问于2014-04-17
得票数 1
回答已采纳
1
回答
连续空间
最短
路径
、
、
、
我需要一个
最短
路径
算法
来控制一个真实的机器人。 假设我有一个矩阵形式的环境地图,其中1是一个障碍,0是自由空间。如果我使用传统的
最短
路径
算法
,比如A*,那就给了我曼哈顿距离
最短
的
路径
。所以离实际
最短
的路很远。这个问题的出现,是因为我想不出一条对角线比两条直线更好地惩罚运动的方法。我可以做一个启发式,让A*先尝试两点之间的欧几里德
最短
路径
,但实际上并不能使欧几里得
最短
路径</
浏览 2
提问于2016-05-15
得票数 4
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
图的最短路径算法-Floyd算法-弗洛伊德算法
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
计量地理学 最短路径算法
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券