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

Question

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

我认为最短路径（SP）对负权重有问题，因为它将沿路径加起来的所有权重相加，并尝试找到最小值。

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

我说得对吗？

- Jackson Tale

---

顺便提一下，当图中的所有边都是负数时，寻找最短路径与为带有原始长度绝对值标记的边的图寻找最长路径是相同的问题。已知最长路径问题是NP难问题。 - Palec

谢谢您的提问。您能否告诉我为什么您认为算法不受负边影响？我也已经阅读了回复。 - Avv

Answer 1

是的，你说得对。最小生成树（MST）的概念允许边权为任意符号。寻找MST的两种最流行算法（Kruskal和Prim）可以处理负权边。

实际上，你可以将一个大正常数加到图中所有的边上，使所有边都变成正数。MST（作为边的子集）仍然保持不变。

- Skiminok

---

一棵作为图的子图的树，其边的数量固定取决于节点数，因此将每条边的权值增加一个值p会使得最小生成树的总权值增加pE。然而在寻找最短路径时不成立，因为最短路径可以由不同数量的边组成。 - enedil

寻找最小生成树的两种最流行算法（Kruskal和Prim）适用于带有负边的图，因为它们适用于无向图。 - raghavsood33

Answer 2

是的，你说的对。因为如果你看最短路径算法（比如Dijkstra算法），它会检查当前顶点v的距离是否大于当前值加上边权值的和，如果是，就将距离s的顶点v的数值更改为总和的数值。但是，如果边权值为负，则会出现一些问题。

但是，在最小生成树（MST）问题中，有像Prim和Kruskal这样的算法，只选取最小权重的边，这使得负边可以符合MST的要求。

- Rahul Dhawan

Answer 3

是的，你是正确的。 Prim算法与Dijkstra算法类似，但在Prim算法中，不应计算从i到j具有负边的最短路径。因此，还有另一个算法，即Bellman-Ford算法，用于计算具有负边缘的从i到j的最短路径。

因此，Prim和Kruskal算法对负边缘不公平。

- REVANASIDDA