腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
如果
使用
最大
优先级
队列
,
Dijkstra
算法
是
如何
工作
的
?
c++
、
algorithm
、
graph-algorithm
、
dijkstra
我最近看了一些
Dijkstra
算法
的
代码。代码
的
目标
是
找到从顶点1到顶点N
的
最小成本路径。我在查看问题
的
解决方案时遇到了以下
工作
代码: void
dijkstra
(int start, int n) { dist[w; q.push(end);
浏览 30
提问于2020-04-26
得票数 0
回答已采纳
1
回答
单源最短路径实现:
优先级
与FIFO
队列
queue
、
priority-queue
、
dijkstra
、
shortest-path
、
bellman-ford
根据问题
的
具体情况,在单源最短路径问题中通常提到
的
两种
算法
是
Dijkstra
算法
和Bellman
算法
。
Dijkstra
的
算法
工作
在正边权值,而Bellman
算法
是
一个推广,也允许负边权。正如Sedgewick
的
“
算法
”(第4版)所实现
的
,
Dijkstra
的
算法</em
浏览 7
提问于2015-04-18
得票数 0
3
回答
负边有向无圈图
的
Dijkstra
算法
algorithm
、
dijkstra
、
directed-acyclic-graphs
如果
是
无圈图(DAG),
Dijkstra
的
算法
会在负边图上
工作
吗?我认为这是因为由于没有循环,所以不可能有负循环。这个
算法
会失败还有其他原因吗? 谢谢明天
的
期中考试
浏览 4
提问于2015-03-11
得票数 6
回答已采纳
1
回答
具有最小
优先级
队列
的
Dijkstra
算法
graph
、
path
、
priority-queue
、
dijkstra
、
shortest-path
我正在尝试用
优先级
队列
实现
dijkstra
算法
,但我不能理解它是
如何
工作
的
。我在网上读了很多指南,但我根本不能理解这个
算法
。第二个问题,当我提取
队列
的
根时,
如果
这个节点不与任何被访问
的<
浏览 0
提问于2013-08-19
得票数 18
回答已采纳
2
回答
为什么在
Dijkstra
算法
中
使用
PriorityQueue?
algorithm
、
data-structures
、
priority-queue
、
shortest-path
、
dijkstra
我一直在尝试理解
Dijkstra
算法
的
内部原理,以找到加权图
的
最短路径。 访问完一个顶点后,为什么我们必须将相邻
的
顶点存储到一个PriorityQueue中,而不是普通
的
队列
?我问上面问题
的
原因
是
:我知道用PriorityQueue我们可以从
队列
中得到
最大
/最小
的
数字。但在
Dijkstra
算法
的
情况下,我们无论
浏览 2
提问于2020-04-20
得票数 0
2
回答
Dijkstra
的
算法
--
如何
使用
优先级
队列
或最小堆?
c++
、
algorithm
、
queue
、
priority-queue
、
dijkstra
我一直在努力实现
Dijkstra
的
算法
;更具体地说,就是
优先级
队列
的
部分。将顶点添加到数据结构中,并
使用
迭代器遍历所有顶点并找到最小距离;这很容易,但时间不长。我想要
的
是
: 我认为,要使
Dijkstra
算法
正常
工作
,您应该能够在恒定时间内插入顶点,并在log(n)时间中提取它们;我被建议
浏览 2
提问于2014-02-21
得票数 2
回答已采纳
1
回答
自适应梯形规则及其
优先级
队列
实现
的
说明
algorithm
、
recursion
、
numerical-methods
、
numerical-integration
关于自适应梯形细分(请参阅和),我需要解决一个评估f(x)需要花费大量时间
的
问题,所以我需要尽可能少地这样做。于是我找到了这个答案: 这到底是什么意思?
优先级
队列</
浏览 10
提问于2020-08-29
得票数 0
5
回答
编程竞赛最好
的
单源最短路径
算法
是什么?
c++
、
algorithm
、
graph
据我所知,对于此类问题,具有最佳大O运行时间
的
算法
是
Dijkstra
,
使用
斐波那契堆作为
优先级
队列
,尽管实际上二进制堆更容易实现,并且
工作
得也很好。然而,似乎即使
是
二进制堆也需要相当长
的
时间才能滚动,而且在比赛中时间
是
有限
的
。我知道STL提供了一些堆
算法
和
优先级
队列
,但它们似乎没有提供
Dijkstra
需要<em
浏览 4
提问于2009-12-08
得票数 1
回答已采纳
3
回答
如何
在线性时间内反转图形?
algorithm
、
data-structures
、
graph
、
dijkstra
我知道有两种方法来表示我
的
图形:一种
是
使用
矩阵,另一种
是
使用
列表。所以,我有另一个问题。例如,假设我在我
的
图(矩阵或列表)上
使用
<
浏览 3
提问于2013-04-23
得票数 11
回答已采纳
2
回答
边权有限
的
图上
的
Dijkstra
算法
algorithm
、
dijkstra
假设我们想在一个图上运行
Dijkstra
的
算法
,该图
的
边权值
是
范围{1,2,...,W}中
的
整数,其中W
是
一个相对较小
的
数。
如何
在s中找到从顶点t到t
的
最短路径 我从S. Dasgupta,C.Vazirani
的
书
算法
中遇到了这个问题。我可以证明,
如果
我们像以前一样实现
Dijkstra
算法
,那么在每次迭代时,
优先级</e
浏览 4
提问于2013-04-29
得票数 2
2
回答
什么时候
使用
堆作为
优先级
队列
是
个坏主意?
algorithm
、
heap
、
priority-queue
在解释
Dijkstra
算法
的
章节中,在Cormen等人
的
“
算法
简介”一书中。在分析
算法
的
复杂性时,他们说
如果
图
是
足够稀疏
的
..。通过
使用
二进制最小堆实现最小
优先级
队列
,可以对
算法
进行改进。所以我想知道,为什么要发表这样
的
声明?仅仅对
优先级
队列
使用
堆不是总是更明智
的<
浏览 4
提问于2013-09-26
得票数 1
2
回答
Dijkstra
算法
中
优先级
队列
的
实现
c++
、
queue
、
priority-queue
、
dijkstra
Dijkstra
的
算法
使用
了一个
优先级
队列
,该
队列
按距起始点
的
距离排序,但顶点
的
距离在
算法
过程中会发生变化。我不确定
优先级
队列
何时重新排序,但是否有以下比较器:{ { return( getD
浏览 1
提问于2013-03-07
得票数 1
1
回答
Dijkstra
的
算法
漏掉了什么边缘情况?
python
、
dijkstra
这是我
的
Dijkstra
的
实现。它正在传递pytest input.n.txt文件中
的
所有情况,但是当我提交评分软件(不提供测试或任何输出)时,我得到
的
结果无效。 我真的很难把它放在一起,不是因为我不理解
Dijkstra
算法
,而是因为很难调整已经添加到Python PriorityQueue类中
的
项
的
优先级
(它
的
使用
是通过在开始代码中导入
队列
来暗示
浏览 2
提问于2021-08-30
得票数 0
回答已采纳
1
回答
索引
优先级
队列
是否确实加快了
dijkstra
的
速度?
algorithm
、
data-structures
、
graph
、
graph-algorithm
、
dijkstra
“懒惰”
dijkstra
的
最短路径
算法
的
渐近时间复杂度为O(Elog(V)),它
使用
规则
优先级
队列
而不是索引堆。这意味着会有重复
的
节点,
算法
必须跳过这些节点,但是不管
如何
处理。解决这个问题
的
一个解决方案
是
使用
索引
优先级
队列
,但我对它在实际生活中和
使用
大O时是否真的比惰性版本更快感到困惑,因为懒惰版本仍然跳过<e
浏览 1
提问于2021-08-29
得票数 2
回答已采纳
2
回答
优先级
可调
的
优先级
队列
的
高级描述
java
、
graph-theory
、
priority-queue
在实现
Dijkstra
算法
和Prim
算法
时,我们需要一个
优先级
可调
的
队列
。我理解堆函数
的
基于数组
的
实现,但我不知道
如何
使
优先级
可调。我读过hashmap允许这样做,但我不明白
是
怎么回事。有人能给我一个高层次
的
描述这个实现
使用
一个hashmap
使用
一个例子。a,b,c,d,e,f分别有2,4,0,6,1,9
的
优先级</em
浏览 5
提问于2020-05-11
得票数 2
回答已采纳
1
回答
O((V+E)*W)中
的
Dijsktra
算法
algorithm
、
graph
假设我有一个有向图G(V,E),在它
的
edges.If上有一个积分正权,我知道对于每个边e∈E权(E)∈{0,1,..2^W}(其中W相对较小),我
如何
在O(V+E)*W中实现dijsktra
的
算法
?我尝试修改Dial
的
算法
,
如果
加权(E)∈{0,1,..,W},我可以
使用
桶并在O(∈)中实现dijsktra,但是我似乎不能取得好
的
结果。
浏览 0
提问于2019-01-24
得票数 2
回答已采纳
1
回答
理解
Dijkstra
优先级
队列
实现
的
困难
algorithm
、
shortest-path
我很难理解实现
Dijkstra
的
逻辑流程是什么,更确切地说,我遇到
的
问题
是
如何
得到
优先级
队列
,在图上执行
算法
时是否构建它(
优先级
队列
)?还是我看错了?那就是这样吗?我们
是
在此停止,还是通过将获取
的
信息以其他形式放置在
优先级
队列
中来进一步处理该输出,还是在这里停止?我还理解了为选择
的
节点生成相应
的
最短路径
浏览 2
提问于2020-04-23
得票数 0
回答已采纳
1
回答
引用到
优先级
队列
中
的
节点(迭代器)
c++
我试图用实现
Dijkstra
的
算法
(因为我需要跟踪离源节点最近
的
节点)。 问题
是
:当探索一个节点时,它可能会链接到
优先级
队列
中尚未发现
的
另一个节点(即
优先级
队列
的
一个元素)。
优先级
队列
似乎不支持迭代器,当发现与其关联
的
节点时,
如何
将引用到
优先级
队列
元素?
浏览 2
提问于2015-06-24
得票数 1
回答已采纳
1
回答
Dijkstra
算法
的
时间复杂度
time-complexity
、
runtime
、
dijkstra
据我所知,在最坏
的
情况下,
使用
队列
的
未加权图上
的
Dijkstra
算法
的
时间复杂度
是
O(n2)。我猜想这是因为od bfs和dfs。BFS在标记阶段处理所有顶点,dfs用于回溯。另外,对于加权图,我知道时间复杂度
是
O(EVlogV),其中E
是
边和V顶点。我认为这是因为
优先级
队列
,我知道
优先级
队列
是
如何</
浏览 26
提问于2020-06-04
得票数 0
1
回答
如何
在网格网络/图中找到所有连接?
relational-database
、
graph
、
facebook
、
ipv6
假设我有一系列
的
关系,例如需要在因特网上定位对等点
的
IPv6路由器我感兴趣
的
不仅仅是确定最短路径,还要确定每条路径
的
成本(通过添加任意权重)、每条路径
的
节点以及其他通常用于此通用需要
的
信息。理想情况下,我可以在手机或计算机上本地运行,并以O(N)
的
速度或更好
的
速度搜索大图。
浏览 0
提问于2013-09-22
得票数 1
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
Python实现平面最短路径算法
数据结构与算法(4)——优先队列和堆
什么是优先队列算法?详述优先队列算法的原理?用C语言实现优先队列算法。内附完整代码。
什么是MFQ调度算法?详述MFQ调度算法的原理?用C语言实现MFQ调度算法。内附代码。
Python中的5种队列数据结构,你知道几个?
热门
标签
更多标签
活动推荐
运营活动
广告
关闭
领券