腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
Dijkstra
算法
不产生
最短
路径
?
algorithm
、
graph-theory
、
shortest-path
、
dijkstra
我正在使用Dijkstra
算法
解决
最短
路径
问题。我遇到了麻烦,因为
算法
应该提供
最短
路径
,但在运行该
算法
后,我手动获得了一条
最短
路径
。这只是这个
算法
的副产品吗?我尝试生成的
路径
来自-> z这是我应用
算法
得到的
路径
,在我访问的每个顶点上进行
最短
距离的跳跃: 2 4 2 2 1 2 1 1
浏览 3
提问于2012-04-21
得票数 2
回答已采纳
1
回答
边权加倍后的
最短
路径
algorithm
、
graph
、
shortest-path
假设我们有一个加权有向图G,并利用A*搜索或任何其他
最短
路径
算法
在G中找到了顶点u和v之间的
最短
路径
。现在假设我们将G中的所有边权加倍,
最短
路径
会改变吗? weight(
P
浏览 0
提问于2015-04-17
得票数 6
1
回答
找出Neo4j中的两个节点之间是否有一条
路径
的最佳方法是什么?
database
、
neo4j
、
path
我的问题是:像“
最短
路径
”这样的
算法
需要2-4ms才能找到
最短
路径
。"}))RETURN
p
MATCH
p
=(
p
1:Pers
浏览 0
提问于2018-10-20
得票数 0
回答已采纳
2
回答
如何找到通过一组集合的
最短
路径
?
algorithm
、
graph-theory
、
set-theory
我有一个
算法
问题,其中我有许多无序元素集,我需要找到通过所有这些集合的
最短
路径
(集合的有序组合)。可能有上千套。例如,假设有以下4个无序集:B=cdD=defi
P
=CADB=habcgdeficd注意,集合可以与
路径
中的相邻集合共享元素!还可能存在属于不同集合的重复元素(如上面的示例:'c‘和'd’在
P
中被复制,方法
浏览 0
提问于2019-02-14
得票数 1
回答已采纳
4
回答
FInding两个顶点之间的所有
最短
路径
algorithm
、
graph
、
dijkstra
、
shortest-path
给定一个有向图G=(V,E),两个顶点s,t和两个权重函数w1,w2,我需要在<代码>D10</代码>从s到t的所有
最短
路径
中找到w2到s的
最短
路径
。首先,如何找到两个顶点s和t之间的所有
最短
路径
?Dijkstra的
算法
帮助我们找到从一个顶点到每个其他可访问顶点的
最短
路径
,是否可以修改它以获得两个顶点之间的所有
最短
路径
?
浏览 0
提问于2013-05-11
得票数 4
2
回答
在两个顶点之间的无向图中寻找特定的边
algorithm
、
graph
、
graph-theory
我试着用图论写一个抽象的
算法
。 从G.
浏览 3
提问于2014-06-11
得票数 0
回答已采纳
1
回答
在源点和目标点都可以从负循环到达的情况下,是否存在多项式时间
最短
路径
算法
?
algorithm
、
dynamic-programming
、
shortest-path
、
np
我不是要求一个
算法
来检查图中负圈的存在(Bellman Ford或Floyd Warshall可以这样做),而是在图包含至少一个从源顶点可以到达的负圈,并且从负圈可以到达目标顶点的情况下,是否存在多项式时间
算法
来寻找两点之间的
最短
路径
浏览 3
提问于2013-09-02
得票数 2
回答已采纳
2
回答
算法
像Bellman,只适用于多个起点,单一目的地?
algorithm
、
graph
、
graph-algorithm
、
path-finding
、
bellman-ford
像Bellman
算法
和Dijkstra
算法
这样的
算法
存在于寻找从图上的单个起始顶点到每个其他顶点的
最短
路径
。然而,在我编写的
程序
中,起始顶点的变化要比目标顶点更频繁。有什么
算法
做相反的--也就是,给定一个目标顶点,从每个起始点找到
最短
路径
?
浏览 3
提问于2015-02-27
得票数 5
回答已采纳
1
回答
找到一个从顶点s到顶点t的
路径
,该
路径
具有最少的颜色交替数。
graph
、
depth-first-search
、
dijkstra
、
graph-coloring
、
strongly-connected-graph
让我们,不是G中的顶点,找到从s到t的
路径
(如果存在的话),这样沿着这条
路径
的颜色变化的数量是最小的。 使用Dijks
浏览 5
提问于2020-07-12
得票数 1
回答已采纳
1
回答
竞争下的预处理
最短
路径
algorithm
、
graph
、
path
、
shortest-path
、
proof
证明了如果
P
是u与v之间的
最短
路,那么每个子路也是
最短
路。给定连通图,我希望预处理矩阵中每对节点之间的
最短
路径
,这样: 如果x,y在
路径
中,v,那么
路径
,y是
路径
的子
路径
,v。我不知道一个
算法
或一个证明,实际上,我不知道这是否是可确认的。任何想法都是welcome.Thank你。
浏览 2
提问于2016-07-04
得票数 1
2
回答
在给定
最短
路径
的情况下,修改图的边权重的
算法
graph
、
shortest-path
、
weighted
给定一个具有正权重的边、一对节点和节点之间的
路径
的图,什么是最好的
算法
,它将告诉我如何将图的边权重修改到可能的最小程度,以便指定的
路径
成为节点之间的
最短
路径
(由A*计算)?(当然,如果我将
最短
路径
指定为输入,则输出将是“不做任何更改”)。 注意:最小范围是指对边权重所做的总更改。例如,另一个极端(最具破坏性的更改)是将不沿指定
路径
的所有边的权重更改为无穷大,将沿
路径
的边的权重更改为零。
浏览 0
提问于2013-05-29
得票数 4
回答已采纳
1
回答
关于Dijkstra
算法
证明的困惑
algorithm
、
graph
、
shortest-path
、
dijkstra
在证明Dijkstra
算法
正确性的过程中,有一个引理如下: 设u是
最短
路径
P
: s->.>u-> v从s到v,如果d(u) =δ(s,u)和边(u,v)是松弛的,则d(v) =δ(s,v),其中函数δ(x,y )表示从x到y的最小
路径
权重.如果
路径
P
: s->.-> u -> v是从s到v的
最短
路径
,那么根据最优子结构的性质,
P
的子
路径
s->…->u
浏览 0
提问于2019-01-10
得票数 5
1
回答
Dijkstra
算法
:所有
最短
路径
都是非循环的吗?
shortest-path
、
dijkstra
我知道,如果
算法
达到负循环,
算法
就不会终止,如果
路径
包含一个距离大于0的循环,那么它就不是
最短
路径
。 我的问题是,如果存在一个循环距离为0的
最短
路径
会发生什么,
算法
会将该循环包含在
最短
路径
中吗?你会说所有的
最短
路径
都是非循环的吗?
浏览 13
提问于2017-06-20
得票数 0
1
回答
arangoDB中的多
路径
搜索
arangodb
是否有可能在ArangoDB中找到
最短
路径
的许多变体?我需要找到许多变体,比如第一个
路径
距离2,第二个
路径
距离3等等。是否支持向量权重?
浏览 1
提问于2017-10-28
得票数 1
1
回答
Yen的k
最短
路径
算法
algorithms
、
graph
、
path-finding
我目前正在尝试理解Yen的k条
最短
路径
算法
。我以原始论文和维基百科文章为基础,但仍然不明白为什么k> 2是正确的。事实上,我甚至不明白为什么它适用于以下例子:例如,让我们考虑从A到D的3条
最短
路径
,即A -> B -> C -> D(长度3)、A -> B -> F -> D(长度4)和A -> B ->根据我对该
算法
的了解,正确地计算了2条
最短
路径
。然而,第三条
最短
浏览 0
提问于2016-05-01
得票数 2
回答已采纳
1
回答
我混淆了
最短
路径
查找
算法
和图遍历
算法
。
algorithm
、
graph-theory
、
depth-first-search
、
shortest-path
、
path-finding
我的理解是,BFS和DFS是图遍历
算法
,而其他
算法
(如A*和dijkstra )则用于在图的两个节点之间寻找
最短
路径
。但是在一些地方,我认为BFS和DFS也被称为
最短
路径
查找
算法
。请详细说明图遍历
算法
与
最短
路径
查找
算法
的区别。谢谢!
浏览 6
提问于2022-05-06
得票数 0
2
回答
最长简单
路径
algorithm
、
language-agnostic
、
computer-science
、
graph-theory
、
theory
因此,我理解在图中寻找最长的简单
路径
的问题是NP困难的,因为您可以通过将边权重设置为1并查看最长简单
路径
的长度是否等于边的数量来轻松地解决哈密顿电路问题。我的问题是:如果你得到一个图,找到最大边权重m,用m - w替换每个边权重w,并在上面运行标准的
最短
路径
算法
,你会得到什么样的
路径
?这显然不是最长的简单
路径
,因为如果是,那么NP =
P
,我认为这样的东西的证明会更复杂=
P
。
浏览 0
提问于2009-04-04
得票数 9
回答已采纳
1
回答
Bellman
算法
的中间最优性,是正确的吗?
algorithm
、
graph-theory
、
shortest-path
Bellman
算法
是著名的求解任意连通图G(V,E)的单源
最短
路径
问题(SSSPP)的
算法
。该
算法
的基本实现版本,例如:及其,在使用所有边的并行松弛时,根据我的理解,意味着一个有趣的副产品,我称之为“中间最优性属性”(可能对一些应用
程序
(如)非常有用)如下: 经过k次迭代后,在
路径
中的#边约束下,每个节点都从同一源识别出
最短
路径
为<= k。这将保证在简单
最短
路径
存在的前提下,对每个目标节点,
浏览 4
提问于2014-09-12
得票数 0
回答已采纳
2
回答
dijkstra
算法
,对某些节点的
最短
路径
只运行一次(不是两个,不是整个图)。
algorithm
、
graph
、
graph-algorithm
因此,dijkstra
算法
是搜索加权(无负)连通图
最短
路径
的最佳
算法
。Dijkstra
算法
可用于寻找两点/顶点的
最短
路径
。它可以用来寻找所有顶点的
最短
路径
。 问题:我的理解正确吗?它也能用来寻找某些顶点的
最短
路径
吗?例如,图有A,B,C,D,E,F,G,H,I,J,K,我们只对A,B;C,K的
最短
路感兴趣,我们可能只需要一次就能找到两条路吗?
浏览 2
提问于2018-03-12
得票数 1
8
回答
我可以使用哪种
算法
来查找图中的下一个
最短
路径
?
algorithm
、
graph
我想找一个图中2个顶点之间的下一条
最短
路径
,并且这条
路径
有一个正的cost.The,下一条
最短
路径
是允许共享边的
最短
路径
,我可以使用.Which
算法
吗?
浏览 0
提问于2011-02-12
得票数 20
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
图的最短路径算法-Floyd算法-弗洛伊德算法
计量地理学 最短路径算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券