これは、Why most graph algorithms do not adapt so easily to negative numbers?のフォローアップの質問です。最小スパニングツリーは負の重みを恐れていますか？
私は最短経路（SP）が負の重みに問題があると思うのは、経路に沿ってすべての重みを合計し、最小のものを見つけようとするからです。
しかし、最小スパニングツリー（MST）は負の重みには問題がありません。なぜなら、全体の合計重みを気にすることなく、単一の最小重みエッジしかないからです。
私は正しいですか？
はい、あなたは正しいです。 MSTの概念は、任意の符号の重みを可能にする。 MST（KruskalとPrim）を見つけるための2つの最も一般的なアルゴリズムは、負のエッジでうまく動作します。
実際には、グラフのすべてのエッジに大きな正の定数を追加して、すべてのエッジを正にすることができます。 MST（エッジのサブセットとして）は同じままです。
グラフのサブグラフであるツリーは、頂点の数に応じて一定数のエッジを有するので、すべてのエッジコストに数pを追加すると、pEの全体的なコストが増加します。最短経路が異なる数の辺から構成され得るため、最短経路を見つけることは真実ではない。 – enedil
MST（KruskalとPrim）を見つけるための2つの最も一般的なアルゴリズムは、無向グラフで動作するため、負のエッジでうまく動作します – raghavsood33
dijksteraのような最短経路のアルゴリズムを見ると、頂点vの現在の距離が現在の値+エッジの重みの合計よりも大きいかどうかをチェックし、頂点の距離の値を変更するためですvをsからsの値で除算し、エッジの重みが負の値であれば、いくつかの問題が発生します。
しかし、MSTの問題には、プリムのようなアルゴリズムがあります。kruskalはMSTのために負のエッジを作るように最小ウェイトしか取らない。
[computer science @ stackexchange]（http://cs.stackexchange.com/）？ – HongboZhu
@HongboZhuええ、たぶん次の時間 –
BTWグラフのすべてのエッジが負の場合、最短パスを見つけることは、元の長さの絶対値でラベル付けされたグラフを持つグラフの最長パスを見つけることと同じ問題です。最長経路問題はNP困難であることが知られている。 – Palec