这是Why most graph algorithms do not adapt so easily to negative numbers?的后续问题。
我认为Shortest Path（SP）在负权重方面存在问题，因为它会沿着路径累加所有权重并尝试找到最小权重。
但我不认为最小生成树（MST）存在负权重问题，因为它只需要单个最小权重边缘而不关心总权重。
我对吗？
是的，你是对的。 MST的概念允许任意符号的权重。用于寻找MST（Kruskal和Prim's）的两种最流行的算法在负边缘下工作正常。
实际上，您可以在图形的所有边缘添加一个大的正常数，使所有边缘都为正。 MST（作为边缘的子集）将保持不变。
是的，你是对的，因为如果你看到像dijkstera这样的最短路径的算法，它将检查顶点v的当前距离是否大于当前值+边缘权重的总和，那么它将改变顶点v与s的距离的值。总和值，如果边缘权重为负，则会产生一些问题。
但是在MST问题中，有像prims，kruskal这样的算法只采用最小权重边缘，因此使得负边缘符合MST。
是的，你是对的Prim的算法就像dijkstra的算法一样，但是在prim的算法中，它不应该计算从i到j的具有负边缘的最短路径。因此，它们是另一种算法，它们是Bellman-Ford算法，用于计算从i到j的具有负边缘的最短路径。
因此，prim和Kruskal的算法并不担心负边缘。