2回答
我试图通过创建一个基于循环和基于时间的大(O)图来评估我的python实现的Dijkstra算法的复杂性。我如何随机选择，比如说:5行，然后10行，15行，20行？
浏览 18提问于2018-02-08得票数 0
我是Dijkstra算法的新手。 我的问题是:对于一个有n个结点和m个边的无向图G，Dijkstra算法寻找最短路径的时间复杂度是o((n+m)logn)。然而，如果G是连通的，为什么这个时间复杂度也可以表示为o(mlogn)？ 干杯
浏览 21提问于2021-04-18得票数 0
回答已采纳
4回答
我在课本上偶然发现了这个问题：
a.图中的顶点数。两者都是关于图中顶点和边的数目。解释你的选择。
因此，根据维基百科Prim，Kruskal和Dijkstra的算法，最坏的情况时间复杂度分别是O(ElogV)
浏览 5提问于2012-08-09得票数 2
我很难理解为什么带有堆的Dijkstra算法的复杂度是O( (m + n)*log(n) )，其中m是边的数量，n是顶点的数量。现在我知道必须做n删除mins。我的概念清楚了吗？另外，请您解释一下如何获得Dijkstra算法的时间复杂度。
浏览 0提问于2015-05-04得票数 0
1回答
我在读算法第三版的简介。解决这一问题的方法有3种。我的询问是关于其中两个人的。这是众所周知的</em
浏览 8提问于2016-05-16得票数 4
回答已采纳
1回答
“懒惰”dijkstra的最短路径算法的渐近时间复杂度为O(Elog(V))，它使用规则优先级队列而不是索引堆。这意味着会有重复的节点，算法必须跳过这些节点，但是不管如何处理。解决这个问题的一个解决方案是使用索引优先级队列，但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑，因为懒惰版本仍然跳过算法中的重复节点。通过一些研究，我还发现索引dijkstra比惰性实现的O(
浏览 1提问于2021-08-29得票数 2
回答已采纳
为了在无向加权图中找到最短路径，我比较了BFS和dijkstra的algo，以了解为什么我们需要优先级队列。下面的代码在我写的GeeksForGeeks上被接受了，而不是dijkstra :- } return dist;问题：
浏览 1提问于2021-09-11得票数 0
回答已采纳
1回答
我一直在练习各种算法，我刚刚完成了Dijkstra算法来计算图上节点之间的最短距离。在完成了利用索引minHeap的练习之后，我还完成了利用BFS (附带的解决方案)的练习。这让我想到了几个问题：
，如果我对时间复杂度的计算是正确的-我计算了附加解的复杂性为O(v^2 + e)，其中V=顶点数，E=边数。我们迭代和触摸每个节点一次，而且只有一次，边缘也是一样。v^2来自shift操作，因为在每个it
浏览 2提问于2021-01-18得票数 0
8回答
根据我的理解，我已经计算了Dijkstra算法的时间复杂度，用下面给出的邻接列表作为大O表示法。它并没有像预期的那样出来，这让我一步一步地理解它。每个顶点可以连接到( V-1 )个顶点，因此每个顶点的相邻边数是V-1，假设E表示连接到每个顶点的V-1边。在最小堆中查找和更新每个相邻顶点的权重是O(log(V)) + O(1)或O(log(V))。
因此，从上面的step1和step2来看，更新一个顶点的<
浏览 8提问于2014-10-24得票数 113
回答已采纳
存储图形的一种方法是将节点实现为结构，例如int vertex; node* next; 其中vertex存储顶点编号，next包含指向其他节点的链接。我能想到的另一种方法是将其实现为向量，例如现在，在应用Dijkstra的最短路径算法时，我们需要构建优先级队列和其他所需的数据结构，上面两种不同的图形应用方法在<em
浏览 0提问于2014-01-15得票数 2
如果给定图中的所有边都有相同的权重，Dijkstra的算法还能找到两个顶点之间的最短路径吗？谢谢!
浏览 6提问于2014-01-24得票数 3
回答已采纳
我一直在尝试理解Dijkstra算法的内部原理，以找到加权图的最短路径。
访问完一个顶点后，为什么我们必须将相邻的顶点存储到一个PriorityQueue中，而不是普通的队列？我问上面问题的原因是:我知道用PriorityQueue我们可以从队列中得到最大/最小的数字。但在Dijkstra算法的情况下，我们无论如何都是在访问所有的顶点，而不考虑距离/优先级。在这种情况下，为什么我
浏览 2提问于2020-04-20得票数 0
3回答
据我所知，dijkstra不能与负边权重一起工作。为此，我们必须使用行李员福特。我们认为，dijkstra可以或不能使用负权重边缘。我说的对吗？请指导我做这个?？
浏览 25提问于2016-08-06得票数 0
回答已采纳
2回答
使用数组的Dijkstra算法的时间复杂度为O(V^2)，如果采用优先级队列，则可以进一步将复杂度提高到O(E log V)。但是它的空间复杂性如何呢？在两种情况下都是O(V)吗？
浏览 10提问于2018-06-14得票数 4
1回答
图-具有顶点权的最短路径
、、、、
这是一项消费税：(a)假设图中的每个边的权重为零(而非边的代价为.Assume)，则Cv =1对于所有顶点1≤v≤n (即所有顶点都有相同的代价)。
浏览 3提问于2012-05-04得票数 21
回答已采纳
2回答
给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra<e
浏览 4提问于2014-02-04得票数 0
回答已采纳
我读到了有关图算法的文章，我发现了这两种算法：
我找了很多关于这件事，但没有得到满意的答案！在图中查找最短路径的BFS规则如下：
浏览 8提问于2014-08-22得票数 65
回答已采纳
2回答
在有向无环图(DAG)上运行最短路径算法(通过使用回忆录的动态规划)具有运行时复杂度为O(V + E)的特性，可以使用以下公式进行验证：现在，Dijkstra的算法也要求有向图。该算法的运行时复杂度为O(E + V.log(V))，使用最小优先级队列，这显然比回忆录版本的DP慢。
根
浏览 4提问于2015-01-26得票数 2
回答已采纳
2回答
我昨晚一直在网上广泛搜索，直到今天，我似乎找不到讨论如何通过专门使用回溯算法来解决最短路径问题的资源。我试着用这个算法来解决这个问题，但是对我来说没有意义。*更新:只是好奇，回溯算法真的能解决最短路径问题吗？
浏览 2提问于2012-01-14得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
