腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(3300)
视频
沙龙
2
回答
有没有真正的
单
对
最短
路径
算法?
、
今天我遇到了这个词“
单
对
最短
路径
问题”。我想知道对加权图是否存在
单
对
最短
路径
算法。我的推理可能有缺陷,但我想,如果你想找到A和Z之间的
最短
路径
,你绝对必须知道从A到B,C,D,……的
最短
路径
。Y.如果你不知道后者,你就无法确定你的道路实际上是
最短
的。因此,对于我来说,任何
最短
路径
算法都必须计算出图中从A到其他顶点的
最短
路径
,才能
浏览 4
提问于2017-03-30
得票数 10
回答已采纳
1
回答
两个节点之间的
最短
路径
与从一个节点到所有其他节点的
最短
路径
、
、
我目前正在研究非负边权图中的
最短
路径
问题。我知道Dijkstra算法可以给出
单
源
最短
路径
问题的解决方案,也就是可以找到从一个节点到所有其他节点的
最短
路径
,但是我还没有找到算法,可以给我一个先验的更简单的问题:找到两个节点之间的
最短
路径
。直觉上,我认为可以找到例子,表明“简单”问题并不比
单
源
最短
路径
问题更简单,但我正在寻找参考资料,在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4
提问于2022-05-11
得票数 2
1
回答
如何为无向对称图优化所有对的
最短
路径
算法?
、
、
如何为无向对称图优化所有对的
最短
路径
算法?我不是在寻找
最短
路径
算法的比较,除非你特别关注对称图。
浏览 0
提问于2013-06-09
得票数 0
回答已采纳
1
回答
图表:计算
路径
是否至少比其他
路径
好X%
、
、
、
假设我们在一个无向循环加权图中有一条
路径
。假设我们有一个引擎可以在这样的图中找到从节点A到节点B的
路径
,有没有一种简单的方法/算法来计算出从A到B的给定
路径
是否比从A到B的任何其他不相交的
路径
至少好X%?我所说的不相交是指两条
路径
不能共享任何边。
浏览 1
提问于2011-10-08
得票数 1
回答已采纳
2
回答
有向图所有路的最小权边
、
给定一个边权为-ve或+ve的有向图,找到从顶点s到顶点d的所有
路径
的最小权边的算法是什么?
浏览 0
提问于2017-11-13
得票数 0
1
回答
如何改进
单
源
单
目标
最短
路径
Dijkstra算法?
、
对给定的图像dijkstra算法进行哪些改进,以改进
单
源
单
目标
最短
路径
的Dijkstra算法?
浏览 4
提问于2017-03-24
得票数 1
1
回答
线性时间
单
对
最短
路径
算法?
、
、
、
对线性时间中的混合图(即有向和无向边或无向边表示为两条有向边)中的
单
对
最短
路问题,是否有一种算法,具有负、实边权和非负圈。只提到了问题的
单
源和全对变体的算法.我知道,这些问题中的一个也解决了
单
对问题,但没有一个在线性时间内工作,而且所有的准则都是这样。 那么,对于具有上述条件的
单
对
最短
路径
问题,是否存在线性时间算法呢?
浏览 2
提问于2015-03-16
得票数 0
1
回答
如何使用OSRM计算
单
源
最短
路径
?
、
、
、
、
它在解决
最短
路径
问题上似乎非常有效。然而,我不知道如何用它来计算
单
源
最短
路径
。更准确地说,在给定固定起点的情况下,计算在给定距离限制内可以到达的所有位置的
最短
距离(例如,30分钟内可到达)。OSRM是否提供API来计算
单
源
最短
路径
问题(对距离有限制)?有没有其他免费的路由库更适合这种类型的问题?最好是具有对OpenStreetMap数据的良好支持的一个。
浏览 2
提问于2012-12-30
得票数 8
回答已采纳
2
回答
为什么所有对
最短
路径
算法都与负权值一起工作?
、
、
我最近一直在研究所有对
最短
路径
算法,比如弗洛伊德-瓦赫尔和约翰逊的算法,我注意到这些算法产生了正确的解,即使一个图包含负权边(但不包含负权环)。作为比较,Dijkstra的算法(它是
单
源
最短
路径
)不适用于负重边。是什么使全对
最短
路径
算法在负权重的情况下工作?
浏览 9
提问于2014-04-06
得票数 6
回答已采纳
1
回答
是否有可能在大型图中实现具有并行框架的所有对
最短
路径
算法?
、
使用spark graphx pregel api,可以很容易地计算大型图中的
单
源
最短
路径
,例如数百万个顶点和数千万条边,并且运行时间可以接受,例如几个小时。但是,在可接受的运行时间内,是否有可能在大图中运行所有对的
最短
路径
?
浏览 0
提问于2016-05-12
得票数 7
1
回答
加权图胖算法
、
路径
P的胖度是P中任何边的最大权重。 如何找到图的最小可能的胖度?Dijkstra的算法能用来找出最小的脂肪吗?
浏览 0
提问于2017-10-04
得票数 1
回答已采纳
1
回答
设计了一个求解时间为O(k(|V|+|E|))的
单
源
最短
路径
问题的算法
、
、
、
如果从s到任何其他顶点的
最短
路径
至多需要k edges,如何设计一个算法来求解在时间O(k(|V | + |E|))内运行的
单
源
最短
路径
问题
浏览 7
提问于2019-03-12
得票数 3
4
回答
如何在dijkstra算法中保存
最短
路径
、
、
、
首先,让我们定义算法:我想知道如何使用Dijkstra算法将
最短
路径
形式s保存到t。如何使用Dijkstra保存从s到t的
最短
路径
? 我知道我的问题是基本的和不专业的,但任何帮助都将不胜感激。谢谢你考虑我的问题。
浏览 6
提问于2015-03-11
得票数 11
回答已采纳
1
回答
带最小边的Dijkstra算法
、
、
、
首先,让我们定义算法:所以我想知道有什么方法可以改变dijkstra来解决这个问题吗? 任何解决办法都将不胜感
浏览 2
提问于2015-02-16
得票数 4
回答已采纳
1
回答
Bellman算法的中间最优性,是正确的吗?
、
、
Bellman算法是著名的求解任意连通图G(V,E)的
单
源
最短
路径
问题(SSSPP)的算法。该算法的基本实现版本,例如:及其,在使用所有边的并行松弛时,根据我的理解,意味着一个有趣的副产品,我称之为“中间最优性属性”(可能对一些应用程序(如)非常有用)如下: 经过k次迭代后,在
路径
中的#边约束下,每个节点都从同一源识别出
最短
路径
为<= k。这将保证在简单
最短
路径
存在的前提下,对每个目标节点,在最多迭代后产生SSSPP的
最短
<e
浏览 4
提问于2014-09-12
得票数 0
回答已采纳
1
回答
设计求解
单
源
最短
路径
问题的算法
、
、
、
如果从s到任何其他顶点的
最短
路径
至多需要k条边,并且我们不知道k是什么,那么如何设计一个算法来求解运行时间为O k(|V |+ |E|)的
单
源
最短
路径
问题。
浏览 2
提问于2019-03-12
得票数 0
2
回答
从单个源到所有其他节点在生成树中寻找
最短
路径
的最佳算法
、
、
、
、
如果我知道给定的图实际上是一棵生成树,即每一对顶点之间只有一条
路径
,那么如何才能找到从每个顶点到每个顶点的
最短
路径
?我想要最理想的解决方案。我知道Dijkstra的算法,但它非常复杂。我基本上想知道每个顶点从一个源的距离和
路径
。考虑到它是一棵生成树,那么它的最佳和最优解是什么?另外,如果图实际上是生成树,那么请告诉我是否有什么不同的方法可以找到所有对
最短
路径
,而不是多次使用
单
源
最短
路径
算法。 请原谅我的过度解释。
浏览 6
提问于2014-12-11
得票数 0
回答已采纳
1
回答
K条负边--
单
源
最短
路径
、
我已经设法解决了使用dijkstra在恰好有一个负边时找到所有
单
源
最短
路径
的问题。现在我正试图面对一个新的问题,当只使用dijkstra (而不是bellman ford)时,如何找到从给定来源到恰好K条负边的所有
最短
路径
。(k是已知的)。 我真的想不出一个好的办法。
浏览 10
提问于2013-07-04
得票数 2
2
回答
最短
路径
共同核心问题(S)
、
我的直觉说,我应该想出一个算法,计算出图中所有顶点之间的
最短
路径
,然后查看
路径
,找到流量最高的顶点。但是我很难想出一个具体的算法,因为我以前根本没有这方面的经验。我试着用谷歌搜索这个问题,但没有成功。
浏览 0
提问于2016-11-01
得票数 -2
回答已采纳
2
回答
单
源
最短
双声道
、
、
我正试图解决塞奇威克&韦恩算法书中的一个问题:
单
源
最短
双电子
路径
。一个单调
最短
浏览 6
提问于2017-12-11
得票数 2
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
Arcgis教程:如何求解最短路径
Python实现平面最短路径算法
OSPF 中的最短路径算法:Dijkstra 算法
计量地理学 最短路径算法
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券