对于一个无向、未加权的图，在计算其平均最短路径长度的算法的时间复杂度和计算图的直径的算法的复杂度，即两个顶点之间的最长最短路径方面，是否存在差异？
浏览 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))，使用最小优先级队列，这显然比回忆录版本的DP慢。
这是对无界非负权的任意有向图的最快速的单源最短<
浏览 4提问于2015-01-26得票数 2
回答已采纳
1回答
有约束的弗洛伊德·沃尔
、、、
我想知道是否可以使用具有约束条件的floyd warshall，这意味着您有一组大小为logn的“特殊顶点”，并且您想要计算所有最短路径，但是每条路径必须至少经过一个“特殊顶点”，这是可能的还是很难的np
浏览 5提问于2020-12-23得票数 2
回答已采纳
我读到了有关图算法的文章，我发现了这两种算法：
我找了很多关于这件事，但没有得到满意的答案！在图中查找最短路径的BFS规则如下：
这正是我们在Dijkstra
浏览 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的最短路径将等价于给定图中所需的最短路径。或者我需要修改Dijkstra的算法？
我现在很挣扎。任何帮助都将不胜
浏览 4提问于2014-02-04得票数 0
回答已采纳
1回答
弗洛伊德·沃尔复杂性
、、、、
有人能给我这个过程在for迭代中的时间复杂度吗？这段代码是FloydWarshall算法的“重构路径”部分。prevn是最短路径中源节点与目标节点之间节点的矩阵。在i和j之间插入最短路径的节点，通过我的计算，包括这个部分在^4上运行的循环，但是总的算法复杂度是在^3上，请告诉我！
浏览 2提问于2014-07-23得票数 0
回答已采纳
2回答
最宽路径的Floyd算法
、、、、
我一直在研究加权有向图的图算法，特别是Floyd关于所有对最短路径问题的算法。这是我的伪代码实现。input A
set B[i, j] = 0 for i = 1 to n: b_ij = min
浏览 8提问于2021-02-22得票数 1
1回答
以圆为界的最短路径
、、、
我想找出从第一个圆的原点到最后一个圆的原点的最短路径的距离，并且路径上的任何一点都位于一个或多个圆的内部。 下面是位于(3，3)，(3，7)和(6，7)的三个圆的演示，蓝线是最短路径。 ? 我试图找到每一对圆的交点，并运行最短路径算法，但这会导致O(n^5)的时间复杂度。我想知道是否存在运行速度更快的更好的算法。谢谢。
浏览 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的算法设计手册中解决以下问题
鉴于这个问题来自于动态规划一章，我试图找出如何使用动态规划来解决这个问题。相交(
浏览 1提问于2017-01-04得票数 0
1回答
中间中心性的时间复杂性？
、、、
如果给出图的最短路径前驱体矩阵，计算的时间复杂度是多少？前身矩阵单元如下所示：
我对Brandes算法很熟悉。但是，Brandes算法将计算网络中所有节点的间度。我认为可以计算O(n^2*L)中
浏览 1提问于2011-06-30得票数 0
1回答
有N个城市，有M个双向道路连接它们，我必须找到两个固定城市A和B之间的最短路径。dijkstra algorithm();
cout<<Distance[D]<&
浏览 2提问于2014-12-30得票数 3
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
回答已采纳
福特Fulkerson算法将在O(|E|f)时间内运行，其中f是最大流；但是，是否有方法使其运行O(|E|)？让它运行少于O(|E|f)的解决方案之一是选择一条允许流量最大增加的扩充路径，使用与使用加权最短路径问题等查找路径相关的东西，但我能保证它在O(|E|)时间运行吗？基本上忽略了寻找扩充路径所需的时间复杂度(即，无论算法是什么，让复杂度为O(1))。
如果没有这样的方法，那么反例是什么？如果是，我需要使用什么方法？
浏览 4提问于2014-04-13得票数 3
1回答
找到从顶点1到顶点N的最短路径，或者声明这种路径不存在。
我把它从另一个问题中拿出来，只是替换了变量名和一些单词，因为它听起来适用于这个问题。我如何表示最短的路径？它是路径的数目，所有路径</
浏览 2提问于2016-04-25得票数 0
回答已采纳
如何从谦卑中着手以下任务：
我可以通过使用BFS生成迷宫和搜索最短路径来找到最短路径，但是由于最坏的时间复杂度预计为O(N)，我不认为这是正确的方法。BFS的时间复杂度为O(x=0)，其中V为顶点数，E为边数。例如，如果N= 3，我们有一个大小为17x17的网格，很明显，我们不能在三个步骤中找到路径。因此，要么指出的时间复杂度是错误的，应该是像M^2，或者有一个快速的技巧，简单地计算两个点之间的距离，而不用图形算法。我发现了一些计算两
浏览 1提问于2016-08-04得票数 1
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
