[解決済み] 最小スパニングツリーは負の重みを恐れているのか？

質問

の続きの質問です。 なぜ多くのグラフアルゴリズムは負の数に適応しにくいのか？ .

最短経路（SP）は、経路に沿った重みをすべて足して最小のものを探そうとするから、負の重みが問題になるのだと思う。

しかし、最小スパニングツリー（MST）は、全体の重みを気にせず、最小重みのエッジを1つ選ぶだけなので、負の重みの問題があるとは思えません。

そうでしょうか？

解決方法は？

はい、おっしゃるとおりです。MSTの概念では、任意の符号の重みを許容しています。MSTを求める最もポピュラーな2つのアルゴリズム（クラスカルのものとプリムのもの）は、負のエッジでも問題なく動作します。

実は、グラフのすべての辺に大きな正の定数をつけて、すべての辺を正にすればいいのです。MSTは（エッジのサブセットとして）変わりません。