腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(5351)
视频
沙龙
1
回答
Dijkstra
算法
时间
复杂度
algorithm
我是
Dijkstra
算法
的新手。 我的问题是:对于一个有n个结点和m个边的无向图G,
Dijkstra
算法
寻找
最短
路径
的时间
复杂度
是o((n+m)logn)。然而,如果G是连通的,为什么这个时间
复杂度
也可以表示为o(mlogn)? 干杯
浏览 21
提问于2021-04-18
得票数 0
回答已采纳
2
回答
在至多包含两个负边的图中求
最短
路径
距离
algorithm
、
graph
、
dijkstra
、
shortest-path
给出了一个有向图,其中每个边都有一个cost.Taking优点,即图中最多有两个负边,我的目标是求出从给定节点到V中所有节点的
最短
路径
距离。
算法
的时间
复杂度
应该是O(|E| + |V|*log|V|),所以我认为需要应用
Dijkstra
算法
。我猜想我需要以某种方式将我给定的图转换成一个新的图,该图中从s到v的
最短
路径
将等价于给定图中所需的
最短
路径
。或者我需要修改
Dijkstra
的
算法</em
浏览 4
提问于2014-02-04
得票数 0
回答已采纳
5
回答
BFS
算法
和
Dijkstra
算法
在寻找
最短
路径
时有什么区别?
algorithm
、
graph
、
breadth-first-search
、
shortest-path
、
dijkstra
我读到了有关图
算法
的文章,我发现了这两种
算法
: 我找了很多关于这件事,但没有得到满意的答案!在图中查找
最短
路径
的BFS规则如下: 这正是我们
浏览 8
提问于2014-08-22
得票数 65
回答已采纳
3
回答
Dijkstra
算法
= SSSP
algorithm
、
dijkstra
据我所知,
dijkstra
不能与负边权重一起工作。为此,我们必须使用行李员福特。我们认为,
dijkstra
可以或不能使用负权重边缘。
浏览 25
提问于2016-08-06
得票数 0
回答已采纳
1
回答
决定是否所有从s到t的
最短
路径
都包含边e
graph-algorithm
、
dijkstra
、
shortest-path
、
bellman-ford
设s,t是V中的2个顶点,E是e中的一条边,描述一个
算法
,该
算法
决定从s到t的所有
最短
路径
是否都包含边e。这就是实现Dijsktra时间
复杂度
的方法:只需从s运行
Dijkstra
并计算增量(s,t) (从s到t的
最短
路径
的权重)。删除边e,并从新图中的s再次运行Djikstra。如果新图中的增量(s,t)增加了,这意味着从s到t的所有
最短
路径
都包含边e,否则就不是真的。 我想知道是否有更有效的
算法
来
浏览 6
提问于2013-03-04
得票数 0
回答已采纳
2
回答
最短
路径
算法
:动态规划与
Dijkstra
算法
algorithm
、
time-complexity
、
dynamic-programming
、
dijkstra
在有向无环图(DAG)上运行
最短
路径
算法
(通过使用回忆录的动态规划)具有运行时
复杂度
为O(V + E)的特性,可以使用以下公式进行验证:现在,
Dijkstra
的
算法
也要求有向图。该
算法
的运行时
复杂度
为O(E + V.log(V)),使用最小优先级队列,这显然比回忆录版本的DP慢。 这是对无界非负权的任意有向图的最快速的单源<em
浏览 4
提问于2015-01-26
得票数 2
回答已采纳
3
回答
最短
路径
更快- SPFA
算法
?
graph
、
shortest-path
我正在实现一个k-
最短
顶点不相交
路径
算法
,需要一个快速
算法
来找到
最短
路径
。有负权重,所以我不能使用
dijkstra
和bellman-ford是O(ne)。在我最近读到的一篇论文中,作者使用了一种所谓的SPFA
算法
来寻找负权重图中的
最短
路径
,根据他们的说法,该
算法
的
复杂度
为O(e)。听起来很有趣,但我似乎找不到关于
算法
的信息。有没有人有好的信息或者这个
算法<
浏览 3
提问于2011-10-10
得票数 4
1
回答
包含3个项目的地图的最佳数据结构是什么
python
、
dictionary
让我们使用给定的值( sayIi,Destiny,Distance):B ~ C = 10我想找到从A到C的
最短
路径
(在本例中是A->B,B->C)。
浏览 0
提问于2017-08-19
得票数 0
1
回答
索引优先级队列是否确实加快了
dijkstra
的速度?
algorithm
、
data-structures
、
graph
、
graph-algorithm
、
dijkstra
“懒惰”
dijkstra
的
最短
路径
算法
的渐近时间
复杂度
为O(Elog(V)),它使用规则优先级队列而不是索引堆。这意味着会有重复的节点,
算法
必须跳过这些节点,但是不管如何处理。解决这个问题的一个解决方案是使用索引优先级队列,但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑,因为懒惰版本仍然跳过
算法
中的重复节点。通过一些研究,我还发现索引
dijkstra
比惰性实现的O(E)具有更好的空间
复杂度
,我不知道这是否提高了性能。
浏览 1
提问于2021-08-29
得票数 2
回答已采纳
1
回答
求循环图的最小加权生成树
algorithm
、
graph-algorithm
、
dijkstra
、
minimum-spanning-tree
我正试图解决上述问题,以下是我的尝试:问题:如果我完全错了,我会感激一个正确有效的解决方案。
浏览 2
提问于2015-12-15
得票数 0
回答已采纳
4
回答
最佳
最短
路径
算法
algorithm
、
shortest-path
“弗洛伊德-沃尔”
算法
“和”
Dijkstra
的
算法
“”之间有什么区别,哪种
算法
是图中
最短
路径
的最佳选择?我需要计算网络中所有对之间的
最短
路径
,并将结果保存到一个数组中,如下所示:A 0 10 15 5 20 B 10
浏览 20
提问于2009-12-04
得票数 27
回答已采纳
1
回答
通过给定集合的两个顶点之间的最小
路径
algorithm
、
data-structures
、
graph-theory
、
graph-algorithm
此外,从S到D的总体
路径
应该只包含一个从集合A到集合A的节点。我不想用蛮力的方法。
浏览 0
提问于2014-04-09
得票数 1
2
回答
当所有边都具有相同的权重时
Dijkstra
算法
dijkstra
如果给定图中的所有边都有相同的权重,
Dijkstra
的
算法
还能找到两个顶点之间的
最短
路径
吗?谢谢!
浏览 6
提问于2014-01-24
得票数 3
回答已采纳
1
回答
关于
最短
路径
算法
的几个问题
algorithms
、
graph
、
algorithm-analysis
、
dijkstra
我想弄明白为什么有人更喜欢弗洛伊德-沃夏尔而不是迪克斯特拉:弗洛伊德-沃夏尔做了一个完整的名单和过滤器在那里。我唯一能想象的是巨大的图表,在这种情况下,
Dijkstra
只给出了一个解,结果是给出结果的时间非常长。弗洛伊德-华沙尔,然而,已经开始吐出不同的可能性,并试图一点一滴地改进(例如,基于启发式)。
浏览 0
提问于2023-01-20
得票数 1
回答已采纳
2
回答
为什么在
Dijkstra
算法
中使用PriorityQueue?
algorithm
、
data-structures
、
priority-queue
、
shortest-path
、
dijkstra
我一直在尝试理解
Dijkstra
算法
的内部原理,以找到加权图的
最短
路径
。我错过了什么吗?
浏览 2
提问于2020-04-20
得票数 0
1
回答
带更新的
最短
路径
算法
java
、
algorithm
、
shortest-path
有N个城市,有M个双向道路连接它们,我必须找到两个固定城市A和B之间的
最短
路径
。for u in Q:graph[a][b] = graph[b][a] = INFINITY VALUE <em
浏览 2
提问于2014-12-30
得票数 3
1
回答
动态规划:在有障碍物的网格中寻找
最短
路径
algorithm
、
graph
、
dynamic-programming
我试图从Skiena的
算法
设计手册中解决以下问题 鉴于这个问题来自于动态规划一章,我试图找出如何使用动态规划来解决这个问题。相交(
浏览 1
提问于2017-01-04
得票数 0
2
回答
我们能用
dijkstra
算法
找到任何循环吗?
data-structures
、
graph-theory
、
dijkstra
我们能用
Dijkstra
的
算法
找到循环吗? 如果我们能做什么,我们必须要做的改变吗?
浏览 5
提问于2014-07-02
得票数 0
回答已采纳
1
回答
这种基于BFS的
算法
是否适用于在加权图中查找
最短
路径
algorithm
、
breadth-first-search
、
shortest-path
我知道普通的BFS搜索可以用来在无权图或边权相同的图中寻找
最短
路径
,而
Dijkstra
应该用在加权图中,
Dijkstra
可以看作是BFS的变体。但我想知道,如果每次更新distw时,我都将节点推送到队列中,而不是在普通的BFS搜索中只推送一次,那么这个
算法
是否适用于寻找
最短
路径
?我在一个leetcode问题上尝试了这个
算法
,它是有效的,但是leetcode问题只检查有限的测试用例,所以我不能证明这个
算法
的正确性。如果
算法</e
浏览 36
提问于2020-12-10
得票数 0
回答已采纳
1
回答
带最小边的
Dijkstra
算法
algorithm
、
graph
、
dijkstra
、
breadth-first-search
首先,让我们定义
算法
:
Dijkstra
算法
在具有非负边权的有向图中寻找单源
最短
路径
.如果我有一个源S和目标T,我可以用
Dijkstra
算法
在这两个顶点之间找到
最短
路径
,但是我想要找到这两个顶点之间的
最短
路径
,这两个顶点之间的边数不超过形式K。第一部分是
Dijkstra
算法
,第二部分是BFS
算法
,因为我们可以用BFS
算法
在无加权
浏览 2
提问于2015-02-16
得票数 4
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
OSPF 中的最短路径算法:Dijkstra 算法
什么是最短路径算法?详述最短路径算法的原理?用C语言实现最短路径算法。内附完整代码。
图的最短路径算法-Floyd算法-弗洛伊德算法
计量地理学 最短路径算法
揽货最短路径解决方案算法-C#蚁群优化算法实现
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券