2回答
我想通过消除负圈来解决图的最小费用流问题。Goldberg和Tarjan在1989年发表了一篇以此为标题的论文，但我既找不到原始版本的副本，也找不到任何可能解释相同算法的更新的衍生作品。有没有人有描述这个算法的文档或者实现它的代码？
浏览 0提问于2011-03-27得票数 1
设G是一个无负圈的有向加权图，设计了一种算法，以求G中的最小权圈，其时间复杂度为O({x}V}^3)。我在这个问题上走在正确的轨道上吗？是否有可能修改弗洛伊德-沃尔算法<
浏览 1提问于2014-03-30得票数 3
回答已采纳
如何通过删除回路来最小化有向图的顶点数量？有没有可以在这里改编的算法？ 已经有一个关于删除图中的圈的问题，但我特别询问通过删除图中的圈来最小化顶点的数量。
浏览 20提问于2021-08-08得票数 0
1回答
在Dijkstra的算法中，松弛最多被称为m乘以(其中m=#边)。我试着找出一些具体的图例子，它确实是被执行了很多次。
浏览 1提问于2012-10-21得票数 1
一些组合优化问题，如最大网络流，最小费用网络流，多商品最小费用流，或最短距离路径/路径对问题，都能够扩展到非常大的规模。
是否有人有成功/失败的经验来应用MapReduce来处理这些类型的问题？
浏览 0提问于2011-08-10得票数 2
1回答
考虑圈覆盖问题:给定一个图G，我们寻找一组C圈，使得V(G)的所有顶点都在C的至少一个圈中，且C中的圈数最小。我的任务是证明这个问题不允许绝对逼近，即不可能有一个算法H，对于该问题的所有情形I，H(I) <= OPT(I) + k，其中OPT(I)是i的最优值，k是一个大于或等于1的数。通常的技巧是证明如果存在该算法，我们可以在多个时间内解决一些NP-困难问题。
有人知道哪一个问题可以用来解决这个问题吗？
浏览 0提问于2014-06-16得票数 1
回答已采纳
1回答
我想找出加权有向图中由4条边构成的最短圈(最短=边的最小权和)。
我知道我可以使用弗洛伊德-沃尔算法来寻找图中的最短圈，如所描述的那样。但我不知道如何才能找到由四边构成的最短循环。
浏览 2提问于2015-04-11得票数 1
回答已采纳
1回答
具有最少轮数的网格上的生成树
、、、、
是否有一个多项式算法可以找到无向网格图的生成树，从而最小化树中的圈数？转弯是指有两条边连接到一个具有垂直方向的顶点。
关于近似算法的想法也可能有用。
浏览 6提问于2018-08-03得票数 2
1回答
是否有一种算法以有向图作为输入，并作为输出给出最小数目的边“中断”，以防止循环？例如，上面的图中的循环是：
是否有一种既定的算法可以做到这一点？
浏览 4提问于2020-12-01得票数 3
设G= (V，E)是不含负圈的有向赋权图。如何修改福特bellman算法，使其在while循环的m+1次迭代后停止。M是最小路径中的最大弧数(根据权重而不是道路中拱门的数量确定的最小道路)
浏览 6提问于2020-07-03得票数 0
我希望尽量减少两项职能：b.源和目标之间的边沿总数。如果我只需要最小化(a)，我就会使用Dijkstra的算法；如果我只需要最小化(b)，我就会使用BFS。
但是，考虑到我必须将两者都最小化，我可以只使用Dijkstra的算法吗？换句话说，如果我从障碍中找到代价最小的路径，Dijkstra的算法是否也保证了获得的路径长度(在源和目的地之间)是最短的？
浏览 10提问于2022-09-02得票数 0
1回答
我喜欢在有向图(有时可能有圈)中找到最小生成树(甚至是森林)。解释的那个有一些错误。在Python中有没有这个算法的包/代码可以实际工作？
浏览 8提问于2016-08-04得票数 1
我知道在web.But上有很多计算最小围圈(SEC)的算法，我想知道为什么一个简单的算法不适用于它。我的想法是:我有一组点，我认为我可以用以下方法计算出它们最小的包围圆(SEC)：
计算集合中每个点与cPoint之间的距离。
浏览 3提问于2014-01-29得票数 0
例如，我如何通过Python中的ortools简单地找到(x-1)^2的最小值？
我读了ortools的文档，但我找不到它。我知道它不属于线性优化，但我在它的文档中找不到合适的类型。
浏览 159提问于2018-06-02得票数 2
回答已采纳
2回答
寻找不含负圈的强连通子图
、、、、
是否有解决以下决策问题的算法：G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。本文给出了最小强连通子图问题的一个近似解。
解决这个问题的一种天真的方法是使用福特-贝尔曼或弗洛伊德-沃肖尔算法找到图的负圈，从这个圈中删除一条边，并在图仍然是强连通的情况下重复。但这种幼稚的方法时间复杂度很低，因为我们可能会运行福特-贝尔曼算法，并多次检查强连通性--此外，我无法证明该<
浏览 5提问于2019-12-31得票数 5
1回答
可以使用Prim算法或Kruskal算法来寻找顶点/节点和边/链路的集合的最小生成树/图。我想要的是找到这个集合的最小生成图的算法，但是结果图只需要包括任意选择的节点，而不是所有节点。这样的算法存在吗？也许在修改图以仅包括所需节点后，可以只使用Prim(或Kruskal)算法？但是，我不确定如何修改图形来做到这一点，同时保持它的连通性。假设我们稍微修改一下图表：(2)/ \(1) (2)
B C ------
浏览 1提问于2012-10-31得票数 7
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
