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

Question

这是为什么大多数图算法不那么容易适应负数的后续问题？.

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

但我不认为最小生成树（MST）有负权重的问题，因为它只需要单个最小权重边缘而不关心整体总权重。

我对吗？

Answer 1

是的你是对的。MST 的概念允许任意符号的权重。寻找 MST 的两种最流行的算法（Kruskal's 和 Prim's）可以很好地处理负边缘。

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

Answer 2

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

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

Answer 3

是的，你是对的 Prim 的算法与 dijkstra 的算法一样工作，但在 prim 的算法中，它不应该计算从 i 到 j 的最短路径有负边。因此，他们的另一种算法是他们的贝尔曼福特算法，用于计算从 i 到 j 的最短路径，具有负边缘。

因此 prim 和 Kruskal 的算法并不害怕负边缘。