腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
python中两节点间长
最短
路径
有向无圈图的
生成
、
、
、
、
我想比较几种路由
算法
在有向无环
图
(DAG)中寻找两个节点之间
最短
路径
所需的时间。知道如何克服这个问题吗?
浏览 3
提问于2016-02-07
得票数 2
2
回答
从单个源到所有其他节点在
生成
树中寻找
最短
路径
的最佳
算法
、
、
、
、
如果我知道给定的
图
实际上是一棵
生成
树,即每一对顶点之间只有一条
路径
,那么如何才能找到从每个顶点到每个顶点的
最短
路径
?我想要最理想的解决方案。我知道Dijkstra的
算法
,但它非常复杂。我基本上想知道每个顶点从一个源的距离和
路径
。考虑到它是一棵
生成
树,那么它的最佳和最优解是什么?另外,如果
图
实际上是
生成
树,那么请告诉我是否有什么不同的方法可以找到所有对
最短
路径
,而不是多次使用单源<e
浏览 6
提问于2014-12-11
得票数 0
回答已采纳
1
回答
我混淆了
最短
路径
查找
算法
和
图
遍历
算法
。
、
、
、
、
我的理解是,BFS和DFS是
图
遍历
算法
,而其他
算法
(如A*和dijkstra )则用于在
图
的两个节点之间寻找
最短
路径
。但是在一些地方,我认为BFS和DFS也被称为
最短
路径
查找
算法
。请详细说明
图
遍历
算法
与
最短
路径
查找
算法
的区别。谢谢!
浏览 6
提问于2022-05-06
得票数 0
2
回答
最小
生成
树和
最短
路径
、
、
、
我遇到了这样一个问题: 给定一个具有整数权重(正负)的连通有向
图
,开发一个
算法
来寻找两个顶点之间的
最短
路径
。我想我可以使用最小
生成
树
算法
,例如kruskal的
算法
,然后使用可能的dijkstra
算法
来证明,因为在MST中,每个顶点只有一条进入边,dijkstra的
算法
甚至可以在负权重下工作。附注:我很难证明MST包含每个顶点的有向
图
的
最短
路径
。
浏览 1
提问于2012-11-08
得票数 0
1
回答
使用dijkstra
算法
在图中寻找源和目的地之间的
最短
路径
、
、
、
我想写一个
算法
,在有向
图
和无向图中找到两个特定顶点-源和目标-之间的
最短
路径
。 我知道dijkstra的
算法
,它用来寻找所有的
最短
路径
图
。但是,您是否会修改此
算法
以仅查找两个顶点之间的
最短
路径
?
浏览 31
提问于2018-01-11
得票数 0
1
回答
全
最短
路径
的BFS修改
、
、
作为一项任务,我得到了以下问题,但这确实使我感到困惑: 考虑BFS
算法
。给定有向
图
G = (V,E)和起始点s∈V,该
算法
计算每个顶点u∈V的值du,即从s到u
最短
路径
上的长度(边数),该问题的目的是修改类的BFS
算法
,计算从s到G的每个顶点的
最短
路径
数。解释如何使用该BFS的结果
生成
一个新的有向
图
G2 =(V2,E2),其中V2⊆V和E2⊆E使得G2中从s开始的每一条
路径
都是G中从s开始的<em
浏览 2
提问于2015-04-26
得票数 3
1
回答
图
S的检验是G中的
最短
路径
树(
算法
+正确性)
、
、
、
、
G是一个只具有正权的连通无向
图
。S是
最短
路径
树(不一定是G的防止小组委员会)。因此,我要设计一个
算法
来检查
图
S是否是
图
G的
最短
路径
树。我不知道这个
算法
是否
浏览 3
提问于2014-02-24
得票数 1
回答已采纳
2
回答
dijkstra
算法
,对某些节点的
最短
路径
只运行一次(不是两个,不是整个
图
)。
、
、
因此,dijkstra
算法
是搜索加权(无负)连通
图
最短
路径
的最佳
算法
。Dijkstra
算法
可用于寻找两点/顶点的
最短
路径
。它可以用来寻找所有顶点的
最短
路径
。 问题:我的理解正确吗?它也能用来寻找某些顶点的
最短
路径
吗?例如,
图
有A,B,C,D,E,F,G,H,I,J,K,我们只对A,B;C,K的
最短
路感兴趣,我们可能只需要一次就能找到两条
浏览 2
提问于2018-03-12
得票数 1
1
回答
所需的最小行数
、
有没有像使用
图
和
最短
路径
算法
或最小
生成
树这样的方法,这样我们就可以从任何点开始到达任何点,但最小化直线的总长度? 我想也许我可以用
图
的距离来设置边的成本,并使用
最短
路径
算法
,但我不确定这是否可能。
浏览 14
提问于2020-12-09
得票数 1
2
回答
求解特定情况下替换
路径
问题的
算法
、
、
、
对于
图
G中的任何边e,设G _e表示从G中删除e得到的
图
。(A)假设给出了一个边加权有向
图
G,其中从顶点s到顶点t的
最短
路径
σ通过G的每个顶点,描述了计算G中从s到t的
最短
路径
距离的
算法
,对于G的每一个边e,在O(VlogV)时间内计算
最短
路径
距离。您的
算法
应该输出一组E
最短
路径
距离,一个对应于输入
图
的每个边。您可能假设所有的边权都是非负的。[提
浏览 8
提问于2019-12-20
得票数 0
3
回答
为什么大多数
图
算法
不那么容易适应负数?
、
、
说: 但是为什么呢?当我们在原始权重前面加一个负的-时,我认为大多数涉及权重的
图
问题都可以平等地处理,对吗?
浏览 9
提问于2012-04-30
得票数 9
回答已采纳
3
回答
是否存在最小深度、
生成
树
算法
?
、
、
、
所以我要找的是一个最小的
生成
树(不是最优的,只是最有效的),它最小化到树根的最大电气距离(通过
图
的距离)。 通过这种方式,我只是购买更长更细的电缆,这是一种更便宜的解决方案,较短,较厚的电缆。
浏览 1
提问于2013-06-27
得票数 6
2
回答
最短
路径
树的子树也是
最短
树吗?
、
、
、
我有一个无向加权
图
G=(V,E),其中V表示节点,E表示边。通过Dijkstra
算法
,我得到了一棵以源节点s为根并
生成
图
G中所有节点V的
最短
路径
树Ts=(s,V),然后选择了
最短
路径
树Ts=(s,V)的一个子树Tm=(s,K) (其中K是V的一个子集),它只连接到所有V个节点中的K个节点,即子树Tm是
最短
路径
树Ts的一个子集。我的问题是,现在我如何通过参数或引理/定理证明
最短
路径<
浏览 2
提问于2016-12-28
得票数 2
3
回答
最短
路径
:贝尔曼-福特与约翰逊
、
根据维基百科,Johnson
算法
使用Bellman Ford
算法
将边的权重转换为非负权重,然后使用Dijkstra
算法
查找
最短
路径
。但贝尔曼·福特
算法
也是一种寻找
最短
路径
的
算法
。为什么我们不使用从贝尔曼·福特
算法
得到的
最短
路径
呢?
浏览 0
提问于2011-03-16
得票数 4
回答已采纳
1
回答
加权无向图中的所有对
最短
路径
、
我目前正在为我的游戏寻找
路径
,需要帮助找到一种有效的
算法
来计算加权无向图中的所有对
最短
路径
(图中的每个顶点代表我地图上的一个
路径
点,而每个边表示
路径
对之间的距离)。由于Floyd
算法
的简单性和相对存储效率,我考虑过使用Floyd
算法
,但是Floyd是为有向
图
设计的,而我的
图
是无向
图
。这意味着Floyd
算法
比所需的代价更高,因为我知道从顶点A到顶点B的
最短
路
浏览 0
提问于2011-09-14
得票数 2
回答已采纳
2
回答
最短
路径
共同核心问题(S)
、
我试图想出一个
算法
,让我们在任意图中找到一个顶点,这样顶点与最远顶点的距离最小。 另外,我还想出一个
算法
,让我找到两个顶点,而不是一个,再把最远的顶点到这两个顶点之间的距离最小化。我的直觉说,我应该想出一个
算法
,计算出图中所有顶点之间的
最短
路径
,然后查看
路径
,找到流量最高的顶点。但是我很难想出一个具体的
算法
,因为我以前根本没有这方面的经验。我试着用谷歌搜索这个问题,但没有成功。
浏览 0
提问于2016-11-01
得票数 -2
回答已采纳
1
回答
如何为无向对称
图
优化所有对的
最短
路径
算法
?
、
、
如何为无向对称
图
优化所有对的
最短
路径
算法
?我不是在寻找
最短
路径
算法
的比较,除非你特别关注对称
图
。
浏览 0
提问于2013-06-09
得票数 0
回答已采纳
3
回答
搜索特定长度的
路径
、
、
、
、
这个问题适用于随机地图的
生成
。那么,我的问题是:我可以使用什么
算法
来找到具有特定成本或成本范围的
路径
?我
浏览 0
提问于2014-01-10
得票数 5
1
回答
在全连通无向图中求
最短
路径
、
我试图解决一个问题,在这个问题中,我有一个二维坐标的列表,我想找到连接所有这些坐标的
最短
路径
。你不需要回到最初的城市,我相信TSP希望你这样做。在这个二维平面上,我们使用欧氏距离度量,如果我没记错的话,三角不等式保持不变,这是普通TSP
算法
不关心的。 在这个问题中没有‘你只能访问一个节点一次’的规则;‘
最短
路径
’可以形成一棵树。然后,我想“只需绘制一个
图
,并使用普里姆氏或克鲁斯卡尔氏病
算法
来找到最小
生成
树的
浏览 0
提问于2017-03-26
得票数 2
1
回答
为什么OSRM实现了收缩层次和MLD而不是A*?
我将介绍OSRM实现;他们实现了路由
算法
CH和MLD。我想知道它使用这些
算法
的动机是什么。更重要的是,在这两种
算法
中,我们不能动态地改变边权重。
浏览 0
提问于2019-04-29
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
图的最短路径算法-Floyd算法-弗洛伊德算法
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
OSPF 中的最短路径算法:Dijkstra 算法
计量地理学 最短路径算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券