2回答
单纯形算法被认为具有指数的最坏情况时间复杂度。然而，它在实践中仍然经常被使用。如何确定某个问题(用单纯形解决)的平均时间复杂度？谢谢您抽时间见我。
浏览 4提问于2011-12-28得票数 10
回答已采纳
在最大流问题中，当我应用ford-fulkerson算法寻找最大流时，如果图的所有链接都有权重1，则最大流将是我在ford fulkerson算法中找到的路径数，对吗？我是说，dfs路径的数目。
浏览 4提问于2014-04-17得票数 1
回答已采纳
福特Fulkerson算法将在O(|E|f)时间内运行，其中f是最大流；但是，是否有方法使其运行O(|E|)？让它运行少于O(|E|f)的解决方案之一是选择一条允许流量最大增加的扩充路径，使用与使用加权最短路径问题等查找路径相关的东西，但我能保证它在O(|E|)时间运行吗？基本上忽略了寻找扩充路径所需的时间复杂度(即，无论算法是什么，让复杂度为O(1))。
如果没有这样的方法，那么反例是什么？如果是，我需要使用什么方法？
浏览 4提问于2014-04-13得票数 3
1回答
请给出几种无向图最小割集的确定性算法，以及它们的复杂度。(顺便说一句，我知道福特-富尔克森算法有一个无向版本，它为每个有向边缘增加了一个相反的平行边，有人能告诉我这个算法的时间复杂度是多少，或许可以给我更多的参考？)
谢谢。
浏览 7提问于2015-09-16得票数 2
1回答
寻找组合的不同算法的最坏情况下的时间和空间复杂度是什么，即nCr，哪种算法在时间/空间复杂度方面是最知名的解决方案？
浏览 0提问于2015-08-13得票数 0
2回答
所需时间复杂度: O(n^2(n + m))对于G中的每个节点，执行以下操作：
我的解决方案正确吗？
浏览 3提问于2019-09-13得票数 1
回答已采纳
1回答
我需要在这个网络中找到最大流量。这部分是一般的最大流量.然而，在这个特殊版本的最大流问题中，两个目标必须得到相同的流量。
有人能帮我吗?我该怎么做？
浏览 6提问于2014-01-21得票数 6
回答已采纳
1回答
图-具有顶点权的最短路径
、、、、
这个问题涉及到图G中顶点a和b之间最便宜的路径的寻找。路径的代价是在该路径上遇到的边和顶点的代价之和。给出了一种从a到b寻找最便宜路径的有效算法及其时间复杂度。(a)
浏览 3提问于2012-05-04得票数 21
回答已采纳
1回答
我很难理解某些逻辑。我有一个二部图如下所示。我希望找到最优匹配的所有顶点在左侧(Viz，A1，A2，A3，A4)。我从朋友那里得到了一个建议，那就是边权之和可以用来解决这个问题。不过，我不知道，在这种情况下，边权之和会有什么帮助。例如，对于A1，我可以说AL2是最好的匹配，依此类推。然而，我的朋友建议，边缘权重是这个问题的最优解决方案。我无法理解如何才能成为最佳解决方案。他的想法是，所有的(A1，A2，A3，A4)都将连接到所有的(AL1，AL2，.，AL6)，对于每个边，我们将计算边权的总和。有人能帮我理解他的真正意思吗？
编辑:我认为这可能不是二分图中完美匹配的情况，因为左边的
浏览 5提问于2013-09-19得票数 0
回答已采纳
1回答
我有一个关于网络中最大流量的问题。我试图在图中找到一个割集，它可能会断开源和目标之间的连接。我探索了图中从源到目的地的所有边独立路径。接下来，我从每条路径中选取一条边，并将它们分组在一起。
浏览 0提问于2012-11-28得票数 0
3回答
动态图中的最大流
、、
我正在寻找快速算法来计算动态图中的最大流量(添加/删除具有相关边的节点到图中)。也就是说，我们在G中有了最大流，现在添加/删除了带有相关边的新节点，我不喜欢重新计算新图的最大流，实际上，我想使用以前的结果来计算这个图。
任何不占用大量时间/内存的预处理都会被占用。最简单的想法是重新计算流程。另一个简单的想法是，保存之前的最大流量计算中使用的所有增加路径，现在为了添加顶点v，我们可以找到简单的路径(在上一步更新的容量图中)，这些路径从源开始，
浏览 0提问于2012-01-26得票数 10
回答已采纳
3回答
连接两棵红黑树的最好方法
、、、
最简单的方法是将两个树存储在两个数组中，合并它们，并使用一个排序的数组构建一个新的红黑树，所需时间为O(m + n)。
有没有时间复杂度更低的算法？
浏览 1提问于2017-04-29得票数 3
1回答
我知道在平面图中求最小割数的算法。您创建了一个对偶图，其中每个顶点对应于原始图的面，边对应于连接两个面的最小边。
然后使用Dijkstra在这个图中找到最小路径。
浏览 2提问于2012-05-20得票数 1
1回答
我使用网络单纯形算法来解决有向图中的最大流问题。为了比较几种路由算法的执行时间，我需要使用George的单纯形方法的实现。
我的问题是：单纯形方法能解决给定有向图中的最大流问题吗？
浏览 5提问于2019-05-08得票数 0
回答已采纳
今天，我在msdn中看到了博客，我注意到了如何计算算法的时间复杂度。我完全理解如何计算算法的时间复杂度，但在最后，作者提到了以下几行
(N+4)+(5N+2)+(4N+2) = 10N+8
因此，上述算法的渐近时间复杂度为O(N)，这意味着上述算法是线性时间复杂度算法为什么说它是基于线性时间复杂度
浏览 11提问于2012-05-11得票数 0
回答已采纳
1回答
Edmonds-Karp算法表示，每次增加最短路径时，源s和宿t之间的最短距离t单调增加。在这个假设下，源s和宿T之间的距离t将不会大于|V| - 1。如果这是真的，那么寻找最大流的复杂度将是(|V| - 1) * E。
我知道我错误地假设了上面的某些东西。但是不能理解它是什么。有人能帮我吗？
浏览 17提问于2017-03-14得票数 0
1回答
唯一的最大流算法
、、
如何检查图网络是否包含唯一的最大流？有没有什么多项式时间的算法可以做到这一点？谢谢!edit2:我需要知道图网络是否有唯一的最大流(我只能以一种方式将最大流从源发送到汇点)。
浏览 2提问于2013-12-31得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
