腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
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
回答已采纳
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
2
回答
有没有真正的单对
最短
路径
算法
?
algorithm
、
shortest-path
今天我遇到了这个词“单对
最短
路径
问题”。我想知道对加权图是否存在单对
最短
路径
算法
。我的推理可能有缺陷,但我想,如果你想找到A和Z之间的
最短
路径
,你绝对必须知道从A到B,C,
D
,……的
最短
路径
。Y.如果你不知道后者,你就无法确定你的道路实际上是
最短
的。因此,对于我来说,任何
最短
路径
算法
都必须计算出图中从A到其他顶点的
最短
路
浏览 4
提问于2017-03-30
得票数 10
回答已采纳
4
回答
Bellman
算法
能有任意的边序吗?
algorithm
、
graph
、
dynamic-programming
、
shortest-path
、
bellman-ford
我刚刚开始学习新的
算法
,但是当我读到极客们关于极客的行李员福特
算法
时,我被困住了:- 让我们用下面的例子图来理解<e
浏览 1
提问于2017-01-20
得票数 4
1
回答
Dijkstra
算法
不产生
最短
路径
?
algorithm
、
graph-theory
、
shortest-path
、
dijkstra
我正在使用Dijkstra
算法
解决
最短
路径
问题。我遇到了麻烦,因为
算法
应该提供
最短
路径
,但在运行该
算法
后,我手动获得了一条
最短
路径
。这只是这个
算法
的副产品吗?我尝试生成的
路径
来自-> z这是我应用
算法
得到的
路径
,在我访问的每个顶点上进行
最短
距离的跳跃: 2 4 2 2 1 2 1 1
浏览 3
提问于2012-04-21
得票数 2
回答已采纳
1
回答
通过特定顶点查找
路径
的
算法
python
、
algorithm
、
graph-theory
、
dijkstra
、
path-finding
我正在寻找一种从源顶点(S)到经过图中另一个特定顶点(X)的目标顶点(
D
)的无目标
路径
(最好是
最短
路径
,但不一定是
最短
路径
)。现在,在向我指出之前,我想说这个解忽略了从S到X的
最短
路径
已经包含
D
的情况,在我应用这个
算法
时,这是一个可能的场景。在这种情况下,你会如何解决这个问题?我尝试的是在Yen的K
最短
路径
算法
的结果中寻找这样的
路径
的天真尝试。但
浏览 3
提问于2020-01-16
得票数 0
回答已采纳
3
回答
全对
最短
路径
,领带断裂
algorithm
、
graph
、
shortest-path
、
tie
要做到这一点,我必须找到ASSSP (所有单一源
最短
路径
)。在创建程序时,我意识到最终我将有联系(从源到目的地的距离相同,但
路径
不同)。这使我想到了这个问题。我该如何解决这些关系?让我做一个小小的示范性图: / \ \ /现在假设A节点是我们希望找到ASSSP的源。可见,有两条
路径
(A->B->
D
和A->C->
D
),bot的长度相同,两者
最短
。现在我应该选择哪一个,
浏览 2
提问于2012-07-11
得票数 2
回答已采纳
2
回答
行李员福特和一个奥林匹克竞赛的问题?
algorithm
、
data-structures
、
graph
、
graph-theory
、
shortest-path
我们知道贝尔曼-福特
算法
在每一步中检查所有的边,并且对于每条边,然后更新
d
(v),使得w(u,v)是边(u, v)的权重,
d
(u)是顶点u的最佳发现
路径
的长度。如果在一个步骤中我们有了no update for vertexes,
算法
就是terminates。假设在k < n迭代完成后,这个
算法
用于在具有n个顶点的图G中找到从顶点s到所有
最短
路径
的所有
最短<
浏览 34
提问于2015-04-09
得票数 14
回答已采纳
4
回答
寻找第k条
最短
路径
?
algorithm
、
graph
、
shortest-path
寻找图中两点之间的
最短
路径
是一个经典的
算法
问题,有许多好的答案(,等)。我的问题是,是否有一种有效的
算法
,在给定一个有向加权图、一对节点s和t以及一个值k的情况下,找到s和t之间的第k条
最短
路径
。如果有多条相同长度的
路径
都与第k条
最短
路径
相同,则
算法
可以返回其中任何一条
路径
。 我怀疑这个
算法
可能可以在多项式时间内完成,尽管我知道可能会减少,这将使其成为NP困难。有没有人知道这样一种
浏览 1
提问于2011-08-27
得票数 28
回答已采纳
2
回答
使用dijkstra从队列中弹出
最短
路径
的节点。
algorithm
、
graph
、
routing
、
openstreetmap
、
dijkstra
我使用适当实现的dijkstra
算法
计算出
最短
路径
。它通过B,C,
D
和E从A到F,所以整个
最短
路径
是A,B,C,
D
,E,F。
浏览 2
提问于2015-08-28
得票数 0
回答已采纳
1
回答
一个接受图的*
算法
python
、
shortest-path
、
dijkstra
、
a-star
我正在做一个项目,在这个项目中,我需要一个
最短
路径
算法
来找到
最短
路径
。目前我正在使用David Eppstein的Dijkstra
算法
实现,但由于图的大性质(大约360万个节点),找到这条
最短
路径
可能需要几乎一分钟的时间。我知道A*
算法
运行得更快,但我发现的i的所有实现都是基于网格样式而不是图形样式。示例图如下所示: "B&quo
浏览 1
提问于2012-11-30
得票数 2
4
回答
最佳
最短
路径
算法
algorithm
、
shortest-path
“弗洛伊德-沃尔”
算法
“和”Dijkstra的
算法
“”之间有什么区别,哪种
算法
是图中
最短
路径
的最佳选择?我需要计算网络中所有对之间的
最短
路径
,并将结果保存到一个数组中,如下所示:A 0 10 15 5 20C 15 5 0 10 15
D
5 5 10
浏览 20
提问于2009-12-04
得票数 27
回答已采纳
2
回答
有向图所有路的最小权边
algorithm
、
directed-graph
给定一个边权为-ve或+ve的有向图,找到从顶点s到顶点
d
的所有
路径
的最小权边的
算法
是什么?
浏览 0
提问于2017-11-13
得票数 0
1
回答
用Dijkstra
算法
求解地铁换乘时间
最短
路径
java
、
algorithm
问题是在地铁中找到从起点到目的地的
最短
路径
。地铁数据提供了每个节点与其线路之间所用的时间。每次换乘(换线)都需要5分钟。 我试着用Dijkstra的
算法
编写这个
算法
。Dijkstra和这个问题的主要区别是这个问题有可能改变那些已经计算的节点中的
最短
路径
(将它们放在集合S中)。 例如,有A,B,C,
D
,E节点。我想找一条从A到E的
最短
路径
。C -> E: 2 minutes 在这种情况下,Dijkstra
算法
将首
浏览 89
提问于2020-06-15
得票数 0
1
回答
通过给定集合的两个顶点之间的最小
路径
algorithm
、
data-structures
、
graph-theory
、
graph-algorithm
假设我有一个源节点S、目标节点
D
和由中间节点P1、P2、P3、…组成的集合A边加权无向图中的。我想找到顶点Pi∈A 最小化dist(S,Pi)+dist(
D
,Pi)?此外,从S到
D
的总体
路径
应该只包含一个从集合A到集合A的节点。我不想用蛮力的方法。
浏览 0
提问于2014-04-09
得票数 1
1
回答
找到一条从A到B的
最短
路径
最大的边
algorithm
、
graph
、
shortest-path
和顶点A和B,求出从A到B的
最短
路径
最大的边。 候选边是虚线。从A到B的
最短
路径
是A -> C ->
D
-> G -> B(成本7)。但是对于边(
D
,B),
最短
路径
是A -> C ->
D
-> B(代价6),因此
算法
应该返回(
D
,B)。我想出了一个蛮力的解决方案O((x=1,2)^2 log
浏览 4
提问于2014-10-06
得票数 3
1
回答
多源多目标
最短
路径
问题
algorithm
、
graph-theory
、
path-finding
、
weighted-graph
我试图找出从所有源节点到任何一个目标节点的
最短
路径
的最优方法,从而在加权图中得到最小的权重。所有节点都是源节点或目标节点。所以图我们有一个图,A,B,C作为源节点,
D
,E,F作为目标节点。A,B,C必须找到任何一个恰好有
最短
路径
的目标节点的
最短
路径
。简单的解决办法是使用Dijkstra
算法
或类似的方法,首先找到从A到
D
的
最短
路径
,然后从A到E等,然后比较每条
最短
路径</em
浏览 4
提问于2022-11-05
得票数 0
2
回答
如何找到通过一组集合的
最短
路径
?
algorithm
、
graph-theory
、
set-theory
我有一个
算法
问题,其中我有许多无序元素集,我需要找到通过所有这些集合的
最短
路径
(集合的有序组合)。可能有上千套。例如,假设有以下4个无序集:B=cd
D
=defiP=CADB=habcgdeficd注意,集合可以与
路径
中的相邻集合共享元素!还可能存在属于不同集合的重复元素(如上面的示例:'c‘和'
d
’在P中被复制,方法是向中添加B )。
浏览 0
提问于2019-02-14
得票数 1
回答已采纳
1
回答
行李员福特和图G的一些事实?
math
、
graph
、
graph-theory
、
shortest-path
、
bellman-ford
我们知道贝尔曼-福特
算法
检查每一步的所有边,如果每一条边, 然后
d
(v)被更新,使得w(u,v)是边(u,v)的权重,
d
(u)是顶点u的最佳查找
路径
的长度。如果在一个步骤中我们没有更新顶点,
算法
就会终止。利用该
算法
,在s迭代完成后,在图G中求出图G中n顶点的所有
最短
路径
,下列哪一条是正确的?1)来自s的所有
最短
路径
中的边数最多为k
浏览 0
提问于2015-03-28
得票数 0
1
回答
具有最小费用下界约束的单源
最短
路径
algorithm
、
graph-algorithm
问题描述:我知道有了这个限制,像Bellman ford这样的传统SSSP
算法
不能正常工作。我该如何为这个问题找到最有效的
算法
呢?
浏览 1
提问于2017-10-25
得票数 2
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
图的最短路径算法-Floyd算法-弗洛伊德算法
计量地理学 最短路径算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券