腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
3
回答
最短
路径
更快- SPFA
算法
?
、
我正在
实现
一个k-
最短
顶点不相交
路径
算法
,需要一个快速
算法
来找到
最短
路径
。有负权重,所以我不能使用dijkstra和bellman-ford是O(ne)。在我最近读到
的
一篇论文中,作者使用了一种所谓
的
SPFA
算法
来寻找负权重图中
的
最短
路径
,根据他们
的
说法,该
算法
的
复杂度为O(e)。听起来很有趣,但我似乎找不到关
浏览 3
提问于2011-10-10
得票数 4
3
回答
是Bellman“所有对”还是“来自一个节点”
最短
路径
的
结果?/是否有一个全对Bellman版本?
、
、
我最近正在学习图形
算法
,在我
的
大学里,我们被教导说,Bellman
的
结果是一个从所有节点到所有其他节点
的
距离表(所有对
最短
路径
)。然而,我不明白这个
算法
是如何
实现
的
,我试图通过观看YouTube视频和查找维基百科中
的
定义来理解它……我无法找到描述该
算法
的
资源,其结果将是所有对
最短
路径
表,但只能“从一个节点到所有其他节点对Bell
浏览 8
提问于2017-07-16
得票数 1
回答已采纳
2
回答
用A*
算法
求几条
最短
路径
、
、
、
我正在制作一个路由应用程序,它使用A*
算法
来查找路由。我想提供
的
不只是一条路线,还有几条替代路线。例如,仅比最佳路由稍长一点
的
路由。 由于A* (和其他许多)只找到一条路线,我如何搜索这些替代路线?我应该使用其他
算法
吗?
浏览 0
提问于2015-02-26
得票数 1
1
回答
一个接受图
的
*
算法
、
、
、
我正在做一个项目,在这个项目中,我需要一个
最短
路径
算法
来找到
最短
路径
。目前我正在使用David Eppstein
的
Dijkstra
算法
实现
,但由于图
的
大性质(大约360万个节点),找到这条
最短
路径
可能需要几乎一分钟
的
时间。我知道A*
算法
运行得更快,但我发现
的
i
的
所有
实现
都是基于网格样式而不是图形样式。"
浏览 1
提问于2012-11-30
得票数 2
1
回答
用图工具求k条
最短
路径
、
、
、
我有一个有向图,我试图找出最上面的k条
最短
路径
。目前,我已经在图形工具中
实现
了网络,它提供了一个
最短
路径
算法
,但根据我所能知道
的
,没有k个
最短
路径
算法
。我遇到过这个帖子(),但我毕竟不是连接两个节点
的
路径
。 似乎NetworkX有一个用于此()
的
函数。是否有办法在图形工具中这样做,还是我更好地切换工具箱和使用NetworkX?
浏览 2
提问于2016-02-23
得票数 1
回答已采纳
1
回答
Bellman
算法
的
中间最优性,是正确
的
吗?
、
、
Bellman
算法
是著名
的
求解任意连通图G(V,E)
的
单源
最短
路径
问题(SSSPP)
的
算法
。该
算法
的
基本
实现
版本,例如:及其,在使用所有边
的
并行松弛时,根据我
的
理解,意味着一个有趣
的
副产品,我称之为“中间最优性属性”(可能对一些应用程序(如)非常有用)如下: 经过k次迭代后,在
路径
中
的
#边约束下,每个节点都从同一源识别出<em
浏览 4
提问于2014-09-12
得票数 0
回答已采纳
1
回答
android中
的
最短
路径
算法
、
、
我正在android中
实现
一个离线地图导航项目,所以我使用mbtile作为我
的
地图源。现在我想覆盖地图上
的
点之间
的
路径
(路由),有谁能给出一个想法,如何在android中
实现
最短
路径
算法
来路由点之间
的
最短
路径
?
浏览 3
提问于2013-04-04
得票数 0
1
回答
给定特定步数时,从起始节点到结束节点
的
最大
路径
、
、
目前,我已经
实现
了Dijkstra
的
最短
路径
算法
。给定一个迷宫,
最短
路径
算法
提供了以最少
的
步数从入口到出口退出迷宫
的
最快方法。然而,我想找到一种方法,给定特定
的
n步,迷宫中可能
的
最大
路径
是什么?(您可以到达死胡同并返回,这将被算作额外
的
步骤)
浏览 31
提问于2019-04-27
得票数 0
1
回答
基于Gremlin
的
Dijkstra
算法
、
、
我想在Gremlin中
实现
Dijkstra
算法
,以创建一个只包含
最短
路径
的
全网状图。我也可以用Java编写,但我需要Gremlin解决方案
的
灵活性。如何做到这一点?
浏览 2
提问于2012-06-20
得票数 2
1
回答
什么是桶还是双桶数据结构?
、
、
、
我正在读一些关于
最短
路径
算法
实现
的
文章,并且一遍又一遍地发现,用双桶数据结构
实现
Dijkstra
算法
是一个很好
的
实现
。我读
的
特别报纸是这样
的
, Cherkassky,B.V.,Goldberg
浏览 1
提问于2017-02-22
得票数 9
回答已采纳
1
回答
带弧标志
的
最短
路径
问题dijsktra
、
、
、
在2M节点道路网络这样
的
大型图上,dijkstra
算法
不能在合适
的
时间内解决
最短
路径
问题。我们需要
最短
的
路径
查询执行时间不到1秒,我正在
实现
圆弧标志方式,以使dijkstra更快。有谁知道如何
实现
弧形标志
的
预处理和查询。弧标志
的
预处理有一些不同
的
算法
,我需要一个快速
的
。
浏览 2
提问于2010-09-15
得票数 1
3
回答
当使用最小优先级队列时,如何跟踪Dijkstra
算法
中
的
最短
路径
?
、
、
、
我试图用优先级队列
实现
Dijkstra
的
算法
。 但是,在我使用上述两个数据结构
实现
时,当我最终到达目标节点时,我没有存储顶点
路径
?换句
浏览 0
提问于2019-06-15
得票数 2
2
回答
从
路径
到顶点
的
最短
路径
、
我使用netwrokx计算不同顶点之间
的
最短
路径
,使用Dijkstra
算法
。我有一个例子,我想连接三个不同
的
顶点(例如,A,B和C在一个无向图中)。首先,我找到了从A到B
的
最短
路径
,然后我想要找到从A到B
的
路径
的
最短
路径
。到目前为止,我尝试
的
是从A到B
路径
的
所有节点到C
的
最短
浏览 1
提问于2018-08-15
得票数 2
回答已采纳
2
回答
使用dijkstra从队列中弹出
最短
路径
的
节点。
、
、
、
、
我使用适当
实现
的
dijkstra
算法
计算出
最短
路径
。它通过B,C,D和E从A到F,所以整个
最短
路径
是A,B,C,D,E,F。
浏览 2
提问于2015-08-28
得票数 0
回答已采纳
1
回答
使用Boost Dijkstra查找指定最大距离
的
最短
路径
、
、
、
我喜欢使用boost
的
dijkstra
实现
来查找到节点
的
最短
路径
我可以自己
实现
,但我相信boost
的
实现
比我
的
高效得多,所以我更喜欢使用boost来完成这项任务 我只是想知道,如果节点太远,是否有一种方法可以告诉boost
的
di
浏览 3
提问于2012-06-21
得票数 2
1
回答
使用A*标记单元可以使用
的
字段
、
我正在使用A*
算法
在六边形地图上寻找
最短
路径
。但在我
实现
A*
算法
之前,我使用了。(单击设备) 为了找到
最短
的
位置,我已经使用了A*,现在我想使用A*来标记单元可能到达
的
字段。我
的
问题是,对于这个问题,使用A*
的
最好方法是什么?我必须找到到每个字段
的
最短
路径
,并获得
路径
长度,然后将该长度与单元
的
移动进行比较吗?这个解决方案不好,而
浏览 5
提问于2012-05-23
得票数 0
1
回答
加权无向图上
的
最长
路径
、
、
、
我知道这是指数级
的
。我已经
实现
了一种使用Dijkstra
算法
寻找
最短
路径
的
方法。是否可以修改该方法以找到最长
的
路径
?如果我把所有的重量都减了,这难道不管用吗。我当前图表上
的
所有权重都是正数。此外,不应该有重复
的
路径
。 我知道Bellman Ford
算法
在负权值下工作,但我希望我能修改我现有的
最短
路径
法。
浏览 5
提问于2013-11-29
得票数 1
回答已采纳
1
回答
Dijkstra
算法
:所有
最短
路径
都是非循环
的
吗?
、
我知道,如果
算法
达到负循环,
算法
就不会终止,如果
路径
包含一个距离大于0
的
循环,那么它就不是
最短
路径
。 我
的
问题是,如果存在一个循环距离为0
的
最短
路径
会发生什么,
算法
会将该循环包含在
最短
路径
中吗?你会说所有的
最短
路径
都是非循环
的
吗?
浏览 13
提问于2017-06-20
得票数 0
3
回答
最短
路径
:贝尔曼-福特与约翰逊
、
我很难理解
的
用处。我认为这个问题对于一个在这个领域有知识的人来说听起来一定很愚蠢,但我想不出来。根据维基百科,Johnson
算法
使用Bellman Ford
算法
将边
的
权重转换为非负权重,然后使用Dijkstra
算法
查找
最短
路径
。但贝尔曼·福特
算法
也是一种寻找
最短
路径
的
算法
。为什么我们不使用从贝尔曼·福特
算法
得到
的
最短
路径
浏览 0
提问于2011-03-16
得票数 4
回答已采纳
2
回答
A*总是提供
最短
路径
吗?
、
、
我正在尝试理解A*,统一成本和贪婪搜索
算法
是如何工作
的
。我知道探索节点
的
方式在所有三种
算法
中都会发生变化(贪婪将基于启发式值进行探索,A*基于启发式加距离,均匀基于距离)。我想知道,对于给定
的
源和目的地,是否所有3种
算法
都应该提供
最短
路径
(只需探索不同数量
的
城市?)或者他们能提供一条不同
的
路径
。我最困惑
的
是
实现
部分-如果你将节点存储在队列中,那么当你打算探索目标节
浏览 4
提问于2016-10-04
得票数 1
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
Python实现平面最短路径算法
OSPF 中的最短路径算法:Dijkstra 算法
图的最短路径算法-Floyd算法-弗洛伊德算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券