腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
有没有真正的单对
最短
路径
算法
?
、
今天我遇到了这个词“单对
最短
路径
问题”。我想知道对加权图是否存在单对
最短
路径
算法
。我的推理可能有缺陷,但我想,如果你想找到A和Z之间的
最短
路径
,你绝对必须知道从A到B,C,D,……的
最短
路径
。Y.如果你不知道后者,你就无法确定你的道路
实际
上是
最短
的。因此,对于我来说,任何
最短
路径
算法
都必须计算出图中从A到其他顶点的
最短
路
浏览 4
提问于2017-03-30
得票数 10
回答已采纳
3
回答
是Bellman“所有对”还是“来自一个节点”
最短
路径
的结果?/是否有一个全对Bellman版本?
、
、
我最近正在学习图形
算法
,在我的大学里,我们被教导说,Bellman的结果是一个从所有节点到所有其他节点的距离表(所有对
最短
路径
)。然而,我不明白这个
算法
是如何实现的,我试图通过观看YouTube视频和查找维基百科中的定义来理解它……我无法找到描述该
算法
的资源,其结果将是所有对
最短
路径
表,但只能“从一个节点到所有其他节点对Bellman
算法
进行调整以实现所有对
最短
路径
表,还是我的大学讲师在这方面完全错
浏览 8
提问于2017-07-16
得票数 1
回答已采纳
2
回答
弗洛伊德·沃肖尔:计算每个顶点对的top-k
最短
路径
、
、
、
在弗洛伊德-沃肖尔
算法
中,为任何一对顶点计算
最短
路径
成本。额外的记账使我们能够将
实际
路径
(顶点列表)保持在
最短
路径
上。我如何扩展Floyd-Warshall,以便对任何一对顶点,都能找到top-K
最短
路径
?例如,对于K=3,结果将是计算并维护3条
最短
路径
? 我一直在使用来自Sedgewick的。
浏览 6
提问于2014-08-23
得票数 0
3
回答
iOS上的dijkstra
算法
、
、
我使用经度/经度和Haversine
算法
来确定两点之间的距离。接下来,我想使用dijkstra的
最短
路径
算法
来查找源和目标位置之间的
最短
路径
(源和目标由用户选择)我正在寻找一些客观的C代码,将执行此搜索。
浏览 0
提问于2012-06-07
得票数 8
2
回答
从单个源到所有其他节点在生成树中寻找
最短
路径
的最佳
算法
、
、
、
、
如果我知道给定的图
实际
上是一棵生成树,即每一对顶点之间只有一条
路径
,那么如何才能找到从每个顶点到每个顶点的
最短
路径
?我想要最理想的解决方案。我知道Dijkstra的
算法
,但它非常复杂。我基本上想知道每个顶点从一个源的距离和
路径
。考虑到它是一棵生成树,那么它的最佳和最优解是什么?另外,如果图
实际
上是生成树,那么请告诉我是否有什么不同的方法可以找到所有对
最短
路径
,而不是多次使用单源
最短
路径
算法<
浏览 6
提问于2014-12-11
得票数 0
回答已采纳
1
回答
连续空间
最短
路径
、
、
、
我需要一个
最短
路径
算法
来控制一个真实的机器人。 假设我有一个矩阵形式的环境地图,其中1是一个障碍,0是自由空间。如果我使用传统的
最短
路径
算法
,比如A*,那就给了我曼哈顿距离
最短
的
路径
。所以离
实际
最短
的路很远。这个问题的出现,是因为我想不出一条对角线比两条直线更好地惩罚运动的方法。我可以做一个启发式,让A*先尝试两点之间的欧几里德
最短
路径
,但
实际
上并不能使欧几里得<
浏览 2
提问于2016-05-15
得票数 4
回答已采纳
3
回答
全对
最短
路径
,领带断裂
、
、
、
要做到这一点,我必须找到ASSSP (所有单一源
最短
路径
)。在创建程序时,我意识到最终我将有联系(从源到目的地的距离相同,但
路径
不同)。这使我想到了这个问题。我该如何解决这些关系?可见,有两条
路径
(A->B->D和A->C->D),bot的长度相同,两者
最短
。现在我应该选择哪一个,在什么条件下?随机断系器(问题) 如果我使用随机断带器,如要找到的第一个,则标记为
最短
路径
(程序是分布的,因此该解决方案将以随机方式工作)。然后,我将对中间的中心性产生
浏览 2
提问于2012-07-11
得票数 2
回答已采纳
2
回答
boost
最短
路径
查找
算法
、
、
、
、
我想在随机图中找到
最短
路径
。我使用boost图形库。据我所知,我需要使用点之间的现有距离来构建图形。之后我需要使用一些
算法
..。正如我所看到的,Dijkstra的
算法
实际
上是找到从1点到其他点的所有
路径
。(应该慢慢来?)怎样才能找到两点之间的
最短
路径
?我在bgl文件夹中看到了许多
最短
路径
算法
头,但是我没有找到如何使用它们的例子。 此外,我可以预先计算一些东西
浏览 5
提问于2015-05-20
得票数 0
回答已采纳
1
回答
多源多目标
最短
路径
问题
、
、
、
我试图找出从所有源节点到任何一个目标节点的
最短
路径
的最优方法,从而在加权图中得到最小的权重。所有节点都是源节点或目标节点。所以图我们有一个图,A,B,C作为源节点,D,E,F作为目标节点。A,B,C必须找到任何一个恰好有
最短
路径
的目标节点的
最短
路径
。简单的解决办法是使用Dijkstra
算法
或类似的方法,首先找到从A到D的
最短
路径
,然后从A到E等,然后比较每条
最短
路径
的最终权重,看看哪条
路径<
浏览 4
提问于2022-11-05
得票数 0
3
回答
通过以下链接找到从网页A到网页B的最快方法
我正在寻找一种
算法
来找到两个URL之间的
最短
路径
,或两个维基百科页面。(我不确定Dijkstra的是不是这里的最佳选择,因为图中每条边的权重是1)
浏览 7
提问于2009-11-07
得票数 4
1
回答
竞争下的预处理
最短
路径
、
、
、
、
证明了如果P是u与v之间的
最短
路,那么每个子路也是
最短
路。给定连通图,我希望预处理矩阵中每对节点之间的
最短
路径
,这样: 如果x,y在
路径
中,v,那么
路径
,y是
路径
的子
路径
,v。我不知道一个
算法
或一个证明,
实际
上,我不知道这是否是可确认的。任何想法都是welcome.Thank你。
浏览 2
提问于2016-07-04
得票数 1
1
回答
可以使用A*搜索非网格图吗?
、
、
、
我知道A*是寻找
最短
路径
的最优
算法
,但我不知道任何启发式
算法
是如何在非格图上工作的?这让我想知道A*
实际
上是否能够用于无向或有向图。如果A*能够做到这一点,那么什么样的启发式方法可以使用呢?如果A*不是,那么目前在有向或无向非格图上计算
最短
路径
的最快
算法
是什么?如果需要更多的信息,请发表评论。
浏览 0
提问于2014-12-08
得票数 2
回答已采纳
2
回答
验证图的
最短
路径
、
对图G进行编辑,给出了从顶点V1到图的每一个其他顶点的
最短
路径
距离。我们如何验证给定的距离是一个人可以找到的
实际
最短
路径
(通过Dijkstra或其他
算法
)?它的运行时间呢?
浏览 2
提问于2013-11-29
得票数 1
回答已采纳
3
回答
最短
路径
:贝尔曼-福特与约翰逊
、
根据维基百科,Johnson
算法
使用Bellman Ford
算法
将边的权重转换为非负权重,然后使用Dijkstra
算法
查找
最短
路径
。但贝尔曼·福特
算法
也是一种寻找
最短
路径
的
算法
。为什么我们不使用从贝尔曼·福特
算法
得到的
最短
路径
呢?
浏览 0
提问于2011-03-16
得票数 4
回答已采纳
1
回答
Dijkstra
算法
:所有
最短
路径
都是非循环的吗?
、
我知道,如果
算法
达到负循环,
算法
就不会终止,如果
路径
包含一个距离大于0的循环,那么它就不是
最短
路径
。 我的问题是,如果存在一个循环距离为0的
最短
路径
会发生什么,
算法
会将该循环包含在
最短
路径
中吗?你会说所有的
最短
路径
都是非循环的吗?
浏览 13
提问于2017-06-20
得票数 0
1
回答
我混淆了
最短
路径
查找
算法
和图遍历
算法
。
、
、
、
、
我的理解是,BFS和DFS是图遍历
算法
,而其他
算法
(如A*和dijkstra )则用于在图的两个节点之间寻找
最短
路径
。但是在一些地方,我认为BFS和DFS也被称为
最短
路径
查找
算法
。请详细说明图遍历
算法
与
最短
路径
查找
算法
的区别。谢谢!
浏览 6
提问于2022-05-06
得票数 0
1
回答
动态规划:在有障碍物的网格中寻找
最短
路径
、
、
我试图从Skiena的
算法
设计手册中解决以下问题 鉴于这个问题来自于动态规划一章,我试图找出如何使用动态规划来解决这个问题。相交(
浏览 1
提问于2017-01-04
得票数 0
1
回答
Yen的k
最短
路径
算法
、
、
我目前正在尝试理解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
回答
查找所有小于给定距离的备用
路径
、
图
算法
问题给你。另一个示例
路径
是连接节点1->4的BD,该<em
浏览 3
提问于2013-09-07
得票数 0
回答已采纳
3
回答
当使用最小优先级队列时,如何跟踪Dijkstra
算法
中的
最短
路径
?
、
、
、
我试图用优先级队列实现Dijkstra的
算法
。这是什么意思呢?的
实际
问题: 是否需要额外的数据结构(“构成
最短
路径
的顶点集 *")?如果没有,我如何
浏览 0
提问于2019-06-15
得票数 2
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
Python实现平面最短路径算法
图的最短路径算法-Floyd算法-弗洛伊德算法
计量地理学 最短路径算法
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
云直播
活动推荐
运营活动
广告
关闭
领券