我是Dijkstra算法的新手。 我的问题是:对于一个有n个结点和m个边的无向图G，Dijkstra算法寻找最短路径的时间复杂度是o((n+m)logn)。然而，如果G是连通的，为什么这个时间复杂度也可以表示为o(mlogn)？ 干杯
浏览 21提问于2021-04-18得票数 0
回答已采纳
4回答
我在课本上偶然发现了这个问题：
a.图中的顶点数。两者都是关于图中顶点和边的数目。解释你的选择。
因此，根据维基百科Prim，Kruskal和Dijkstra的算法，最坏的情况时间复
浏览 5提问于2012-08-09得票数 2
1回答
我很难看到直接实现Dijkstra算法的O(mn)界限(没有堆)。在我的实现和其他实现中，我发现主循环迭代n-1次(对于不是源的每个顶点，n-1)，然后在每次迭代中找到最小顶点是O(n) (检查队列中的每个顶点并找到到源的最小距离)，然后每个发现的最小顶点最多有n-1在我看来，这似乎导致了O(n^2)的界限。下面提供了我的实现 public int[] dijkstra(int s
浏览 9提问于2019-12-24得票数 1
回答已采纳
1回答
我在读算法第三版的简介。解决这一问题的方法有3种。我的询问是关于其中两个人的。这是众所周知的</em
浏览 8提问于2016-05-16得票数 4
回答已采纳
我很难理解为什么带有堆的Dijkstra算法的复杂度是O( (m + n)*log(n) )，其中m是边的数量，n是顶点的数量。现在我知道必须做n删除mins。我的概念清楚了吗？另外，请您解释一下如何获得Dijkstra算法的时间复杂度。
浏览 0提问于2015-05-04得票数 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
我被困在我的算法任务中，要求在具有n个顶点(非循环间接图)的树(V，E)中找到从顶点v到顶点w的直接路径，时间复杂度为O(dist(v，w))。我必须找到一个预处理程序(在O(N)中运行)来存储一些信息，这样我就可以达到O(dist(v，w))的时间复杂度。 我需要一些想法来存储在预处理过程中，这将有助于稍后的算法。 没有完整的解决方案。我已经尝试存储可能
浏览 19提问于2019-05-25得票数 0
1回答
我一直在练习各种算法，我刚刚完成了Dijkstra算法来计算图上节点之间的最短距离。在完成了利用索引minHeap的练习之后，我还完成了利用BFS (附带的解决方案)的练习。这让我想到了几个问题：
，如果我对时间复杂度的计算是正确的-我计算了附加解的复杂性为O(v^2 + e)，其中V=顶点数，E=边数。我们迭代和触摸每个节点一次，而且只有一次，边缘也是一样。v^2来自shift操
浏览 2提问于2021-01-18得票数 0
1回答
“懒惰”dijkstra的最短路径算法的渐近时间复杂度为O(Elog(V))，它使用规则优先级队列而不是索引堆。这意味着会有重复的节点，算法必须跳过这些节点，但是不管如何处理。解决这个问题的一个解决方案是使用索引优先级队列，但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑，因为懒惰版本仍然跳过算法中的重复节点。通过一些研究，我还发现索引dijkstra比惰性实现<em
浏览 1提问于2021-08-29得票数 2
回答已采纳
如果给定图中的所有边都有相同的权重，Dijkstra的算法还能找到两个顶点之间的最短路径吗？谢谢!
浏览 6提问于2014-01-24得票数 3
回答已采纳
为了在无向加权图中找到最短路径，我比较了BFS和dijkstra的algo，以了解为什么我们需要优先级队列。下面的代码在我写的GeeksForGeeks上被接受了，而不是dijkstra :- } return dist;问题：
浏览 1提问于2021-09-11得票数 0
回答已采纳
1回答
图-具有顶点权的最短路径
、、、、
这是一项消费税：(a)假设图中的每个边的权重为零(而非边的代价为.Assume)，则Cv =1对于所有顶点1≤v≤n (即所有顶点都有相同的代价)。
浏览 3提问于2012-05-04得票数 21
回答已采纳
2回答
使用数组的Dijkstra算法的时间复杂度为O(V^2)，如果采用优先级队列，则可以进一步将复杂度提高到O(E log V)。但是它的空间复杂性如何呢？在两种情况下都是O(V)吗？
浏览 10提问于2018-06-14得票数 4
3回答
据我所知，dijkstra不能与负边权重一起工作。为此，我们必须使用行李员福特。我们认为，dijkstra可以或不能使用负权重边缘。我说的对吗？请指导我做这个?？
浏览 25提问于2016-08-06得票数 0
回答已采纳
1回答
据我所知，在最坏的情况下，使用队列的未加权图上的Dijkstra算法的时间复杂度是O(n2)。我猜想这是因为od bfs和dfs。BFS在标记阶段处理所有顶点，dfs用于回溯。它们都具有线性时间复杂度。但我不确定这个逻辑是否正确。
另外，对于加权图，我知道时间复杂度是O(EVlogV)，其中E是边和V顶点。我认为这是因为优先级队列，我知道优先级队列是如何工作的，但
浏览 26提问于2020-06-04得票数 0
1回答
Matlab图论渐近复杂性
、、、、
我最近对图论很感兴趣，在投资了MATLAB的生物信息学工具箱之后，我发现图形最短路径函数非常有用。然而，当使用该函数时，运行时间总是非常相似的，无论我将函数设置为广度优先搜索、Dijkstra算法还是Bellman算法。我尝试了不同数量的节点，从几百个到几十万个，但运行时间仍然几乎相同。现在，在MATLAB网站的图速记路径页面上，Dijkstra的算法显示了一个时间复杂度<
浏览 4提问于2014-04-29得票数 1
回答已采纳
1回答
我正在为我的学士论文做两个算法的研究: Floyd-Warshall和A*算法。在我的工作中，时间复杂度是两种算法比较中的一个重要部分。但由于A*中的启发式算法，算法的时间复杂度不是恒定的。我发现的唯一信息是，在最坏的情况下，时间复杂性可能是指数级的
浏览 188提问于2021-03-24得票数 0
回答已采纳
5回答
据我所知，对于此类问题，具有最佳大O运行时间的算法是Dijkstra，使用斐波那契堆作为优先级队列，尽管实际上二进制堆更容易实现，并且工作得也很好。然而，似乎即使是二进制堆也需要相当长的时间才能滚动，而且在比赛中时间是有限的。我知道STL提供了一些堆算法和优先级队列，但它们似乎没有提供Dijkstra需要的减键函数。还是我说错了？似乎另一种可能性是不使用Dijkstra的<
浏览 4提问于2009-12-08得票数 1
回答已采纳
我想知道二进制、二项式和Fibonacci堆之间的基本区别，以及它们最适合使用的场景。我主要关注的是他们在Dijkstra算法中的应用，根据所使用的堆的类型，它的时间复杂度将如何变化？
浏览 1提问于2015-11-20得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
