Dijkstra算法时间复杂度

文章/答案/技术大牛

发布

1回答

algorithm

我是Dijkstra算法的新手。我的问题是:对于一个有n个结点和m个边的无向图G，Dijkstra算法寻找最短路径的时间复杂度是o((n+m)logn)。然而，如果G是连通的，为什么这个时间复杂度也可以表示为o(mlogn)？干杯

浏览 21提问于2021-04-18得票数 0

回答已采纳

4回答

图算法的时间复杂度取决于什么？

time-complexity、dijkstra、prims-algorithm、kruskals-algorithm

我在课本上偶然发现了这个问题： a.图中的顶点数。两者都是关于图中顶点和边的数目。因此，根据维基百科Prim，Kruskal和Dijkstra的算法，最坏的情况时间复杂度分别是O(ElogV)，O(ElogV)和O(E+VlogV)。所以我想答案是c？但是为什么呢？

浏览 5提问于2012-08-09得票数 2

1回答

DAG拓扑排序图中松弛边的Dijkstra算法

algorithm、graph、graph-theory、dijkstra

我在读算法第三版的简介。解决这一问题的方法有3种。我的询问是关于其中两个人的。这是众所周知的。正如书中所显示的，没有名字的时间复杂度是O(V+E)，而Dijstra的时间复杂度是O(ElogV)。我们不能用负重的Dijkstra，但我们可以用另一个。使用Dijkstra算法除了可以用于循

浏览 8提问于2016-05-16得票数 4

回答已采纳

1回答

Dijkstra算法的运行时间--优先级队列(堆)

algorithm、time-complexity、dijkstra

我很难理解为什么带有堆的Dijkstra算法的复杂度是O( (m + n)*log(n) )，其中m是边的数量，n是顶点的数量。现在我知道必须做n删除mins。另外，请您解释一下如何获得Dijkstra算法的时间复杂度。

浏览 0提问于2015-05-04得票数 0

8回答

理解Dijkstra算法的时间复杂度计算

algorithm、graph、big-o、time-complexity、dijkstra

根据我的理解，我已经计算了Dijkstra算法的时间复杂度，用下面给出的邻接列表作为大O表示法。它并没有像预期的那样出来，这让我一步一步地理解它。因此，从上面的step1和step2来看，更新一个顶点的所有相邻顶点的时间复杂度是E*(logV)。或E*logV.因此，所有V点的时间复杂度都是V* (E*logV)，即O(VElogV)。但是Dijkstra算法的时间复杂度

浏览 8提问于2014-10-24得票数 113

回答已采纳

1回答

dijkstra最短路径算法的时间复杂度是否依赖于所使用的数据结构？

c++、data-structures、graph-algorithm、dijkstra

我能想到的另一种方法是将其实现为向量，例如现在，在应用Dijkstra的最短路径算法时，我们需要构建优先级队列和其他所需的数据结构，上面两种不同的图形应用方法在复杂度上会有什么不同吗？哪一个更可取？编辑:在第一种情况下，每个节点都与可从给定节点直接访问的节点的链表相关联。

浏览 0提问于2014-01-15得票数 2

1回答

Dijkstra算法复杂度与BFS复杂度

time-complexity、big-o、breadth-first-search、dijkstra

我一直在练习各种算法，我刚刚完成了Dijkstra算法来计算图上节点之间的最短距离。在完成了利用索引minHeap的练习之后，我还完成了利用BFS (附带的解决方案)的练习。这让我想到了几个问题：，如果我对时间复杂度的计算是正确的-我计算了附加解的复杂性为O(v^2 + e)，其中V=顶点数，E=边数。我们迭代和触摸每个节点一次，而且只有一次，边缘也是一样。shift操作，因为在每个iteration.This BFS解决方案上都可以通过利用类似于Java中的ArrayDeque来改进这一点，这将给我们

浏览 2提问于2021-01-18得票数 0

1回答

索引优先级队列是否确实加快了dijkstra的速度？

algorithm、data-structures、graph、graph-algorithm、dijkstra

“懒惰”dijkstra的最短路径算法的渐近时间复杂度为O(Elog(V))，它使用规则优先级队列而不是索引堆。这意味着会有重复的节点，算法必须跳过这些节点，但是不管如何处理。解决这个问题的一个解决方案是使用索引优先级队列，但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑，因为懒惰版本仍然跳过算法中的重复节点。通过一些研究，我还发现索引dijkstra比惰性实现的O(E)具有更好的空间复杂度，我不知道这是否提高了性能。

浏览 1提问于2021-08-29得票数 2

回答已采纳

2回答

当所有边都具有相同的权重时Dijkstra算法

dijkstra

如果给定图中的所有边都有相同的权重，Dijkstra的算法还能找到两个顶点之间的最短路径吗？谢谢!

浏览 6提问于2014-01-24得票数 3

回答已采纳

1回答

我修改了BFS以在加权无向图中找到最短路径，而不是使用Dijkstra的algo，它起作用了。

c++、data-structures、graph、breadth-first-search、dijkstra

为了在无向加权图中找到最短路径，我比较了BFS和dijkstra的algo，以了解为什么我们需要优先级队列。下面的代码在我写的GeeksForGeeks上被接受了，而不是dijkstra :- vector <int> dijkstra(int vertices, vector<vector问题：-或者如果这是一个正确的方法，那么时间的复杂性是什么？(也许是因为时间比dijkstra更复

浏览 1提问于2021-09-11得票数 0

回答已采纳

1回答

图-具有顶点权的最短路径

algorithm、data-structures、graph、shortest-path、dijkstra

给出了一种从a到b寻找最便宜路径的有效算法及其时间复杂度。(a)使用正常的BFS；(c) 也使用dijkstra算法

浏览 3提问于2012-05-04得票数 21

回答已采纳

2回答

Dijkstra算法的空间复杂度是多少？

algorithm、graph-algorithm、dijkstra

使用数组的Dijkstra算法的时间复杂度为O(V^2)，如果采用优先级队列，则可以进一步将复杂度提高到O(E log V)。但是它的空间复杂性如何呢？在两种情况下都是O(V)吗？

浏览 10提问于2018-06-14得票数 4

3回答

Dijkstra算法= SSSP

algorithm、dijkstra

 据我所知，dijkstra不能与负边权重一起工作。为此，我们必须使用行李员福特。我们认为，dijkstra可以或不能使用负权重边缘。

浏览 25提问于2016-08-06得票数 0

回答已采纳

1回答

Dijkstra算法的时间复杂度

time-complexity、runtime、dijkstra

据我所知，在最坏的情况下，使用队列的未加权图上的Dijkstra算法的时间复杂度是O(n2)。我猜想这是因为od bfs和dfs。BFS在标记阶段处理所有顶点，dfs用于回溯。它们都具有线性时间复杂度。但我不确定这个逻辑是否正确。另外，对于加权图，我知道时间复杂度是O(EVlogV)，其中E是边和V顶点。

浏览 26提问于2020-06-04得票数 0

1回答

Matlab图论渐近复杂性

algorithm、matlab、graph、runtime、complexity-theory

然而，当使用该函数时，运行时间总是非常相似的，无论我将函数设置为广度优先搜索、Dijkstra算法还是Bellman算法。我尝试了不同数量的节点，从几百个到几十万个，但运行时间仍然几乎相同。现在，在MATLAB网站的图速记路径页面上，Dijkstra的算法显示了一个时间复杂度，这意味着它将比其他两种算法快得多。从我所读到的情况来看，时间复杂性更像是最坏的情况，但我预计运行时至少会有细微的差异。见这

浏览 4提问于2014-04-29得票数 1

回答已采纳

5回答

编程竞赛最好的单源最短路径算法是什么？

c++、algorithm、graph

据我所知，对于此类问题，具有最佳大O运行时间的算法是Dijkstra，使用斐波那契堆作为优先级队列，尽管实际上二进制堆更容易实现，并且工作得也很好。然而，似乎即使是二进制堆也需要相当长的时间才能滚动，而且在比赛中时间是有限的。我知道STL提供了一些堆算法和优先级队列，但它们似乎没有提供Dijkstra需要的减键函数。还是我说错了？似乎另一种可能性是不使用Dijkstra的，有人声称他们用广度优先搜索/贝尔曼-福特解决了上面的问题，这更容易编码

浏览 4提问于2009-12-08得票数 1

回答已采纳

1回答

二进制、二项式和斐波那契堆之间有什么区别？

data-structures、heap、dijkstra

我主要关注的是他们在Dijkstra算法中的应用，根据所使用的堆的类型，它的时间复杂度将如何变化？

浏览 1提问于2015-11-20得票数 2

回答已采纳

2回答

在至多包含两个负边的图中求最短路径距离

algorithm、graph、dijkstra、shortest-path

算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。或者我需要修改Dijkstra的算法？我现在很挣扎。任何帮助都将不胜感激！

浏览 4提问于2014-02-04得票数 0

回答已采纳

5回答

BFS算法和Dijkstra算法在寻找最短路径时有什么区别？

algorithm、graph、breadth-first-search、shortest-path、dijkstra

我读到了有关图算法的文章，我发现了这两种算法：我找了很多关于这件事，但没有得到满意的答案！这正是我们在Dijkstra算法中所做的事情！如果有人能用伪代码来解释它，我会非常感激的！我知道我错过了什么！请帮帮我！

浏览 8提问于2014-08-22得票数 65

回答已采纳

1回答

给定一棵树T= (V，E)，找出从顶点v到顶点w的直接路径

python、tree、pseudocode、direct-path

我被困在我的算法任务中，要求在具有n个顶点(非循环间接图)的树(V，E)中找到从顶点v到顶点w的直接路径，时间复杂度为O(dist(v，w))。我必须找到一个预处理程序(在O(N)中运行)来存储一些信息，这样我就可以达到O(dist(v，w))的时间复杂度。我需要一些想法来存储在预处理过程中，这将有助于稍后的算法。没有完整的解决方案。我已经尝试存储可能的路径，但要创建一个全局调整列表，我需要O(n^2)的二次时间。此外，Dijkstra的运行<em

浏览 19提问于2019-05-25得票数 0

点击加载更多