腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
UnixPath或WindowsPath在JUnit测试中的应用
java
、
junit
、
nio
我想测试一个方法,它查找两个
路径
中
最长
、公共的子
路径
()。由于程序应该在Windows和
Linux
下运行,我想用
Linux
路径
创建测试,用Windows
路径
创建其他测试。
问题
是,Windows测试只在Windows环境中通过,而在
Linux
环境中失败。对于
Linux
测试,情况正好相反。 在进行实际测试之前,我可以通过检查操作系统来缓解这个
问题
。例如:org.junit.Assume.assumeTr
浏览 2
提问于2021-12-16
得票数 0
回答已采纳
2
回答
为什么在图中找到
最长
的
路径
是NP困难的?
algorithm
、
graph-algorithm
这个提到: 在转型之后,我们有这样的情况: -G有一个负循环,在这种情况下,无法找到-G中的最短
路径
。-G不存
浏览 2
提问于2018-11-20
得票数 7
回答已采纳
1
回答
求解
最长
路径
长度。我的解决方案正确吗?
algorithm
、
longest-path
这是来自CLRS的
问题
将优化
问题
最长
路径
长度定义为将无向图的每个实例和两个顶点与两个顶点之间
最长
简单
路径
中的边数相关联的关系。定义决策
问题
最长
路径
= {:G=(V,E)是一个无向图,u,v包含在V中,k >= 0是一个整数,并且在G中存在一条从u到v的至少包含k条边的简单
路径
}。证明了最优化
问题
最长
路长度在多项式时间内可解的充要条件是
最长
路包含在P中。所以
浏览 2
提问于2011-12-09
得票数 3
回答已采纳
1
回答
为什么Bellman-Ford不能用于单源
最长
路径
?
algorithm
、
shortest-path
、
dijkstra
、
bellman-ford
、
longest-path
Dijkstra不能用于
最长
路径
,因为它使用了当前最短
路径
肯定比其他
路径
短的属性。当然,假设没有负边权重,这是正确的。这也是为什么
最长
路径
在Dijkstra上不起作用的原因,因为当前的
最长
路径
不能保证以后不会有另一条更长的
路径
采用更大的值。 另一方面,贝尔曼福特提供了负重的灵活性,但性能较差。这就是为什么我感到困惑的原因--为什么Bellman Ford不能用于单源
最长
路径
问题
(N
浏览 34
提问于2020-08-25
得票数 2
回答已采纳
1
回答
树中
最长
路径
的公共段
algorithm
、
tree
我遇到了一个编程
问题
我们需要返回理想
路径
中
最长
的公共段中的最短部分。理想
路径
是在属于上述集合S的顶点上开始和终止的
路径
。不能保证公共
路径
的存在。我知道在线性时间内找到树中
最长
的
路径
,我们也可以很容易地将它扩展到理想
路径
的情况,但是经典的2 dfs算法并不能帮助找到
最长
的
路径
,而只帮助找到
最长
的<em
浏览 1
提问于2013-03-07
得票数 1
2
回答
加权的
最长
路径
是<= x(加权的无向图)
algorithm
、
graph
、
path
我想不出任何算法可以找到
最长
的
路径
,小于或等于某个x变量。使用Dijkstra的算法,我可以很容易地得到
最长
路径
,但是我不确定是否可以在我的
问题
中使用它。
浏览 1
提问于2013-01-06
得票数 1
2
回答
最长
简单
路径
algorithm
、
language-agnostic
、
computer-science
、
graph-theory
、
theory
因此,我理解在图中寻找
最长
的简单
路径
的
问题
是NP困难的,因为您可以通过将边权重设置为1并查看
最长
简单
路径
的长度是否等于边的数量来轻松地解决哈密顿电路
问题
。我的
问题
是:如果你得到一个图,找到最大边权重m,用m - w替换每个边权重w,并在上面运行标准的最短
路径
算法,你会得到什么样的
路径
?这显然不是
最长
的简单
路径
,因为如果是,那么NP = P,我认为这样的东西的证明会更复杂=P。
浏览 0
提问于2009-04-04
得票数 9
回答已采纳
1
回答
最宽
路径
与
最长
路径
问题
的基本区别
graph
、
theory
、
longest-path
最宽
路径
和
最长
路径
问题
有什么区别?更具体地说,为什么前者可以通过找到最大生成树来解决,而后者却不能。我知道在绘制最大生成树时,很明显,它不一定包含
最长
的
路径
,但我无法思考这两个
问题
之间的区别,这两个
问题
使这一事实成为现实。 谢谢。
浏览 2
提问于2014-08-12
得票数 1
回答已采纳
1
回答
证明具有负边权重的
最长
路径
是NP-Hard的
np
、
longest-path
我知道以前也有人问过类似的
问题
,网上有大量的资源,但我有一个略有不同的
问题
。我理解从HAM
路径
到
最长
路径
的缩减。它依赖于两者都需要使用n-1个边。但是,如果在
最长
路径
中给定的图的边权重为负值,会发生什么呢?那么
最长
的
路径
可以有n-2条边,但HAM仍然有n-1条边。 对于这个
问题
,有没有不同的简化方法?我是不是遗漏了什么?
浏览 13
提问于2018-12-05
得票数 1
2
回答
为什么我们不能把
最长
的路变成最短的图呢?
algorithm
今天,我阅读了关于算法的介绍,该算法在加权有向图中询问通过两个顶点的
最长
简单
路径
是什么。作者用一个很好的例子说明了动态规划对于
最长
路径
问题
是失败的,因为没有一个很好的最优结构总是伴随着一个最优子结构。有人评论说这个
问题
实际上是NP-完全的。所以这一定很难。 下面是我的
问题
:与其给每一条边分配一个正的权重k>0,不如简单地用权重k给每个边分配负权重呢?那么每条“
最长
路径
”都会自动成为最短
路径
,如果在最短
路
浏览 3
提问于2015-02-23
得票数 0
2
回答
无向图的
最长
距离
algorithm
、
graph
、
floyd-warshall
、
undirected-graph
、
longest-path
然后我找出最短的
路径
。 但它并没有给我正确的输出。有人能指出我正在犯的错误吗。
浏览 10
提问于2017-02-28
得票数 1
1
回答
如何在无向图中找到最短
路径
和
最长
路径
?
algorithm
、
graph
、
depth-first-search
、
breadth-first-search
、
longest-path
我有一个关于如何在具有简单边的无向图中找到最短
路径
和
最长
路径
的一般
问题
,其中边没有权重。我们需要使用DFS算法来寻找图中的
最长
路径
,而我们需要使用BFS算法来寻找图中的最短
路径
,这是一个正确的结论吗?我知道当我们使用BFS时,我们逐层访问节点,我们可以使用它来寻找最短
路径
(这可能就是为什么Dijkstra是基于BFS或类似于BFS的原因)。但我看不出我们如何有效地找到使用BFS的
最长
路径
。此外,我理解使用DFS查找<
浏览 42
提问于2021-03-26
得票数 0
1
回答
有向无圈图中的
最长
路
algorithm
、
directed-acyclic-graphs
、
longest-path
如何在没有权重的DAG中找到
最长
路径
? 我知道如果DAG是按拓扑排序的,那么从A到B的
最长
路径
可以在线性时间内找到,但我需要在所有图中找到
最长
路径
。有没有比搜索所有顶点对之间的
最长
路径
(即O(n^3))更快的方法?
浏览 0
提问于2013-04-07
得票数 1
回答已采纳
1
回答
从随机顶点到
最长
路径
端点的
最长
距离
algorithm
、
graph
、
graph-algorithm
、
depth-first-search
、
breadth-first-search
我有一个树状图/结构,顶点和城市一样,我们假设
最长
的
路径
是从's‘和't’。现在,我想证明,从任何其他城市的
最长
的
路径
(假设'w')结束在s或t。我所想的是两种不同的情况:如果w在
最长
路径
之外,则为。这就是我困惑的地方。如果我运行一个DFS,我如何保证它将给
浏览 3
提问于2021-09-12
得票数 0
1
回答
BFS - WordChain/Wordladder
algorithm
、
search
、
graph
、
nodes
、
breadth-first-search
我需要帮助解决一个
问题
。我想找出某个词和某个给定词尾之间
最长
的最短
路径
。所有单词的长度都是4。我有一个图,其中每个节点代表一个单词,每个单词在一个位置上的不同是连接的。我有一个正确的函数,它找到
最长
的最短
路径
,但它从单词列表中的每个单词开始,然后从单词列表中的每个单词执行BFS。 如果给出一些结尾词,我如何才能找到到给定词尾的最短
路径
的单词?所谓
最长
的最短
路径
,我指的是从所有单词到结束词的最短
路径
,以及其中
最长
的<e
浏览 1
提问于2013-04-19
得票数 1
回答已采纳
3
回答
这个在有向无循环图上寻找最大
路径
的算法是如何命名的?
algorithm
、
graph
、
directed-acyclic-graphs
一段时间以来,我一直在使用一个复杂度为O(V + E)的算法来寻找从点A到点B的有向无向图上的最大
路径
,这包括进行泛洪填充,以找出哪些节点可以从节点A访问,以及每个节点有多少个“父节点”(来自其他节点的边我告诉了一位信息学教授,他只是称它为“DAG上的最大
路径
”,但当你说“我用Fenwick树解决了第一个
问题
,第二个用Dijkstra解决了第一个
问题
,第三个
问题
用最大
路径
解决了”时,这听起来不太好。
浏览 0
提问于2010-05-17
得票数 5
回答已采纳
1
回答
在DAG中求正负权重
最长
路径
的一个例子
algorithm
、
directed-acyclic-graphs
我读到关键
路径
方法使用的是具有正权值的
最长
路径
方法,它用于调度一组项目活动(时间值必须是正的)。 在我的例子中,我需要找到DAG中正负权重的
最长
路径
。我能用这个
问题
做什么?我需要一个例子。
浏览 1
提问于2015-06-17
得票数 2
回答已采纳
1
回答
特殊方格子图中的长
路径
算法
algorithm
、
path-finding
、
a-star
、
longest-path
在A和B之间的D中,是否有一种简单、直接的算法来寻找合理长的自避免
路径
? 我发现了一些文献,指的是寻找绝对
最长
的
路径
,以及次优算法,这些算法虽然执行得很好,但看起来非常复杂。我在这里的唯一想法是计算出通过A*的最短
路径
,然后通过“折叠”横向扭曲它来填充尽可能多的空间,但我不确定这是否是一个好主意。
浏览 0
提问于2016-04-14
得票数 1
1
回答
图-非简单
路径
,
最长
路径
java
、
algorithm
、
optimization
、
graph
、
shortest-path
我试图在图中求出
最长
的
路径
。即使在中,它也提到我们试图找到
最长
的简单
路径
。非简单
路径
是顶点/边可以重复的
路径
.我可以认为任何一个周期或电路是非简单的
路径
。
问题
: 因为在非简单
路径
中有一个循环,
最长
的非简单
路径
或
浏览 6
提问于2019-12-08
得票数 0
回答已采纳
1
回答
精确遍历n条边,从源节点到目标节点,找到
最长
的
路径
。
algorithm
、
graph
现在,我们到达目标节点的
路径
可以有周期。如何使和最大化?
浏览 3
提问于2017-08-20
得票数 0
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
【大网管】Linux路径展开
车辆路径问题
最长上升子序列问题
Linux配置文件路径大全
Windows路径转换为Msys2表示的Linux路径
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券