最小生成树与最短路径树
在一个具有不同正边的无向图中，是否可能有一个MST与最短路径树没有公共边？
我一直试图引出不同的例子，但似乎这是不可能的。最短路径树中的最短路径边似乎也应该包括在MST中。
共有1个答案
考虑到Prim的算法，您从一个顶点v开始，并开始以一种成本最低的方式将其他顶点连接到它上。因此，对于你连接到你用Prim算法增长的连通分量的任何其他顶点u（即，包含顶点v的那个），尽管可能存在（我认为）一个顶点w可以在更短的距离内到达u，但没有更短的方法从v到达u，因为Prim算法规定，你通过去添加最便宜的节点来扩展你开始的连通分量。
因此，由于从v到u没有更短的到达路径，所以从v和v的最短路径树出发生成的MST中至少有1条共同的边。
即使MST（如rootA）和最短路径树（如rootB）的节点根不同，在构建MST时，Prim的算法也应该使用最短路径树上从rootB到rootA的最短路径上的边到达rootB，因为根据它的定义，最短路径树应该帮助rootB以尽可能短的方式到达rootA。
-
给了我一个问题，上面写着： 给定一个具有整数权值（正负两种）的连通有向图，发展一种求两顶点之间最短路径的算法。 我想我可以使用最小生成树算法，比如Kruskal的算法，然后用Dijkstra的算法来证明，因为在MST中，每个顶点只有一条内边，Dijkstra的算法即使在负权值下也能工作。 这听起来像是共食吗？ 附注。我很难证明MST包含有向图的每个顶点的最短路径。
-
(b)假设图的最小生成树是唯一的。无向图的最小生成树中一对顶点之间的路径一定是最短（最小权）路径吗？ 我的回答是 (a)
-
我们有一个边带正权的有向图G(V，E)，作为源顶点s，目标点T。此外，最短的s-t路径包括图中的每一个其他顶点。我需要计算s和t之间的交替最短路径距离，以防某些边e∈e被删除。我想设计一个O(e^2logV)算法，它计算图G\e中所有e∈e的最短S-T路径距离。最后的输出应该是一个大小为E的数组，其中edge E的条目应该包含G\E中最短的S-T路径距离。
-
这个问题是NetworkX特有的。我可以创建自己的函数来完成所有我需要的事情，但是这需要更长的时间，所以我想避免它。 情况： 我有一个未加权图，由NetworkX无向图表示。从这个图中，我寻找“最短循环”——也就是说，对于给定的节点k，我正在寻找最短的简单路径（只通过一个节点一次），它离开k，然后返回k。 为了实现这一点，我想使用任何NetworkX最短路径算法，并从节点k到节点k进行搜索。问题是
-
赋权图G的最小瓶颈生成树是G的生成树，使得生成树中任何边的最大权值最小。MBST不一定是MST（最小生成树）。 请举例说明这些说法有意义的地方。
-
我一直在读生成树的概念及其类型。这就是我所理解的： 生成树：图G中连接所有顶点的边数最小的子集 最小生成树：它是边权的总和最小的生成树。 现在，这是否意味着，在检索MST时， > 如果我们遇到G中的一条路径，它有更多的边（与其他路径相比），但在边权重总和上的权重最小（与所有其他路径相比），我们将不把它视为MST？ MST的概念是否只有在G有多个生成树的情况下才起作用？其他跨树=mst？ 谢谢你的帮