对于一个无向、未加权的图，在计算其平均最短路径长度的算法的时间复杂度和计算图的直径的算法的复杂度，即两个顶点之间的最长最短路径方面，是否存在差异？
浏览 0提问于2011-08-02得票数 3
回答已采纳
3回答
我正在实现一个k-最短顶点不相交路径算法，需要一个快速算法来找到最短路径。有负权重，所以我不能使用dijkstra和bellman-ford是O(ne)。在我最近读到的一篇论文中，作者使用了一种所谓的SPFA算法来寻找负权重图中的最短路径，根据他们的说法，该算法的复杂度为O(e)。听起来很有趣，但我似乎找不到关
浏览 3提问于2011-10-10得票数 4
1回答
有没有什么方法可以用多项式的复杂度(或者更好)得到一个无向图的第k条或k条最短路径？ 或者，Yen的k最短路径算法可以修改为无向图吗？
浏览 21提问于2018-12-31得票数 0
2回答
在有向无环图(DAG)上运行最短路径算法(通过使用回忆录的动态规划)具有运行时复杂度为O(V + E)的特性，可以使用以下公式进行验证：现在，Dijkstra的算法也要求有向图。该算法的运行时复杂度为O(E + V.log(V))，使用最小优先级队列，这显然比回忆录版本的</
浏览 4提问于2015-01-26得票数 2
回答已采纳
1回答
有约束的弗洛伊德·沃尔
、、、
我想知道是否可以使用具有约束条件的floyd warshall，这意味着您有一组大小为logn的“特殊顶点”，并且您想要计算所有最短路径，但是每条路径必须至少经过一个“特殊顶点”，这是可能的还是很难的np
浏览 5提问于2020-12-23得票数 2
回答已采纳
我读到了有关图算法的文章，我发现了这两种算法：
我找了很多关于这件事，但没有得到满意的答案！在图中查找最短路径的BFS规则如下：
存储从源u到顶点v的距离(重量/长度)。更新的路
浏览 8提问于2014-08-22得票数 65
回答已采纳
我是Dijkstra算法的新手。 我的问题是:对于一个有n个结点和m个边的无向图G，Dijkstra算法寻找最短路径的时间复杂度是o((n+m)logn)。然而，如果G是连通的，为什么这个时间复杂度也可以表示为o(mlogn)？ 干杯
浏览 21提问于2021-04-18得票数 0
回答已采纳
2回答
给出了一个有向图，其中每个边都有一个cost.Taking优点，即图中最多有两个负边，我的目标是求出从给定节点到V中所有节点的最短路径距离。算法的时间复杂度应该是O(|E| + |V|*log|V|)，所以我认为需要应用Dijkstra算法。我猜想我需要以某种方式将我给定的图转换成一个新的图，该图中从s到v的最短路径将等价于给定图中所需的
浏览 4提问于2014-02-04得票数 0
回答已采纳
1回答
弗洛伊德·沃尔复杂性
、、、、
有人能给我这个过程在for迭代中的时间复杂度吗？这段代码是FloydWarshall算法的“重构路径”部分。prevn是最短路径中源节点与目标节点之间节点的矩阵。printAllSP在迭代中运行了n^2次，但我无法真正计算出它每次执行的递归调用的次数，只知道这取决于i值(max n)、j值(Max n)和k(？？)在i和j之间插入最短路径的节点，通过我的<
浏览 2提问于2014-07-23得票数 0
回答已采纳
2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。input A
set B[i, j] = 0 for i =
浏览 8提问于2021-02-22得票数 1
1回答
以圆为界的最短路径
、、、
存在半径为r的n圆，i-th圆的原点位于(x[i], y[i])。我想找出从第一个圆的原点到最后一个圆的原点的最短路径的距离，并且路径上的任何一点都位于一个或多个圆的内部。下面是位于(3，3)，(3，7)和(6，7)的三个圆的演示，蓝线是最短路径。 ? 我试图找到每一对圆的交点，并运行最短</e
浏览 53提问于2021-07-10得票数 3
回答已采纳
1回答
我试图解决一个关于图的算法挑战，我已经将它分解为以下几个方面:给定一个无向生成树，找到2叶，使得它们之间的代价最小。现在我知道了Floyd算法，它可以找到具有时间复杂度O(N^3)和空间复杂度O(N^2)的所有对最短路径。问题的输入是N= 10^5，所以O(N^3)和O(N^2)太多了。有没有办法优化这个问题的时间和空间复杂度？
浏览 6提问于2017-03-07得票数 1
1回答
我试图从Skiena的算法设计手册中解决以下问题
8-16考虑一个城市，其街道由X，x，Y网格定义。我们感兴趣的是从网格的左上角走到右下角。不幸的是，这座城市有着糟糕的社区，我们不想走进这些街区的十字路口。给出了一个坏的X×Y矩阵，其中BADi，j=“是”当且仅当街道i和j之间的交点在一个邻域以避免。(c)给出一个O(XY)算法，以在网格中找到避免不良邻域的最短路径</e
浏览 1提问于2017-01-04得票数 0
1回答
中间中心性的时间复杂性？
、、、
如果给出图的最短路径前驱体矩阵，计算的时间复杂度是多少？前身矩阵单元如下所示：
我对Brandes算法很熟悉。但是，Bra
浏览 1提问于2011-06-30得票数 0
1回答
有N个城市，有M个双向道路连接它们，我必须找到两个固定城市A和B之间的最短路径。
但是问题是，如果有Q查询，那么两个城市之间的路径会被阻塞，我必须在每个Q查询中找到最短的路径。在我的蛮力算法中，我的时间复杂度是O(QNlogN)，它给了我超过错误的时间限制，我如何改进我的解决方案请帮助。graph[a][b] = graph[b][a] = IN
浏览 2提问于2014-12-30得票数 3
福特Fulkerson算法将在O(|E|f)时间内运行，其中f是最大流；但是，是否有方法使其运行O(|E|)？让它运行少于O(|E|f)的解决方案之一是选择一条允许流量最大增加的扩充路径，使用与使用加权最短路径问题等查找路径相关的东西，但我能保证它在O(|E|)时间运行吗？基本上忽略了寻找扩充路径所需的时间复杂度(即，无论算法是什么，让复杂度为O(1))。
如果没
浏览 4提问于2014-04-13得票数 3
1回答
设G= (V;E)是边都具有非负权的有向图。设s，t是V中的2个顶点，E是e中的一条边，描述一个算法，该算法决定从s到t的所有最短路径是否都包含边e。这就是实现Dijsktra时间复杂度的方法:只需从s运行Dijkstra并计算增量(s，t) (从s到t的最短路径的权重)。删除边e，并从新图中的s再次运行Djikstra。如果新
浏览 6提问于2013-03-04得票数 0
回答已采纳
如何从谦卑中着手以下任务：
我可以通过使用BFS生成迷宫和搜索最短路径来找到最短路径，但是由于最坏的时间复杂度预计为O(N)，我不认为这是正确的方法。BFS的时间复杂度为O(x=0)，其中V为顶点数，E为边数。例如，如果N= 3，我们有一个大小为17x17的网格，很明显，我们不能在三个步骤中找到路径。因此，要么指出的时间复杂度是错误的，应该是像M
浏览 1提问于2016-08-04得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
