腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
DAG中的
最小
路径
覆盖
、
、
、
我想知道是否存在一个有效的
算法
来计算有向无环图的
最小
路径
覆盖
。请不要将
最小
“
路径
覆盖
”与“顶点不相交的
路径
覆盖
”混淆。对于后者,我知道一个有效的
算法
,使用相应的二部图的最大匹配。当每个顶点可以被多次访问时,是否可以放松相同的
算法
以获得
路径
覆盖
的答案?
浏览 4
提问于2013-06-10
得票数 3
回答已采纳
1
回答
有k个节点的Dijkstra变体?
、
、
、
、
我必须从一个源和目的地找到一个
最小
路径
,其中源和目的地是相同的节点,并且我需要
路径
中
最小
的固定节点数。我想用k节点包含在
最小
路径
中的变体来实现Dijkstra
算法
(在Java中)。(k是要
覆盖
的
最小
节点数)。是对的吗?如有,有何建议予以实施?提前感谢
浏览 1
提问于2016-06-22
得票数 5
回答已采纳
4
回答
哈密顿
路径
与ST的区别
、
、
我正在研究寻找
最小
生成树(在加权图的情况下)和查找图是否有哈密顿
路径
(这取决于哈密顿圈的存在)的
算法
。我把一切都搞砸了。那么哈密顿
路径
和生成树之间有什么区别呢?两者都
覆盖
了图中的所有顶点。虽然我们可以有高效的
算法
来寻找生成树(可能是
最小
生成树),但为什么我们就不能有寻找哈密顿回路的
算法
呢?我们可以一次增加和删除一条边,直到我们到达一个循环,也许我们可以找到哈密顿循环??
浏览 1
提问于2011-07-23
得票数 14
1
回答
寻找最短周期
、
、
基本上,我需要在一个图中有一个
覆盖
所有顶点并返回到源的最短
路径
。只要是最短
路径
,任何顶点的重复都是可以的。 我的
算法
从源开始。我运行dijkstra
算法
来找到最短
路径
。然后我选择
最小
的加权未达顶点,并再次运行dijkstra作为所选顶点作为源,并继续运行,直到所有顶点都完成。然后,从最后一个顶点再次使用dijkstra找到返回原始源的最短
路径
。
浏览 0
提问于2012-10-30
得票数 0
3
回答
Crab图,
算法
,图论,这个网络是如何流动的?
、
、
、
我们的目标是以这样的方式选择这些蟹,使它们
覆盖
的顶点总数最大化。例如。输入1 43 45 85 6
浏览 3
提问于2013-06-05
得票数 6
回答已采纳
3
回答
为什么Kruskal产生的树与Dijkstra不同?
、
、
、
、
有谁能解释为什么Kruskal产生的树与Dijkstra不同?
浏览 2
提问于2013-12-05
得票数 7
回答已采纳
1
回答
最小
化图保持连通性
、
我正在与OpenSG一起工作,并试图找出建筑物中两点之间的
路径
。IntersectAction完成的) 所以我有一个
算法
,它或多或少地做了我想做的事情,但我只是认为这一定是一个众所周知的问题。它不是
最小
顶点
覆盖
,因为例如,如果在<e
浏览 4
提问于2013-04-11
得票数 1
回答已采纳
1
回答
如何在混合有向/无向图中找到欧拉
路径
?
如何找到遍历顶点和边的图中所有边的
路径
,其中一些边是有向的,而另一些则不是?我想要
覆盖
图的
最小
路径
数。 我知道Heirholtz的
算法
,我知道如何将它应用于只有有向边或只有无向边的图。
浏览 17
提问于2019-02-05
得票数 0
3
回答
图的边遍历
算法
,一些边需要,一些可选
、
、
、
在这个图中,有一组必须只
覆盖
一次的边,还有一组除非绝对必要,否则根本不应该
覆盖
的边。我需要找到一组通过图的一条或多条
路径
,这样所有需要的边都只被
覆盖
一次,并且遍历的不需要的边的数量被
最小
化。任何需要的边都不能被一条以上的
路径
穿过,但不需要的边可以被任意数量的
路径
穿过。它不完全是欧拉
路径
,因为有可选的边。每条
路径
的长度受其可
覆盖
的所需边的最大数量的限制,尽管一条
路径
可以
覆盖
任意数量的
浏览 4
提问于2012-03-21
得票数 1
回答已采纳
2
回答
边缘团
覆盖
算法
、
、
、
、
我试图编写一个
算法
来计算输入图(无向和无自循环)的边团
覆盖
数(
覆盖
所有边的
最小
团数)。我的想法是 有谁知道一个更好的方法吗?有标准的
算法
吗?令我惊讶的是,我找不到任何这样的
算法
。
浏览 2
提问于2018-03-06
得票数 3
回答已采纳
2
回答
根据给定的准则寻找图中两个节点之间的
路径
--优化任务
、
、
、
、
我需要根据以下规则在两个给定节点之间找到简单的
路径
(没有循环): 根据给出
浏览 5
提问于2013-08-27
得票数 1
回答已采纳
2
回答
如何找出
最小
封面的数量?
、
、
可能的不同
最小
覆盖
的数目如下 我试过的是: 寻找
最小
覆盖
的
算法
(教科书:“数据库系统的基础”- Elmasri,Navathe): 输入:一组函数依赖项E。如果{ {F - {X→A}∪{ (X - {B}
浏览 1
提问于2019-10-16
得票数 1
2
回答
一种求集合
覆盖
问题
最小
集合
覆盖
的
算法
、
在集合
覆盖
问题中,我们被赋予一个论域U,使得|U|=n和集合S1,……,Sk是U的子集。集合
覆盖
是来自S1,……的一些集合的集合C,Sk,其并集是整个宇宙U。我正在尝试想出一个
算法
,它可以找到
最小
数量的集合
覆盖
,这样我就可以证明,贪婪的集合
覆盖
算法
有时会找到更多的集合。对每个集合重复此操作。1.
覆盖
<-Seti (i=1,,,n) 2.如果一个集合不是任何其他集合的子集,则take将该集合纳入
覆盖
。 但它在某
浏览 5
提问于2010-11-26
得票数 1
回答已采纳
3
回答
构造
覆盖
顶点特定子集的
最小
生成树
、
、
、
我有一个无向,正边权图(V,E),我想要一个
最小
生成树
覆盖
一个顶点的子集k( Steiner树问题)。 我并不是将生成树的大小限制为k个顶点,而是确切地知道在MST中必须包含哪些k个顶点。从整个MST开始,我可以缩小边缘/节点,直到得到包含所有k的
最小
MST为止。我可以使用Prim的
算法
获得整个MST,并在子集k的MST未被破坏的情况下开始删除边缘/节点;或者,我可以使用Floyd获得所有对最短
路径
,并以某种方式合并
路径
。有没有更好的方法来解决这个问题?
浏览 5
提问于2011-10-07
得票数 44
3
回答
判定图G是否含有树状结构的
算法
有向图G的树状结构是有根树,使得从根点到图中的每一个顶点都有一条有向
路径
。给出了一种有效且正确的
算法
来判定图G是否含有树形图,并分析了其时间复杂度。我只能考虑从每个节点运行DFS/BFS,直到其中一个DFS
覆盖
了所有节点。我想过使用
最小
生成树
算法
,但这也只适用于无向图 有没有其他有效的
算法
来解决这个问题?我发现了一个后续问题,对于同样的问题,有一个O(n+m)
算法
,有人能帮我解决吗?
浏览 1
提问于2014-01-07
得票数 5
1
回答
无向图的
最小
加权
路径
树
、
、
我们能给出一个
算法
,使从S到X的
路径
上的边的最大权重
最小
化吗?注意,这不是最短
路径
算法
,因为我们对
最小
化它们的和不感兴趣。 这个
算法
的复杂度是多少?
最小
生成树
算法
(如Prim)是否是该问题的解决方案?
浏览 0
提问于2018-11-14
得票数 0
1
回答
无向加权图中具有
最小
游动边和最大权的
路径
、
、
、
我试着想出一种
算法
来找到一条穿越无向图的
路径
。这不是一条传统的道路,我找不到任何类似这样的事情已经做过的参考资料。我的目标是找到一条具有
最小
游动边的
路径
(顶点之间的跳跃)和这条
路径
的最大权重(流行度在
最小
游走边)。该
算法
首先检查所有具有
最小
游动边的
路径
,然后选择这些
路径
中的哪一条具有最大权重。例如,两个
最小
行程边
路径
是{3->4->5},而{5->6->3}
浏览 6
提问于2022-11-08
得票数 1
1
回答
寻找
最小
生成
路径
的
算法
?
、
受这个漫画的启发 我知道有许多
算法
可以找到加权图的
最小
生成树,但是我一直在努力寻找任何能够找到
最小
生成“
路径
”的
算法
。对于漫画来说,如果我们根据每对关系对每条边进行加权,那么社会最优排列将是
最小
跨越“
路径
”,即一条跨越所有顶点的
路径
。有人能帮忙吗?
浏览 5
提问于2012-05-24
得票数 5
1
回答
有向无圈图的
最小
方差
路径
、
、
、
、
我希望通过具有节点值
最小
方差的图获得
路径
。谢谢你,皮耶罗
浏览 4
提问于2015-04-10
得票数 0
回答已采纳
3
回答
在有向图上有下界但没有上界的情况下,我应该使用什么
算法
来求
最小
流?
、
、
、
在有向图上有下界而没有上界的情况下,我应该使用什么
算法
来求
最小
流?例如这个简单的例子:在文献中,这是一个
最小
成本流问题。在文献中,问题是:寻找单源/单汇有向无圈图的
最小
成本流的最佳
算法
是什么,其中每个边都有无限的容量,流上的非零下界,以及与流的下界相等的成本。我的意思是,如果所有的成本和下限都是1,如上面所示.然后,我们正在寻找一种流,它
覆盖
所有边界,遵守流规则,并且不会在从s到t的任何
路径
中推动过多的流。这感觉就好像不需要对我使用LP求解器,而且
浏览 7
提问于2013-09-03
得票数 11
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
算法:32.最小子串覆盖
RRT路径规划算法
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
算法:44.最小子数组
什么是最小生成树算法?详述最小生成树算法的原理?用C语言实现最小生成树算法。内附完整代码。
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券