腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
最
宽路径
的
Floyd
算法
、
、
、
、
我一直在研究加权有向图
的
图
算法
,特别是Floyd关于所有对最
短路
径问题
的
算法
。这是我
的
伪代码实现。input A set B[i, j] = 0 for i = 1 to n: for j
浏览 8
提问于2021-02-22
得票数 1
3
回答
图
的
平均最
短路
径长度和直径
算法
在时间
复杂度
上有什么不同吗?
、
、
、
对于一个无向、未加权
的
图,在计算其平均最
短路
径长度
的
算法
的
时间
复杂度
和计算图
的
直径
的
算法
的
复杂度
,即两个顶点之间
的
最长最
短路
径方面,是否存在差异?
浏览 0
提问于2011-08-02
得票数 3
回答已采纳
2
回答
最
短路
径
算法
:动态规划与Dijkstra
算法
、
、
、
在有向无环图(DAG)上运行最
短路
径
算法
(通过使用回忆录
的
动态规划)具有运行时
复杂度
为O(V + E)
的
特性,可以使用以下公式进行验证:现在,Dijkstra
的
算法
也要求有向图。该
算法
的
运行时
复杂度
为O(E + V.log(V)),使用最小优先级队列,这显然比回忆录版本
的
DP慢。 根
浏览 4
提问于2015-01-26
得票数 2
回答已采纳
1
回答
Dijkstra
算法
时间
复杂度
我是Dijkstra
算法
的
新手。 我
的
问题是:对于一个有n个结点和m个边
的
无向图G,Dijkstra
算法
寻找最
短路
径
的
时间
复杂度
是o((n+m)logn)。然而,如果G是连通
的
,为什么这个时间
复杂度
也可以表示为o(mlogn)? 干杯
浏览 21
提问于2021-04-18
得票数 0
回答已采纳
1
回答
无向图中
的
第k条最
短路
、
、
有没有什么方法可以用多项式
的
复杂度
(或者更好)得到一个无向图
的
第k条或k条最
短路
径? 或者,Yen
的
k最
短路
径
算法
可以修改为无向图吗?
浏览 21
提问于2018-12-31
得票数 0
2
回答
FInding节点之间
的
最
短路
径,以及图是否连通
、
、
我不明白我
的
教授在说什么,所以我甚至不需要知道从哪里开始查找所需
的
信息来找到这个问题
的
答案。如果你能给我一些关于在哪里学习这个东西
的
线索,以及你可能如何解决这个问题,我将不胜感激。在下图中,找到两个节点之间
的
最
短路
径-您
的
选择,但使问题变得有趣。
浏览 1
提问于2013-03-05
得票数 0
回答已采纳
1
回答
适用于负循环
的
弗洛伊德-沃尔
算法
、
、
、
如何修改Floyd
算法
以求保持O(V^3)时间
复杂度
的
有向图
的
负代价循环
的
最
短路
径?
浏览 4
提问于2015-02-24
得票数 2
1
回答
最小生成树
的
全对最
短路
径
、
我试图解决一个关于图
的
算法
挑战,我已经将它分解为以下几个方面:给定一个无向生成树,找到2叶,使得它们之间
的
代价最小。现在我知道了Floyd
算法
,它可以找到具有时间
复杂度
O(N^3)和空间
复杂度
O(N^2)
的
所有对最
短路
径。问题
的
输入是N= 10^5,所以O(N^3)和O(N^2)太多了。有没有办法优化这个问题
的
时间和空间
复杂度
?
浏览 6
提问于2017-03-07
得票数 1
2
回答
在至多包含两个负边
的
图中求最
短路
径距离
、
、
、
给出了一个有向图,其中每个边都有一个cost.Taking优点,即图中最多有两个负边,我
的
目标是求出从给定节点到V中所有节点
的
最
短路
径距离。
算法
的
时间
复杂度
应该是O(|E| + |V|*log|V|),所以我认为需要应用Dijkstra
算法
。我猜想我需要以某种方式将我给定
的
图转换成一个新
的
图,该图中从s到v
的
最
短路
径将等价于给定图中所需
的
最
短路
径。或者我需要修改D
浏览 4
提问于2014-02-04
得票数 0
回答已采纳
1
回答
弗洛伊德·沃尔复杂性
、
、
、
、
有人能给我这个过程在for迭代中
的
时间
复杂度
吗?这段代码是FloydWarshall
算法
的
“重构路径”部分。prevn是最
短路
径中源节点与目标节点之间节点
的
矩阵。printAllSP在迭代中运行了n^2次,但我无法真正计算出它每次执行
的
递归调用
的
次数,只知道这取决于i值(max n)、j值(Max n)和k(??)在i和j之间插入最
短路
径
的
节点,通过我
的
计算,包括这个部分在^4上运行
的</e
浏览 2
提问于2014-07-23
得票数 0
回答已采纳
1
回答
有约束
的
弗洛伊德·沃尔
、
、
、
我想知道是否可以使用具有约束条件
的
floyd warshall,这意味着您有一组大小为logn
的
“特殊顶点”,并且您想要计算所有最
短路
径,但是每条路径必须至少经过一个“特殊顶点”,这是可能
的
还是很难
的
np
浏览 5
提问于2020-12-23
得票数 2
回答已采纳
1
回答
中间中心性
的
时间复杂性?
、
、
、
如果给出图
的
最
短路
径前驱体矩阵,计算
的
时间
复杂度
是多少?谢谢你
的
回答, 我对Brandes
算法
很熟悉。但是,Brandes
算法
将计算网络中所有节点
的
间度。我认为计算一个顶点
的
CB所花费
的
时间与计算所有顶点
的
CB
的
时间是相同
的
,因为Brandes
算法
不能适应这种情况。因此,我
的
想法是存储前任矩阵,并且能够计算某个顶点
的</
浏览 1
提问于2011-06-30
得票数 0
5
回答
BFS
算法
和Dijkstra
算法
在寻找最
短路
径时有什么区别?
、
、
、
、
我读到了有关图
算法
的
文章,我发现了这两种
算法
: 我找了很多关于这件事,但没有得到满意
的
答案!在图中查找最
短路
径
的
BFS规则如下: 存储从源u到顶点v
的
距离(重量/长度)。更新
的
路径从源u到那个顶点v
的
最短
浏览 8
提问于2014-08-22
得票数 65
回答已采纳
3
回答
最
短路
径更快- SPFA
算法
?
、
我正在实现一个k-最短顶点不相交路径
算法
,需要一个快速
算法
来找到最
短路
径。有负权重,所以我不能使用dijkstra和bellman-ford是O(ne)。在我最近读到
的
一篇论文中,作者使用了一种所谓
的
SPFA
算法
来寻找负权重图中
的
最
短路
径,根据他们
的
说法,该
算法
的
复杂度
为O(e)。听起来很有趣,但我似乎找不到关于
算法
的
信息。看起来是这样
的
浏览 3
提问于2011-10-10
得票数 4
1
回答
以圆为界
的
最
短路
径
、
、
、
存在半径为r
的
n圆,i-th圆
的
原点位于(x[i], y[i])。我想找出从第一个圆
的
原点到最后一个圆
的
原点
的
最
短路
径
的
距离,并且路径上
的
任何一点都位于一个或多个圆
的
内部。下面是位于(3,3),(3,7)和(6,7)
的
三个圆
的
演示,蓝线是最
短路
径。 ? 我试图找到每一对圆
的
交点,并运行最
短路
径
算法
,但这会导致O(n^5)
浏览 53
提问于2021-07-10
得票数 3
回答已采纳
1
回答
决定是否所有从s到t
的
最
短路
径都包含边e
、
、
、
设G= (V;E)是边都具有非负权
的
有向图。设s,t是V中
的
2个顶点,E是e中
的
一条边,描述一个
算法
,该
算法
决定从s到t
的
所有最
短路
径是否都包含边e。这就是实现Dijsktra时间
复杂度
的
方法:只需从s运行Dijkstra并计算增量(s,t) (从s到t
的
最
短路
径
的
权重)。删除边e,并从新图中
的
s再次运行Djikstra。如果新图中
的
增量(s,t
浏览 6
提问于2013-03-04
得票数 0
回答已采纳
1
回答
索引优先级队列是否确实加快了dijkstra
的
速度?
、
、
、
、
“懒惰”dijkstra
的
最
短路
径
算法
的
渐近时间
复杂度
为O(Elog(V)),它使用规则优先级队列而不是索引堆。这意味着会有重复
的
节点,
算法
必须跳过这些节点,但是不管如何处理。解决这个问题
的
一个解决方案是使用索引优先级队列,但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑,因为懒惰版本仍然跳过
算法
中
的
重复节点。通过一些研究,我还发现索引dijkstra比惰性实现
的
O(E)具有更好<em
浏览 1
提问于2021-08-29
得票数 2
回答已采纳
1
回答
关于谦卑
的
HilbertMaze任务
、
如何从谦卑中着手以下任务: 我可以通过使用BFS生成迷宫和搜索最
短路
径来找到最
短路
径,但是由于最坏
的
时间
复杂度
预计为O(N),我不认为这是正确
的
方法。BFS
的
时间
复杂度
为O(x=0),其中V为顶点数,E为边数。例如,如果N= 3,我们有一个大小为17x17
的
网格,很明显,我们不能在三个步骤中找到路径。因此,要么指出
的
时间
复杂度
是错误
的
,应该是像M^2,或者有一个快速
的
技巧,简单地计
浏览 1
提问于2016-08-04
得票数 1
回答已采纳
1
回答
具有动态规划
的
最
短路
径
、
我不想知道这个问题
的
答案,我只是需要一个正确
的
方向。 状态是顶点i
的
解决方案,其中i <= N。较小
的
状态将是j<e
浏览 2
提问于2016-04-25
得票数 0
回答已采纳
1
回答
无向图
的
最小加权路径树
、
、
我们能给出一个
算法
,使从S到X
的
路径上
的
边
的
最大权重最小化吗?注意,这不是最
短路
径
算法
,因为我们对最小化它们
的
和不感兴趣。 这个
算法
的
复杂度
是多少?最小生成树
算法
(如Prim)是否是该问题
的
解决方案?
浏览 0
提问于2018-11-14
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
OSPF 中的最短路径算法:Dijkstra 算法
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
什么是复杂度算法?详述复杂度算法的原理?用C语言实现复杂度算法。内附完整代码。
图的最短路径算法-Floyd算法-弗洛伊德算法
Python编程之算法复杂度
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券