最小生成树害怕负重吗？

我认为最短路径（SP）有负权重的问题，因为它将路径上的所有权重相加，并试图找到最小路径。

但我不认为最小生成树（MST）在负权重方面存在问题，因为它只需要单个最小权重边而不关心总权重。

我对不对？

考虑[计算机科学@ stackexchange]（http://cs.stackexchange.com/）？ – HongboZhu

@HongboZhu是啊，也许下一次 –

顺便说一句，当图中所有的边都是负数时，找到最短路径与寻找最长路径的问题是一样的，其边界标有绝对值的原始长度。已知最长路径问题是NP难题。 – Palec

是的，你说得对。 MST的概念允许任意标志的权重。用于查找MST的两种最流行的算法（Kruskal's和Prim's）可以在负边缘上正常工作。

实际上，你可以在你的图的所有边上添加一个很大的正常数，使所有的边都是正的。 MST（作为边缘的一个子集）将保持不变。

2012-05-02 12:54:21 Skiminok

事实上，作为图的子图的树具有取决于顶点数量的固定数量的边缘，因此向每个边缘成本添加数字“p”会增加“pE”的总体mst成本。找到最短路径并不正确，因为最短路径可以由不同数量的边组成。 – enedil

找到MST的两种最流行的算法（Kruskal's和Prim's）可以在负边缘上正常工作，因为它们在无向图上工作 – raghavsood33

是的，你是对的，因为如果你看到像dijkstera这样的最短路径算法，它会检查当前顶点v的距离是否大于当前值+边权重的总和，那么它会改变顶点距离的值v从s的总和值，如果边的权重为负，那么它会带来一些问题。

但是在MST问题中存在像prim，kruskal这样的算法，这些算法只取最小权重边缘，从而使负边缘适合于MST。

2017-02-13 08:05:19

回答