对于一个无向、未加权的图，在计算其平均最短路径长度的算法的时间复杂度和计算图的直径的算法的复杂度，即两个顶点之间的最长最短路径方面，是否存在差异？
浏览 0提问于2011-08-02得票数 3
回答已采纳
我是Dijkstra算法的新手。 我的问题是:对于一个有n个结点和m个边的无向图G，Dijkstra算法寻找最短路径的时间复杂度是o((n+m)logn)。然而，如果G是连通的，为什么这个时间复杂度也可以表示为o(mlogn)？ 干杯
浏览 21提问于2021-04-18得票数 0
回答已采纳
1回答
中间中心性的时间复杂性？
、、、
如果给出图的最短路径前驱体矩阵，计算的时间复杂度是多少？i和j之间有多条最短路径，则可以是一个前导数组。我认为计算一个顶点的CB所花费的时间与计算所有顶点的CB的时间是相同的，因为Brandes算法不能适应这种情况。我知道我不能实现更小的时间复杂度，但我认为，时间的差异可以通过不计算所有7000个顶点的CB来实现。相反，通过拥有这个矩阵，我只能计算出一个顶点的CB。我认为可以计算O
浏览 1提问于2011-06-30得票数 0
1回答
我试图解决一个关于图的算法挑战，我已经将它分解为以下几个方面:给定一个无向生成树，找到2叶，使得它们之间的代价最小。现在我知道了Floyd算法，它可以找到具有时间复杂度O(N^3)和空间复杂度O(N^2)的所有对最短路径。问题的输入是N= 10^5，所以O(N^3)和O(N^2)太多了。有没有办法优化这个问题的时间和空间复杂度？
浏览 6提问于2017-03-07得票数 1
福特Fulkerson算法将在O(|E|f)时间内运行，其中f是最大流；但是，是否有方法使其运行O(|E|)？让它运行少于O(|E|f)的解决方案之一是选择一条允许流量最大增加的扩充路径，使用与使用加权最短路径问题等查找路径相关的东西，但我能保证它在O(|E|)时间运行吗？基本上忽略了寻找扩充路径所需的时间复杂度(即，无论算法是什么，让复杂度为O(1))。
如果没有这样的方法，那么
浏览 4提问于2014-04-13得票数 3
我读到了有关图算法的文章，我发现了这两种算法：
我找了很多关于这件事，但没有得到满意的答案！在图中查找最短路径的BFS规则如下：
这正是我们在Dijkstra
浏览 8提问于2014-08-22得票数 65
回答已采纳
2回答
给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra的算法？
我现在很挣扎
浏览 4提问于2014-02-04得票数 0
回答已采纳
1回答
有N个城市，有M个双向道路连接它们，我必须找到两个固定城市A和B之间的最短路径。dijkstra algorithm();
cout<&l
浏览 2提问于2014-12-30得票数 3
如何从谦卑中着手以下任务：
我可以通过使用BFS生成迷宫和搜索最短路径来找到最短路径，但是由于最坏的时间复杂度预计为O(N)，我不认为这是正确的方法。BFS的时间复杂度为O(x=0)，其中V为顶点数，E为边数。例如，如果N= 3，我们有一个大小为17x17的网格，很明显，我们不能在三个步骤中找到路径。因此，要么指出的时间复杂度是错误的，应该是像M^2，或者有一个快速的技巧，简单地计算两个点之间的距离
浏览 1提问于2016-08-04得票数 1
回答已采纳
1回答
设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
回答已采纳
1回答
弗洛伊德·沃尔复杂性
、、、、
有人能给我这个过程在for迭代中的时间复杂度吗？这段代码是FloydWarshall算法的“重构路径”部分。prevn是最短路径中源节点与目标节点之间节点的矩阵。在i和j之间插入最短路径的节点，通过我的计算，包括这个部分在^4上运行的循环，但是总的算法复杂度是在^3上，请告诉我！
浏览 2提问于2014-07-23得票数 0
回答已采纳
1回答
以圆为界的最短路径
、、、
我想找出从第一个圆的原点到最后一个圆的原点的最短路径的距离，并且路径上的任何一点都位于一个或多个圆的内部。 下面是位于(3，3)，(3，7)和(6，7)的三个圆的演示，蓝线是最短路径。 ? 我试图找到每一对圆的交点，并运行最短路径算法，但这会导致O(n^5)的时间复杂度。我想知道是否存在运行速度更快的更好的算法。谢谢。
浏览 53提问于2021-07-10得票数 3
回答已采纳
1回答
例如，(0,7) ->>>> (5,2)的答案是4，但我的算法是38。我的坐标轴是X:从左到右，Y轴:从上到下。请帮我解决我的问题。
浏览 0提问于2012-12-14得票数 0
回答已采纳
1回答
找到从顶点1到顶点N的最短路径，或者声明这种路径不存在。
我把它从另一个问题中拿出来，只是替换了变量名和一些单词，因为它听起来适用于这个问题。我如何表示最短的路径？它是路径的数目，所有路径</
浏览 2提问于2016-04-25得票数 0
回答已采纳
希望找到从节点a到任何节点的最短加权路径。未给出目标节点。一个人可以多次访问任何一个顶点。下一步的算法是什么？？无法检测到算法本身。
浏览 2提问于2015-04-05得票数 0
回答已采纳
1回答
我一直在练习各种算法，我刚刚完成了Dijkstra算法来计算图上节点之间的最短距离。在完成了利用索引minHeap的练习之后，我还完成了利用BFS (附带的解决方案)的练习。这让我想到了几个问题：
，如果我对时间复杂度的计算是正确的-我计算了附加解的复杂性为O(v^2 + e)，其中V=顶点数，E=边数。我们迭代和触摸每个节点一次，而且只有一次，边缘也是一样。shift操作，因为在每个iteration.This BFS解决方案上都可以通过利用类似于Java中的ArrayDeque来改进这一点，这将给我们
浏览 2提问于2021-01-18得票数 0
3回答
我正在实现一个k-最短顶点不相交路径算法，需要一个快速算法来找到最短路径。有负权重，所以我不能使用dijkstra和bellman-ford是O(ne)。在我最近读到的一篇论文中，作者使用了一种所谓的SPFA算法来寻找负权重图中的最短路径，根据他们的说法，该算法的复杂度为O(e)。听起来很有趣，但我似乎找不到关于算法的信息。有没有人有好的信息或者这个算法的实现？另
浏览 3提问于2011-10-10得票数 4
我已经读到图中是否存在的问题是NP-完全的，而且由于在多项式时间内运行，所以不能修改它以求最短的哈密顿路径。(这逻辑有效吗？)考虑到这些规范，现在是否有可能修改Dijkstra的算法，以A和Z为端点寻找最短哈密顿路径？(多项式时间)
注意:我只关心从两个节点找到最短哈密顿路径。例如，如果有一个包含26个节点(标记为A到Z)的图，那么通过所有点但从A开始到Z结束的最短路径是什么(我不关心寻找其他具有不
浏览 16提问于2014-06-25得票数 2
回答已采纳
1回答
有没有什么方法可以用多项式的复杂度(或者更好)得到一个无向图的第k条或k条最短路径？ 或者，Yen的k最短路径算法可以修改为无向图吗？
浏览 21提问于2018-12-31得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
