algorithm - 最小スパニング ツリーは負の重みを恐れていますか?

Question

これは、ほとんどのグラフ アルゴリズムが負の数に簡単に適応しないのはなぜですか?のフォローアップの質問です。.

最短パス (SP) は、パスに沿ってすべての重みを合計し、最小のものを見つけようとするため、負の重みに問題があると思います。

しかし、最小スパニング ツリー (MST) が負の重みの問題を抱えているとは思いません。なぜなら、全体の重みの合計を気にせずに、単一の最小重みエッジを取るだけだからです。

私は正しいですか？

Answer 1

はい、あなたは正しいです。MST の概念では、任意の符号の重みを使用できます。MST を見つけるための 2 つの最も一般的なアルゴリズム (Kruskal と Prim) は、負のエッジで問題なく機能します。

実際には、グラフのすべてのエッジに大きな正の定数を追加して、すべてのエッジを正にすることができます。MST (エッジのサブセットとして) は変わりません。