我正在学习Dijkstra的算法来寻找最短路径。我注意到有一个优先级队列来帮助提取顶点集中优先级最低的顶点。如果我从顶点集中选择一个顶点，而不是优先级最低的顶点，那么该算法是否仍然有效?如果是，那么时间复杂度如何？维基百科最初的Dijkstra算法如下： dist[source] ← 0prev[v] ← u
Q.decreas
浏览 4提问于2017-10-27得票数 0
1回答
我正在研究A*搜索算法，并看到了以下示例：该算法的描述如下：更新节点1到3的距离和优先级到9.32455532033676当前优先级最低为9.32455532033676的访问节点1更新节点4到13的距离和优先级到15.8284271
浏览 3提问于2022-11-07得票数 0
回答已采纳
4回答
尽管如此，我想让你暂时忽略一下我试图用算法解决的问题，帮助我分析我编写的算法的巨大复杂性--在一个图中使用深度限制搜索的所有简单路径，如，并实现了。谢谢!原问题如下：因此，和是相关的。我正在努力解决问题。这通常需要在一对演员之间找
浏览 8提问于2009-12-02得票数 3
回答已采纳
当支持度和置信度的百分比值给定时，如何在Apriori算法中找到最小支持度。例如，当支持度和置信度分别为60%和60%时，最低支持度是多少？
浏览 11提问于2012-04-28得票数 12
回答已采纳
3回答
我正在学习不同的排序算法及其时间/空间复杂度，并看到冒泡排序和插入排序等算法的空间复杂度为O(1)。
这让我感到奇怪，因为最低的空间复杂度肯定是O(n) (例如，存储数据集所需的内存，仅此而已)？
浏览 1提问于2017-05-10得票数 7
回答已采纳
如何修改福特bellman算法，使其在while循环的m+1次迭代后停止。M是最小路径中的最大弧数(根据权重而不是道路中拱门的数量确定的最小道路)
浏览 6提问于2020-07-03得票数 0
一位朋友告诉我，宽度优先搜索算法(由邻接列表表示的图)具有二次时间复杂度。但是在所有的消息来源中，BFS算法的复杂度恰恰是O(x=0)或O (n + m)，由此我们得到了二次复杂度？
浏览 4提问于2014-01-15得票数 0
回答已采纳
有人能告诉我这个Dijkstra algo中优先级队列的空间复杂性吗？请注意，在这里，可以添加一个顶点来排队超过一次。但是，由于访问集的原因，它不会被处理超过一次。
浏览 3提问于2019-12-18得票数 3
回答已采纳
我正在做一个作业题，我需要从顶点z开始运行bellman-ford算法，它要求我“在每一次遍历中，以与图中相同的顺序放松边，并在每次遍历后显示d和pi值。”据我所知，我认为这个算法像BFS一样遍历图形，这从他们想要我使用的图形中是有意义的，所以我看不出相同的路径是如何工作的。如果有人能通过指出如何开始来给我指出正确的方向，那将是非常有用的。
浏览 0提问于2011-11-27得票数 2
回答已采纳
1回答
我试图找到一个算法，对于给定的数组A= a1，a2，.，如果有两个索引I !== j，使得gcd(ai，aj) =1(否则为false )，则整数的a_n返回true。我试图将这个算法的复杂度降到最低。
当然，显而易见的解决方案是对每对(ai，aj)使用欧几里得算法，但是它的复杂度是n(n+1)/2的欧几里德算法的复杂度的一倍。
浏览 3提问于2014-11-15得票数 1
回答已采纳
1回答
我知道一些现有的路径查找算法:深度优先搜索，Dijkstra算法，A*等等。
现在，我想要一个算法，给我N个路径，以最低的成本。这是否可以通过简单的修改以上之一得到？或者需要一种不同的算法，如果需要，那么是哪种算法？
浏览 0提问于2016-11-20得票数 4
回答已采纳
1回答
有人能告诉我排序的线程安全原子(无锁)链表/优先级队列的算法吗？我知道如何仅仅做一个链接列表本身，但现在我需要一个排序。与未排序的列表相比，我不确定这是否是微小的更改或重大的重新设计，因此在创建自己的列表之前，我希望看到一个现有的算法。它实际上不需要是一个列表(或技术排序)，但它的行为就像一个具有以下属性的优先级队列：
timemodification locks)insertion/removal最低元素是具有最小整数字段值的最低元素，它仅通过原子操作(在线性时间中
浏览 3提问于2011-03-26得票数 6
回答已采纳
1回答
“懒惰”dijkstra的最短路径算法的渐近时间复杂度为O(Elog(V))，它使用规则优先级队列而不是索引堆。这意味着会有重复的节点，算法必须跳过这些节点，但是不管如何处理。解决这个问题的一个解决方案是使用索引优先级队列，但我对它在实际生活中和使用大O时是否真的比惰性版本更快感到困惑，因为懒惰版本仍然跳过算法中的重复节点。通过一些研究，我还发现索引dijkstra比惰性实现的O(E)具有更好的空间复杂度，我不知道这是否提高了性能。
浏览 1提问于2021-08-29得票数 2
回答已采纳
我正在为堆编写siftup算法，我被困在了问题的末尾。问题的最后一部分说，该算法应该具有对数最坏的时间复杂度，即O(log(n)。我编写了下面的算法，其中i是堆中元素的索引，v是堆数组。根的索引是最低的，而对于堆的最低子节点则是它的最大值。我正在考虑数组从1到nSiftup (v, i) { v[i/2] = temp
i = i
浏览 2提问于2013-02-14得票数 0
回答已采纳
1回答
我有一个复杂度为O(n)的Add方法。我想知道，在不将整个列表转换为字符串/int/long(如果可能的话计算列表)的情况下，是否可以以任何方式将这两个数字相乘，并将其保持在O(n^2)的复杂性上。
浏览 4提问于2014-01-31得票数 1
回答已采纳
1回答
据我所知，在最坏的情况下，使用队列的未加权图上的Dijkstra算法的时间复杂度是O(n2)。我猜想这是因为od bfs和dfs。BFS在标记阶段处理所有顶点，dfs用于回溯。它们都具有线性时间复杂度。但我不确定这个逻辑是否正确。
另外，对于加权图，我知道时间复杂度是O(EVlogV)，其中E是边和V顶点。我认为这是因为优先级队列，我知道优先级队列是如何工作的，但仍然不理解O符号。
浏览 26提问于2020-06-04得票数 0
讨论不同的想法、算法和权衡。(隔离度定义：)我能想到的候选算法有:广度优先搜索(BFS)，深度优先搜索(DFS)，深度限制搜索(DLS)，迭代加深搜索(IDS)。很有可能的是，即使当两个人连接在一起(即分离度= 1)时，算法也可能长时间沿着错误的路径进行搜索。
BFS保证找到最小的分离度(因为图没有加权)。假设最大分支因子为b，两个目标人之间的实际分离度为d，则时间复杂度和空间复杂度<
浏览 0提问于2013-03-10得票数 7
回答已采纳
1回答
我最近有一个关于A星形算法的Java实现的课程工作，其中输入数据是20 * 20网格的形式。PriorityQueue<GridPiece> unvisit
浏览 0提问于2018-04-29得票数 0
云服务器
ICP备案
云直播
对象存储
实时音视频
腾讯云开发者
