腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(5024)
视频
沙龙
1
回答
Dijkstra的
算法
--为什么每次提取
优先
级最小的顶点?
algorithm
、
time-complexity
、
pseudocode
、
dijkstra
、
shortest-path
我正在学习Dijkstra的
算法
来寻找最短路径。我注意到有一个
优先
级队列来帮助提取顶点集中
优先
级
最低
的顶点。如果我从顶点集中选择一个顶点,而不是
优先
级
最低
的顶点,那么该
算法
是否仍然有效?如果是,那么时间复杂
度
如何?维基百科最初的Dijkstra
算法
如下: dist[source] ← 0prev[v] ← u Q.decreas
浏览 4
提问于2017-10-27
得票数 0
3
回答
宽度
优先
搜索
算法
(以邻接表表示的
图
)具有二次时间复杂
度
?
algorithm
、
graph
、
time-complexity
、
breadth-first-search
一位朋友告诉我,宽度
优先
搜索
算法
(由邻接列表表示的
图
)具有二次时间复杂
度
。但是在所有的消息来源中,BFS
算法
的复杂
度
恰恰是O(x=0)或O (n + m),由此我们得到了二次复杂
度
?
浏览 4
提问于2014-01-15
得票数 0
回答已采纳
2
回答
最短路径
算法
:动态规划与Dijkstra
算法
algorithm
、
time-complexity
、
dynamic-programming
、
dijkstra
在有向无环
图
(DAG)上运行最短路径
算法
(通过使用回忆录的动态规划)具有运行时复杂
度
为O(V + E)的特性,可以使用以下公式进行验证:现在,Dijkstra的
算法
也要求有向
图
。该
算法
的运行时复杂
度
为O(E + V.log(V)),使用最小
优先
级队列,这显然比回忆录版本的DP慢。 这是对无界非负权的任意有向
图
的
浏览 4
提问于2015-01-26
得票数 2
回答已采纳
2
回答
具有未知节点对应关系的
图
相似性度量
algorithm
、
graph-theory
、
graph-algorithm
如何度量节点数相等或不相等的两个
图
G1和G2之间的相似
度
,其中,
图
的节点之间的对应关系是未知的。例如,G1的节点A已移动到G2的中间。有没有什么相似性度量
算法
可以返回其中,1表示最高相似
度
,0表示
最低
相似
度
。<code>B1</code>
浏览 35
提问于2020-03-16
得票数 1
1
回答
求
图
局部极小/最大值的爬山
算法
的时间复杂
度
algorithm
、
time-complexity
、
complexity-theory
、
theory
在具有n节点的图中找到局部最小值(每个节点具有最大d邻居)的
算法
的时间复杂
度
(
算法
的顺序)是多少? Detail:我们有一个带有n节点的
图
。图中的每个节点都有一个整数值。每个节点都有最大的d邻居。我们正在寻找一个节点,它的值在相邻节点中是
最低
的。
图
用邻接表表示。该
算法
首先选择随机节点,然后在这些节点中选择具有最小值的节点(例如节点u)。从节点u开始,
算法
找到一个邻居v,其中value(v) < value(u)。然后,继续使用v并重复上述步骤。当
浏览 2
提问于2016-01-19
得票数 3
回答已采纳
1
回答
时间复杂
度
:节点A和节点B之间的所有路径是否都与节点X或节点Y相交?
time-complexity
如果我有一个至少有4个节点的
图
,那么最小的时间复杂
度
是多少? 注意:我不是计算机科学家,我是哲学博士生,所以我提前为我的无知道歉。
浏览 1
提问于2016-03-01
得票数 1
1
回答
Dijkstra
算法
的时间复杂
度
time-complexity
、
runtime
、
dijkstra
据我所知,在最坏的情况下,使用队列的未加权图上的Dijkstra
算法
的时间复杂
度
是O(n2)。我猜想这是因为od bfs和dfs。BFS在标记阶段处理所有顶点,dfs用于回溯。它们都具有线性时间复杂
度
。但我不确定这个逻辑是否正确。 另外,对于加权
图
,我知道时间复杂
度
是O(EVlogV),其中E是边和V顶点。我认为这是因为
优先
级队列,我知道
优先
级队列是如何工作的,但仍然不理解O符号。
浏览 26
提问于2020-06-04
得票数 0
2
回答
该Dijkstra
算法
中
优先
级队列的空间复杂
度
dijkstra
、
space-complexity
有人能告诉我这个Dijkstra algo中
优先
级队列的空间复杂性吗?请注意,在这里,可以添加一个顶点来排队超过一次。但是,由于访问集的原因,它不会被处理超过一次。
浏览 3
提问于2019-12-18
得票数 3
回答已采纳
1
回答
查找仅包含2和3
度
节点的最大子
图
algorithm
、
graph
、
language-agnostic
、
graph-theory
、
depth-first-search
我正在尝试实现以下论文中的(未加权的)反馈顶点集近似
算法
:。
算法
的步骤之一(在第4页描述)是计算输入
图
的最大2-3个子
图
。这篇论文的作者声称,可以通过在图上进行“简单深度
优先
搜索(DFS)”来进行计算。然而,这个
算法
似乎让我摸不着头脑。如何计算最大子
图
?
浏览 0
提问于2019-04-01
得票数 5
2
回答
以下
算法
的时间复杂
度
是多少?
algorithm
、
graph
、
time-complexity
我只想确认下面
算法
的时间复杂
度
。 假设:
图
是无权的、无向的,并且我们在内存中加载了它的邻接列表表示(包含每个顶点的邻居的列表列表)。第3行:查找
最低
值需要检查所有值,即O(n)。因为这是嵌套在while循环中的,这个循环只访问所有节点一次,所以它变成O(n^2)。汇总:总复杂
度
为O(n) + O(n^2) + O(n * avg_neigh^2)
浏览 0
提问于2019-10-07
得票数 6
回答已采纳
3
回答
将无向
图
转换为具有特定条件的有向
图
algorithm
、
graph
、
graph-theory
、
directed-graph
、
undirected-graph
给出了一种具有M条边和N个顶点的无向
图
,我们必须将每条边从u-v转换为u->v或v->u,使得每个顶点的索引树都是even.Which方法或
算法
,从而使时间复杂
度
最低
。
浏览 3
提问于2018-12-09
得票数 0
1
回答
执行
松弛
m次的Dijkstra
算法
algorithm
、
graph-algorithm
、
dijkstra
在Dijkstra的
算法
中,
松弛
最多被称为m乘以(其中m=#边)。我试着找出一些具体的图例子,它确实是被执行了很多次。我知道,每次找到到给定节点的更便宜的路径时,都会出现
松弛
,但我不能真正“想象”这种情况。
浏览 1
提问于2012-10-21
得票数 1
1
回答
一个*搜索
算法
和一个例子
algorithm
、
graph
、
greedy
我正在研究A*搜索
算法
,并看到了以下示例:该
算法
的描述如下:更新节点1到3的距离和
优先
级到9.32455532033676当前
优先
级
最低
为9.32455532033676的访问节点1更新节点4到13的距离和
优先
级到15.8284271
浏览 3
提问于2022-11-07
得票数 0
回答已采纳
1
回答
选择适当的生成和计算元素共享对排列的
算法
python
、
algorithm
、
time-complexity
、
permutation
、
graph-algorithm
我感兴趣的是,在执行以下任务时,哪种
算法
的时间复杂
度
最低
: 给定一个元组列表,如(A,B),(B,C),(C,D),( D,E),(A,D),(E,A),(A,C),(A,C),查找序列,如A,B,C,
浏览 3
提问于2019-10-27
得票数 0
回答已采纳
1
回答
如何在无向图上应用宽度
优先
算法
生成星图?
data-structures
、
graph
我是从一个数据结构和
算法
教科书上问到这个问题的 (a)绘制具有6个顶点的完全无向
图
。 (b)在(a)中的无向图上应用呼吸
优先
算法
将产生一个星图。
浏览 0
提问于2016-07-20
得票数 0
2
回答
查找图中两个节点之间分离
度
的有效方法
algorithm
、
graph
讨论不同的想法、
算法
和权衡。(隔离
度
定义:)我能想到的候选
算法
有:广度
优先
搜索(BFS),深度
优先
搜索(DFS),深度限制搜索(DLS),迭代加深搜索(IDS)。很有可能的是,即使当两个人连接在一起(即分离
度
= 1)时,
算法
也可能长时间沿着错误的路径进行搜索。 BFS保证找到最小的分离
度
(因为
图
没有加权)。假设最大分支因子为b,两个目标人之间的实际分离
度
为d,则时间复杂
度
和空
浏览 0
提问于2013-03-10
得票数 7
回答已采纳
4
回答
如何以编程的方式证明“六
度
分离”的概念?
algorithm
、
networking
、
graph-theory
、
combinatorics
如何以编程中最有效的方式证明“六
度
分离”概念的概念?
浏览 2
提问于2009-06-12
得票数 8
回答已采纳
3
回答
在文档中包含一个单词的完整句子
bash
、
shell
、
grep
、
sentence
因此,举个例子,考虑到这个文本: 对于图中给定的源顶点(节点),
算法
在该顶点与其他顶点之间寻找代价
最低
的路径(即最短路径)。
浏览 4
提问于2014-07-11
得票数 3
回答已采纳
4
回答
在STL
优先
级队列C++中实现C++
c++
、
stl
、
priority-queue
、
prims-algorithm
、
decrease-key
我正在尝试实现Prim的
算法
,为此,我需要一个
优先
级队列的decreaseKey方法(更新
优先
级队列中的键值)。我能在STL
优先
级队列中实现这一点吗?如果有帮助的话,这就是我要遵循的
算法
: 如
浏览 4
提问于2013-01-19
得票数 4
回答已采纳
2
回答
在O(E logV)中求图中的单调最短路径
algorithm
、
language-agnostic
、
graph-theory
、
graph-algorithm
、
shortest-path
单调最短路给出了一个边加权有向
图
,找到了从s到其他顶点的单调最短路径。如果路径上的每条边的权重都是严格递增或严格递减的,则路径是单调的。部分解:按升序
松弛
边,找到最佳路径;然后按降序
松弛
边,找到最佳路径。 假设我们是按降序放松边,我们可以在一个点上选择一个以上的边。我们将在什么基础上选择下一个优势?
浏览 3
提问于2014-04-05
得票数 7
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
Fluent压力速度耦合的选取(文末附120GFluent资料免费领,包括视频、案例、电子书)
程序猿的内功修炼,学好算法与数据结构
从基础知识到实际应用,一文了解机器学习非凸优化技术
从基础知识到实际应用,一文了解“机器学习非凸优化技术”
六十三、一文说清楚Fluent压力-速度耦合
热门
标签
更多标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
活动推荐
运营活动
广告
关闭
领券