最小生成树是否害怕负权重？

Question

我认为Shortest Path(SP)在负权重方面存在问题,因为它会沿着路径累加所有权重并尝试找到最小权重.

但我不认为最小生成树(MST)存在负权重问题,因为它只需要单个最小权重边缘而不关心总权重.

我对吗？

Answer 1

是的,你是对的.MST的概念允许任意符号的权重.用于寻找MST(Kruskal和Prim's)的两种最流行的算法在负边缘下工作正常.

实际上,您可以在图形的所有边缘添加一个大的正常数,使所有边缘都为正.MST(作为边缘的子集)将保持不变.

事实上,作为图形子图的树根据顶点数量具有固定数量的边缘,因此向每个边缘成本添加数字"p"会增加"pE"的总体成本.找到最短路径并不是这样,因为最短路径可以包含不同数量的边缘. (11认同)
两种最流行的 MST 算法（Kruskal 算法和 Prim 算法）可以很好地处理负边，因为它们适用于无向图 (2认同)

Answer 2

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

但在MST问题中，有像prims、kruskal这样的算法，它们只取最小权重边，使负边符合MST的条件。