如何求mst中所有顶点对的最大路径边

文章/答案/技术大牛

发布

0回答

algorithm、graph、depth-first-search、minimum-spanning-tree

假设我们有一个已知的最小生成树。每条路径的最大边：路径1-2 :它只包含成本为10的边，所以答案是10。路径</

浏览 0提问于2016-12-30得票数 1

2回答

将图中的非MST边缘更改为

algorithm、graph、minimum-spanning-tree

设计一种算法，该算法采用加权图G，并找出代价对非MST边的最小变化，这将导致G的最小生成树发生变化。若要更改MST，我们需要更改非MST边缘s.t的权重。它比它的起始顶点和MST中的结束顶点的路径中的最大</em

浏览 1提问于2012-05-28得票数 1

1回答

满足三角不等式的图中所有边权和与MST的关系

graph、computer-science、proof、minimum-spanning-tree

一个具有n个顶点和m个边的加权无向图若对每条边(u，v)的权重小于或等于从u到v的任何其他交替路径的长度，则称为满足三角不等式。证明了对于这样一个图，所有边的总权重是<= ( MST +1)*MST，其中MST是最小生成树的所有边的总权重。 (提示:不属于最小生成树的图

浏览 2提问于2015-10-09得票数 1

回答已采纳

1回答

Kruskal算法:当边缘成为强制时更新MST

algorithm、computer-science、graph-algorithm、kruskals-algorithm

首先，人们问到MST的成本是多少。}然后，对于初始图中的每一条边，询问新的MST的成本是多少--该边将出现在最小生成树中。如果边缘已经存在于MST中，则答案将保持不变。否则，我可以再次运行Kruskall。，总的复杂性是: O(E*E) 我的问题是，是否有更好的解决方案更新MST，如上文所述。我想的是，当

浏览 1提问于2016-05-07得票数 0

回答已采纳

1回答

在两个给定节点/顶点之间的路径中查找最大边

matlab、graph-theory、depth-first-search、minimum-spanning-tree

我正在尝试通过在MST中添加一个新顶点来更新MST。为此，我一直在关注Chin和Houck的“更新生成树”。论文中的一个步骤要求我在两个给定顶点之间的路径中找到最大的边。我的想法是找到顶点之间所有可能的路径，然后从路径中找到最大的

浏览 0提问于2012-07-16得票数 0

回答已采纳

1回答

在一个图中，两个顶点之间的最短路径怎么会比图的最小生成树中这两个顶点之间的路径长呢？

tree

既然最短路径已经是“最短的”，那么它有可能比MST中的任何其他路径都长吗？我知道这两个顶点之间的路径通常比两个顶点之间的最短路径长，但它能更短吗？

浏览 18提问于2020-02-05得票数 1

3回答

如果图中的一条边改变了它的权重，如何从旧的MST中获得新的MST？

algorithm、graph-algorithm

我们知道原始的图和原始的MST。现在我们改变图中一条边的权重。除了Prim和Kruskal之外，有没有办法从旧的MST生成新的MST？

浏览 0提问于2012-11-18得票数 4

1回答

最大路径挑战--最大生成树中最有效的路径查找方法

algorithm、optimization、data-structures、graph-theory、graph-traversal

这个问题是我先前提出的类似问题的延续：。问题摘要：我需要找到图中从顶点A到顶点B的最佳路径，假设路径质量是以路径上边权的最小值来计算，其次是具有最大最小值的最佳路径。通常情况下，它被称为。以前我需要用非常小的图(最多15个顶点)来解决这个问题，所以我不需要复杂的算法，而且在友好的人的帮助下，我设计了我

浏览 2提问于2013-09-04得票数 0

1回答

创建一个“满意”的最小生成树(MST)

algorithm、performance、graph、minimum-spanning-tree、processing-efficiency

经典MST问题给定V个顶点的可能边，其边数通常比M小得多。我的问题:边集是隐含的，而不是给定的在我的例子中，我有一组V点，其中每个顶点都是二维平面上的坐标(x，y)。我根本没有得到任何<em

浏览 0提问于2017-08-14得票数 3

回答已采纳

3回答

构造覆盖顶点特定子集的最小生成树

algorithm、tree、graph-theory、graph-algorithm

我有一个无向，正边权图(V，E)，我想要一个最小生成树覆盖一个顶点的子集k( Steiner树问题)。我并不是将生成树的大小限制为k个顶点，而是确切地知道在MST中必须包含哪些k个顶点。从整个MST开始，我可以缩小边缘/节点，直到得到包含所有k的最小MST为止。我可以使用Prim的算法获得整个MST，并在子集k的<e

浏览 5提问于2011-10-07得票数 44

1回答

带度约束的最小生成树

algorithm、graph、graph-algorithm、minimum-spanning-tree、degrees

我必须解决这个问题：我知道这个算法可能会产生错误的MST (见@AndyG注释)，所以我想到了

浏览 10提问于2015-05-17得票数 2

回答已采纳

3回答

最小生成树害怕负权重吗？

algorithm、data-structures、graph、minimum-spanning-tree

我认为最短路径(SP)有负权重的问题，因为它将路径上的所有权重相加，并试图找到最小的一个。我说的对吗？

浏览 7提问于2012-05-02得票数 56

回答已采纳

2回答

修改最短路径以获得最小代价路径

algorithm、graph、theory、graph-algorithm

如果我们修改最短路径问题，使得两个顶点之间的路径的成本是其上边的成本的最大值，那么对于任何一对顶点u和v，它们之间遵循最小成本生成树的路径是最小成本路径。我如何证明这种方法是正确的？这是有道理的，但我不确定。有没有人知道文献中是否存在这种算法？它有名字吗？

浏览 0提问于2011-11-02得票数 3

回答已采纳

2回答

关于最小生成树的算法证明，我的答案正确吗？

algorithm、minimum-spanning-tree

问:证明了如果加权图中没有两条边具有相同的权重，则每个最小生成树(MST)中都包含与顶点v关联的权重最小的边。我的回答是:给定一个顶点( V )和一个加权图(G)，我们注意到∃(存在)和与V相关的边(E)是最小权重的边。请注意，我们将有两个不同的顶点，它们将具有相同的最小权重边。这对我们来说不

浏览 0提问于2011-11-28得票数 0

回答已采纳

1回答

最短路径与最小生成树的组合

c++、algorithm、shortest-path

我试图得到一个无向加权graph.However的最小生成树，我需要找到一个或多个nodes.After之间的最短路径，这就是，我必须找到一个图的最小生成树。我已经找到了必要节点之间的最短路径，但是我不知道如何找到最小生成树，包括这些最短路径。让我举一个例子。A F ------B E -----D-----C在A和E之间还有一个有2

浏览 2提问于2013-12-22得票数 1

1回答

在Minimax路径查找解决方案中找到路径和最大边缘？

path-finding、depth-first-search、minimum-spanning-tree、minimax、prims-algorithm

我目前有一个编程任务:给定一个大的加权不连通图(1 <V< 2000，0<E< 100 000)。查找从“源”到“目的地”的最小加权路径上的最大加权边。到目前为止，我得到的是将图存储在AdjacencyList ( IntegerPair向量的向量)中，其中第一个整数是相邻的，第二个是边的权重。，并在下面的查询中返回最大权

浏览 2提问于2014-10-06得票数 0

4回答

检查在线性时间内的某些MST中是否包含边(非独异值)

algorithm、minimum-spanning-tree

我正在研究一种算法，以检查给定的边是否包含在所有可能的mst中。我是不是错过了什么

浏览 2提问于2013-02-24得票数 22

回答已采纳

2回答

最小生成树，最大限度地降低成本

algorithm、minimum-spanning-tree

我们有一组E的道路，一组H的高速公路，以及一组不同城市的V。我们也有与每条道路i相关的成本x(i)和与每条高速公路i相关的成本y(i)。我们想要建造连接城市的道路，条件是在任何一对城市之间总是有一条路径，并且我们最多只能建造一条高速公路，这可能比道路更便宜。集合E和集合H是不同的，它们各自的成本是无关的。

浏览 2提问于2015-10-11得票数 0

3回答

查找连接所有节点的最短路径集

algorithm、search、optimization、graph-theory、shortest-path

我想找出一组总长度最短的连接它们的路径。(启发式解决方案ok，不需要精确。) 这可能听起来像旅行推销员的问题，但它是不同的。我不是在寻找一个周期，它将访问每个点一次并且只有一次。我只需要每个点连接到至少一个其他点，这样集合中的所有点至少间接地彼此连接，所选连接的长度之和将被最小化。因此，它应该是非循环的，以最小化连接长度的总和。简单的最近邻居算法(即，将每个点连接到尚未连接到它<e

浏览 6提问于2020-01-31得票数 1

1回答

最小生成树与生成树的区别

algorithm、graph、tree、difference、minimum-spanning-tree

我一直在阅读生成树的概念及其类型。这就是我所理解的：最小生成树：是一种生成树，其边权之和最小。这是否意味着，在检索MST时，如果我们在G中遇到一条边较多的路径(与其他路径相比)，但在边权之和上的权重最小(与所有其他路径相比)

浏览 3提问于2020-05-02得票数 0

回答已采纳

点击加载更多